# American Institute of Mathematical Sciences

January  2001, 7(1): 115-126. doi: 10.3934/dcds.2001.7.115

## An asymptotically perfect pseudorandom generator

 1 Instituto de Investigación en Communicación Optica, Universidad Autónoma de San Luis Potosí, 78000, San Luis Potosí, SLP, Mexico 2 Instituto de Investigación en Comunicación Optica, UASLP, Av. Karakorum 1470, Lomas 4ta sección, San Luis Potosí, SLP

Revised  August 2000 Published  November 2000

A transformation of binary sequences that is ergodic and mixing with respect to the equidistributed measure is constructed with the help of a cellular automaton. The transformation is the basic element for a pseudorandom number generator. The ratio of the number of seeds that generate equidistributed sequences to the number of all words goes to one as the length of words is increased. The evaluation of a hardware implementation of the generator confirms the statistical behavior of sequences as determined from the ergodic properties of the mathematical model of the generator. Unpredictability under random search attacks is attained by means of three coupled transformations.
Citation: Marcela Mejía, J. Urías. An asymptotically perfect pseudorandom generator. Discrete and Continuous Dynamical Systems, 2001, 7 (1) : 115-126. doi: 10.3934/dcds.2001.7.115
 [1] T.K. Subrahmonian Moothathu. Homogeneity of surjective cellular automata. Discrete and Continuous Dynamical Systems, 2005, 13 (1) : 195-202. doi: 10.3934/dcds.2005.13.195 [2] Achilles Beros, Monique Chyba, Oleksandr Markovichenko. Controlled cellular automata. Networks and Heterogeneous Media, 2019, 14 (1) : 1-22. doi: 10.3934/nhm.2019001 [3] Marcus Pivato. Invariant measures for bipermutative cellular automata. Discrete and Continuous Dynamical Systems, 2005, 12 (4) : 723-736. doi: 10.3934/dcds.2005.12.723 [4] Achilles Beros, Monique Chyba, Kari Noe. Co-evolving cellular automata for morphogenesis. Discrete and Continuous Dynamical Systems - B, 2019, 24 (5) : 2053-2071. doi: 10.3934/dcdsb.2019084 [5] Bernard Host, Alejandro Maass, Servet Martínez. Uniform Bernoulli measure in dynamics of permutative cellular automata with algebraic local rules. Discrete and Continuous Dynamical Systems, 2003, 9 (6) : 1423-1446. doi: 10.3934/dcds.2003.9.1423 [6] Marcelo Sobottka. Right-permutative cellular automata on topological Markov chains. Discrete and Continuous Dynamical Systems, 2008, 20 (4) : 1095-1109. doi: 10.3934/dcds.2008.20.1095 [7] Xinxin Tan, Shujuan Li, Sisi Liu, Zhiwei Zhao, Lisa Huang, Jiatai Gang. Dynamic simulation of a SEIQR-V epidemic model based on cellular automata. Numerical Algebra, Control and Optimization, 2015, 5 (4) : 327-337. doi: 10.3934/naco.2015.5.327 [8] Jon Chaika. Hausdorff dimension for ergodic measures of interval exchange transformations. Journal of Modern Dynamics, 2008, 2 (3) : 457-464. doi: 10.3934/jmd.2008.2.457 [9] Wen Huang, Leiye Xu, Shengnan Xu. Ergodic measures of intermediate entropy for affine transformations of nilmanifolds. Electronic Research Archive, 2021, 29 (4) : 2819-2827. doi: 10.3934/era.2021015 [10] Shrey Sanadhya. A shrinking target theorem for ergodic transformations of the unit interval. Discrete and Continuous Dynamical Systems, 2022, 42 (8) : 4003-4011. doi: 10.3934/dcds.2022042 [11] C. Kopf. Symbol sequences and entropy for piecewise monotone transformations with discontinuities. Discrete and Continuous Dynamical Systems, 2000, 6 (2) : 299-304. doi: 10.3934/dcds.2000.6.299 [12] Tanja Eisner, Jakub Konieczny. Automatic sequences as good weights for ergodic theorems. Discrete and Continuous Dynamical Systems, 2018, 38 (8) : 4087-4115. doi: 10.3934/dcds.2018178 [13] Zhixiong Chen, Vladimir Edemskiy, Pinhui Ke, Chenhuang Wu. On $k$-error linear complexity of pseudorandom binary sequences derived from Euler quotients. Advances in Mathematics of Communications, 2018, 12 (4) : 805-816. doi: 10.3934/amc.2018047 [14] Huaning Liu, Yixin Ren. On the pseudorandom properties of $k$-ary Sidel'nikov sequences. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021038 [15] Julia Brettschneider. On uniform convergence in ergodic theorems for a class of skew product transformations. Discrete and Continuous Dynamical Systems, 2011, 29 (3) : 873-891. doi: 10.3934/dcds.2011.29.873 [16] Akinori Awazu. Input-dependent wave propagations in asymmetric cellular automata: Possible behaviors of feed-forward loop in biological reaction network. Mathematical Biosciences & Engineering, 2008, 5 (3) : 419-427. doi: 10.3934/mbe.2008.5.419 [17] Prof. Dr.rer.nat Widodo. Topological entropy of shift function on the sequences space induced by expanding piecewise linear transformations. Discrete and Continuous Dynamical Systems, 2002, 8 (1) : 191-208. doi: 10.3934/dcds.2002.8.191 [18] Oliver Jenkinson. Ergodic Optimization. Discrete and Continuous Dynamical Systems, 2006, 15 (1) : 197-224. doi: 10.3934/dcds.2006.15.197 [19] Alina Ostafe, Igor E. Shparlinski, Arne Winterhof. On the generalized joint linear complexity profile of a class of nonlinear pseudorandom multisequences. Advances in Mathematics of Communications, 2010, 4 (3) : 369-379. doi: 10.3934/amc.2010.4.369 [20] Petr Kůrka. On the measure attractor of a cellular automaton. Conference Publications, 2005, 2005 (Special) : 524-535. doi: 10.3934/proc.2005.2005.524

2021 Impact Factor: 1.588