Influence of Neighborhood Forms on the Quality of Pseudorandom Number Generators' Work Based on Cellular Automata

Influence of Neighborhood Forms on the Quality of Pseudorandom Number Generators' Work Based on Cellular Automata

Sergii Bilan (Onseo Company, Ukraine)
DOI: 10.4018/978-1-7998-1290-6.ch003
OnDemand PDF Download:
No Current Special Offers


The chapter analyzes modern methods for constructing pseudo-random number generators based on cellular automata. Also analyzes the influence of neighborhood forms on the evolution of the functioning of cellular automata, as well as on the quality of the formation of pseudo-random bit sequences. Based on the use of various forms of the neighborhood for the XOR function, the quality of generators was analyzed using graphical tests and NIST tests. As a result of experimental studies, the optimal dimension of cellular automata and the number of heterogeneous cells were determined, which make it possible to obtain a high-quality pseudo-random bit sequence. The obtained results allowed to formulate a method for constructing high-quality pseudo-random number generators based on cellular automata, as well as to determine the necessary initial conditions for generators. The proposed generators allow to increase the length of the repetition period of a pseudo-random bit sequence.
Chapter Preview

Actuality Of Research

Today, there are a large number of pseudo-random number generators that have different quality of pseudo-random number formation and a different basis for their construction. (Schneier, 1996; Bilan, 2017; Chugunkov, 2012; Neumann, 1951; L'Ecuyer, 1998; Marsaglia, 2003; Suhinin, 2010a; Wolfram, 1986a). The implementation of generators has a various nature. A large number of developed pseudo-random number generators (PRNG) are due to their widespread use in various fields of human activity. Such areas as cryptography, protection and diagnostics of data transmission systems, game theory, simulation modeling, and many other areas have a special need for the use of PRNG. All means and processes in which PRNG are used can be divided into the use of the obtained sequence of random numbers, both in statics and in dynamics. The use of a static sequence of random numbers implies the preliminary generation of random numbers and the formation of a database. Then the resulting sequence of random numbers is effectively used.

There is also the need to generate and use random numbers in real time. However, existing requests are not always satisfied with modern generators. This is due to the difficulties of achieving the optimal values of the main parameters of the PRNG. These basic parameters include:

  • 1.

    The length of the repetition period of a sequence of random numbers.

  • 2.

    Low statistical properties of the generated sequence.

  • 3.

    Low speed.

  • 4.

    The degree of independence of consecutive values of numbers.

  • 5.

    Range of numbers.

These characteristics may be acceptable for some tasks and unacceptable for others. A great importance in the construction of the PRNG is its implementation (software or hardware). Often there are such cases when the proposed generator has good statistical properties, but its implementation dramatically reduces the speed, may require additional resources and does not meet the goal.

Based on the described characteristics, it becomes clear that the need to create and develop new algorithms for generating pseudo-random sequences, combining high speed and good statistical properties of the generated initial sequence, still remains relevant.

Complete Chapter List

Search this Book: