In this chapter, the author considers the main theoretical solutions for the creation of pseudo-random number generators based on one-dimensional cellular automata. A Wolfram generator is described on the basis of rule 30. The main characteristics of the Wolfram generator is presented. The analysis of hybrid pseudo-random number generators based on cellular automata is carried out. Models of such generators and their realization with various forms of neighborhoods are presented. Also in the chapter is presented the analysis of the basic structures and characteristics of pseudo-random number generators using additional sources of pseudo-random numbers. As such additional sources the LFSR is used.
TopThe Generators Based On One-Dimensional Cellular Automata: Wolfram Generator
In PRNG based on one-dimensional CA the elementary cellular automata is used. One of the rules is selected and the evolution of the elementary cellular automata on the basis of this rule is studied. In addition, elementary cellular automata in the initial state is set. The signals are generated at the elementary cellular automata cell outputs in each subsequent time step and their values depend from the selected rule (Wolfram, 2002, 1986a, 1986b; Bhattacharjee, Paul, & Das, 2016; Cardell & Fúster-Sabater, 2016).
First PRNG based on the elementary cellular automata was proposed by S. Wolfram and he detailed studied its properties (Wolfram, 1986a, 1986b). S. Wolfram studied the many rules and selected generators, which are similar to the LFSR.
Based rule 30 generator generates a good random sequence.
.
The CA evolution by rule 30 is shown on Figure 1.
Figure 1. An example of the elementary cellular automata evolution based on the rule 30
The generator on the basis of this rule has been investigated in papers (Wolfram, 1986a, 1986b, 1985). In the works is defined class of the rules that are making the elementary cellular automata by similar to the LFSR. These rules use the modulo k function. Most often к=2 is used, In this case, a function is called haw the XOR function. PRNG based on elementary cellular automata was investigated for characteristics such as length of repeat period, spatial and temporal distribution characteristics of elementary cellular automata states and size of elementary cellular automata.
Pseudorandom number generator based on one-dimensional CA have been widely studied in the works (Cattel, Zang, Serra, & Muzio, 1999; Chowdhury, Nandy, & Chattopadhyay, 1994; Sipper, 1999; Bhattacharjee, Paul, & Das, 2016; Cardell & Fúster-Sabater, 2016; Sirakoulis, 2016; Spencer, 2015). Much attention is paid to the study of ECA with different neighborhood structures. The structure of a neighborhood for ECE with memory is defined as
,where r – radius of the neighborhood.
Also, the number of cells on the right (or left) of each elementary cellular automata cell is determined. For example, in paper (Abhisher, Bandyopadhyay, & Maulir, 2008) One-dimensional CA with four a neighborhood cells (4NCA) is considered. In such 4NCA r=2. 4NCA are divided into 4NCA with two right neighbors and 4NCA with two left neighbors. The structures of these neighborhoods are shown on Figure 2.
Figure 2. The neighborhood structures with r=2
The analysis of 4 NCA rules was spent. For this the known tests were used. Variations rules and their compositions were studied. On the basis 4NCA the generators can generate a pseudo-random sequence of a high quality.
Researches of a one - dimensional CA on the basis of various structures of neighborhoods and the rules, is being continued. They give good results. However, they do not indicate the theoretical list of recommendations for obtaining the high quality pseudorandom number generator. Until now, we do not have the necessary characteristic indices for building PRNG based on the elementary cellular automata.