# zbMATH — the first resource for mathematics

Pseudorandom number generator based on the Bernoulli map on cubic algebraic integers. (English) Zbl 1400.65009
Summary: We develop a pseudorandom bit generator using chaotic true orbits of the Bernoulli map on real cubic algebraic integers having complex conjugates. Although this generator has a high computational cost, it exactly simulates the Bernoulli map that can generate ideal random binary sequences. In particular, we clarify a seed selection method that can select initial points (i.e., seeds) without bias and can avoid overlaps in latter parts of the pseudorandom binary sequences derived from them. Moreover, in order to evaluate the memory usage of our generator, we give upper bounds concerning the growth of the representation of points on a true orbit. We also report results of a large variety of tests indicating that the generated pseudorandom sequences have good statistical properties as well as an advantage over one of the most popular generators at this point, the Mersenne Twister MT19937.
 [1] Li, M.; Vitányi, P., An Introduction to Kolmogorov Complexity and Its Applications, (1997), Springer: Springer, New York · Zbl 0866.68051 [2] Sugita, H., Monte Carlo Method, Random Number, and Pseudorandom Number, (2011), Mathematical Society of Japan: Mathematical Society of Japan, Tokyo · Zbl 1236.65004 [3] Knuth, D. E., The Art of Computer Programming, (1998), Addison-Wesley: Addison-Wesley, Reading, MA · Zbl 0895.68054 [4] Lehmer, D. H., Mathematical methods in large-scale computing units, Proceedings of Second Symposium on Large-Scale Digital Calculating Machinery, 141-146, (1951), Harvard University Press · Zbl 0045.40001 [5] Golomb, S. W., Shift Register Sequences, (1982), Aegean Park Press: Aegean Park Press, Laguna Hills, CA [6] Matsumoto, M.; Nishimura, T., Mersenne Twister: A 623-dimensionally equidistributed uniform pseudorandom number generator, ACM Trans. Model. Comput. Simul., 8, 3-30, (1998) · Zbl 0917.65005 [7] Billingsley, P., Ergodic Theory and Information, (1965), Wiley: Wiley, New York · Zbl 0141.16702 [8] Atlee Jackson, E., Perspectives of Nonlinear Dynamics, (1991), Cambridge University Press: Cambridge University Press, Cambridge · Zbl 0769.58019 [9] Rannou, F., Numerical study of discrete plane area-preserving mappings, Astron. Astrophys., 31, 289-301, (1974) · Zbl 0283.58006 [10] Binder, P. M.; Jensen, R. V., Simulating chaotic behavior with finite-state machines, Phys. Rev. A, 34, 4460-4463, (1986) [11] Beck, C.; Roepstorff, G., Effects of phase space discretization on the long-time behavior of dynamical systems, Physica D, 25, 173-180, (1987) · Zbl 0617.65066 [12] Grebogi, C.; Hammel, S. M.; Yorke, J. A.; Sauer, T., Shadowing of physical trajectories in chaotic dynamics: Containment and refinement, Phys. Rev. Lett., 65, 1527-1530, (1990) · Zbl 1050.37521 [13] Earn, D. J. D.; Tremaine, S., Exact numerical studies of Hamiltonian maps: Iterating without roundoff error, Physica D, 56, 1-22, (1992) · Zbl 0759.58015 [14] Dawson, S.; Grebogi, C.; Sauer, T.; Yorke, J. A., Obstructions to shadowing when a Lyapunov exponent fluctuates about zero, Phys. Rev. Lett., 73, 1927-1930, (1994) [15] Diamond, P.; Kloeden, P.; Pokrovskii, A.; Vladimirov, A., Collapsing effects in numerical simulation of a class of chaotic dynamical systems and random mappings with a single attracting centre, Physica D, 86, 559-571, (1995) · Zbl 0878.60094 [16] Sauer, T.; Grebogi, C.; Yorke, J. A., How long do numerical chaotic solutions remain valid?, Phys. Rev. Lett., 79, 59-62, (1997) [17] Yuan, G.; Yorke, J. A., Collapsing of chaos in one dimensional maps, Physica D, 136, 18-30, (2000) · Zbl 0969.37037 [18] Saito, A., Computational aspects of a modified Bernoulli map, Prog. Theor. Phys. Suppl., 161, 328-331, (2006) [19] For a similar reason, there has also been no proposed pseudorandom number generator using chaotic orbits of the tent map on $$\left[0, 1\right]$$ given by $$M_T(x) = 1 - | 2 x - 1 |$$ or the baker’s transformation on $$[0, 1)^2$$ given by $$M_b(x, y) = \left\begin{cases} \left(2 x, \frac{y}{2}\right) & \text{ if } x \in \left[0, 1 / 2\right) \\ \left(2 x - 1, \frac{y + 1}{2}\right) & \text{ if} x \in \left[1 / 2, 1\right) \end{cases}\right.$$ although these maps, together with $$M_B$$, provide (literally) textbook examples of chaotic maps. [20] Saito, A.; Yamaguchi, A., Pseudorandom number generation using chaotic true orbits of the Bernoulli map, Chaos, 26, 063122, (2016) · Zbl 1422.65018 [21] Ulam, S. M.; von Neumann, J., On combination of stochastic and deterministic processes, Bull. Am. Math. Soc., 53, 1120, (1947) [22] Li, T. Y.; Yorke, J. A., Ergodic maps on $$[0, 1]$$ and nonlinear pseudo-random number generators, Nonlinear Anal., 2, 473-481, (1978) · Zbl 0407.28011 [23] Oishi, S.; Inoue, H., Pseudo-random number generators and chaos, Trans. IECE Jpn., E65, 534-541, (1982) [24] Lang, S.; Trotter, H., Continued fractions for some algebraic numbers, J. Reine Angew. Math., 255, 112-134, (1972) · Zbl 0237.10022 [25] Vivaldi, F., Dynamics over irreducible polynomials, Nonlinearity, 5, 941-960, (1992) · Zbl 0762.58020 [26] Lowenstein, J. H.; Poggiaspalla, G.; Vivaldi, F., Sticky orbits in a kicked-oscillator model, Dyn. Syst., 20, 413-451, (2005) · Zbl 1098.37066 [27] Akiyama, S., Finiteness and periodicity of beta expansions—number theoretical and dynamical open problems, Actes des rencontres du CIRM, 1, 3-9, (2009) · Zbl 06938550 [28] Furukado, M.; Ito, S.; Saito, A.; Tamura, J.; Yasutomi, S., A new multidimensional slow continued fraction algorithm and stepped surface, Exp. Math., 23, 390-410, (2014) · Zbl 1335.11055 [29] Saito, A.; Ito, S., Computation of true chaotic orbits using cubic irrationals, Physica D, 268, 100-105, (2014) · Zbl 1286.37042 [30] Saito, A.; Yasutomi, S.; Tamura, J.; Ito, S., True orbit simulation of piecewise linear and linear fractional maps of arbitrary dimension using algebraic numbers, Chaos, 25, 063103, (2015) [31] Hecke, E., Lectures on the Theory of Algebraic Numbers, (1981), Springer: Springer, New York [32] Borel, É., Sur les chiffres décimaux de $$\sqrt{2}$$ et divers problèmes de probabilités en chaîne, C. R. Acad. Sci. Paris, 230, 591-593, (1950) · Zbl 0035.08302 [33] Adamczewski, B.; Bugeaud, Y., On the complexity of algebraic numbers I. Expansions in integer bases, Ann. Math., 165, 547-565, (2007) · Zbl 1195.11094 [34] Marsaglia, G., The Marsaglia Random Number CDROM including the Diehard Battery of Tests of Randomness (1995), available at https://web.archive.org/web/20160125103112/http://stat.fsu.edu/pub/diehard/. [35] Rukhin, A., Soto, J., Nechvatal, J., Smid, M., Barker, E., Leigh, S., Levenson, M., Vangel, M., Banks, D., Heckert, A., Dray, J., and Vo, S., A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications, NIST Special Publication 800-22 Revision 1a (2010). [36] L’Ecuyer, P.; Simard, R., TestU01: A C library for empirical testing of random number generators, ACM Trans. Math. Softw., 33, 22, (2007) · Zbl 1365.65008 [37] Panneton, F.; L’Ecuyer, P.; Matsumoto, M., Improved long-period generators based on linear recurrences modulo 2, ACM Trans. Math. Softw., 32, 1-16, (2006) · Zbl 1346.94089 [38] Harase, S., On the $$\mathbb{F}_2$$-linear relations of Mersenne Twister pseudorandom number generators, Math. Comput. Simul., 100, 103-113, (2014) [39] Niederreiter, H., Factorization of polynomials and some linear-algebra problems over finite fields, Linear Algebra Appl., 192, 301-328, (1993) · Zbl 0845.11042 [40] Niederreiter, H., The multiple-recursive matrix method for pseudorandom number generation, Finite Fields Appl., 1, 3-30, (1995) · Zbl 0823.11041 [41] For initialization, we carried out the same procedure as the one adopted in the program available at .