Pseudorandom number generator uses true chaos to generate sequences with random behavior

Algorithms that generate random and pseudorandom sequences of numbers have a variety of important uses, ranging from data encryption and cryptography to lottery drawing. They can also speed up certain program simulations. Pseudorandom sequences have properties resembling those of truly random sequences, like those generated by flipping a coin. But they will never be truly random: Any algorithmic sequence is generated by a relatively short program, but the short program itself shows the regularity of the sequence.

Pseudorandom number generators are optimized to lengthen the period or preperiod of a sequence. Typically, these algorithms are based on number theory so that the periodicity of the sequence is predictable. Although generators based on chaos theory have also been proposed, it is usually more difficult to guarantee these generators have a long period, and they are less widespread than number-theoretic generators.

Saito and Yamaguchi use both chaos and number theories to construct a pseudorandom number generator that produces sequences that behave as if they are truly random. Their approach has a high computational cost, but the high quality of the sequences could be useful, for example, to validate standardized statistical tests for pseudorandom numbers.

The authors simulated the Bernoulli map, a mathematical model well-known to generate purely random binary sequences, using cubic irrational numbers. This approach allowed them to avoid the map’s tendency to become periodic when described with rational numbers, and to reach a fixed point when described with finite binary decimals.

Finally, the authors conducted extensive statistical testing of their generator, demonstrating that it has good statistical properties. They also clarified an advantage that their generator has over the Mersenne Twister MT19937, the most popular pseudorandom number generator, in terms of an independence property.

Source: “Pseudorandom number generator based on the Bernoulli map on cubic algebraic integers,” by Asaki Saito and Akihiro Yamaguchi, Chaos: An Interdisciplinary Journal of Nonlinear Science (2018). The article can be accessed at https://doi.org/10.1063/1.5048115 .