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

An asymptotically perfect pseudorandom generator


Instituto de Investigación en Communicación Optica, Universidad Autónoma de San Luis Potosí, 78000, San Luis Potosí, SLP, Mexico


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

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


Achilles Beros, Monique Chyba, Oleksandr Markovichenko. Controlled cellular automata. Networks and Heterogeneous Media, 2019, 14 (1) : 1-22. doi: 10.3934/nhm.2019001


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


Oliver Jenkinson. Ergodic Optimization. Discrete and Continuous Dynamical Systems, 2006, 15 (1) : 197-224. doi: 10.3934/dcds.2006.15.197


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


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


  • PDF downloads (69)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]