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 & Continuous Dynamical Systems - A, 2001, 7 (1) : 115-126. doi: 10.3934/dcds.2001.7.115
[1]

T.K. Subrahmonian Moothathu. Homogeneity of surjective cellular automata. Discrete & Continuous Dynamical Systems - A, 2005, 13 (1) : 195-202. doi: 10.3934/dcds.2005.13.195

[2]

Marcus Pivato. Invariant measures for bipermutative cellular automata. Discrete & Continuous Dynamical Systems - A, 2005, 12 (4) : 723-736. doi: 10.3934/dcds.2005.12.723

[3]

Bernard Host, Alejandro Maass, Servet Martínez. Uniform Bernoulli measure in dynamics of permutative cellular automata with algebraic local rules. Discrete & Continuous Dynamical Systems - A, 2003, 9 (6) : 1423-1446. doi: 10.3934/dcds.2003.9.1423

[4]

Marcelo Sobottka. Right-permutative cellular automata on topological Markov chains. Discrete & Continuous Dynamical Systems - A, 2008, 20 (4) : 1095-1109. doi: 10.3934/dcds.2008.20.1095

[5]

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 & Optimization, 2015, 5 (4) : 327-337. doi: 10.3934/naco.2015.5.327

[6]

Tanja Eisner, Jakub Konieczny. Automatic sequences as good weights for ergodic theorems. Discrete & Continuous Dynamical Systems - A, 2018, 38 (8) : 4087-4115. doi: 10.3934/dcds.2018178

[7]

C. Kopf. Symbol sequences and entropy for piecewise monotone transformations with discontinuities. Discrete & Continuous Dynamical Systems - A, 2000, 6 (2) : 299-304. doi: 10.3934/dcds.2000.6.299

[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]

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

[10]

Julia Brettschneider. On uniform convergence in ergodic theorems for a class of skew product transformations. Discrete & Continuous Dynamical Systems - A, 2011, 29 (3) : 873-891. doi: 10.3934/dcds.2011.29.873

[11]

Prof. Dr.rer.nat Widodo. Topological entropy of shift function on the sequences space induced by expanding piecewise linear transformations. Discrete & Continuous Dynamical Systems - A, 2002, 8 (1) : 191-208. doi: 10.3934/dcds.2002.8.191

[12]

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

[13]

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

[14]

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

[15]

Oliver Penrose, John W. Cahn. On the mathematical modelling of cellular (discontinuous) precipitation. Discrete & Continuous Dynamical Systems - A, 2017, 37 (2) : 963-982. doi: 10.3934/dcds.2017040

[16]

Eduardo Ibarguen-Mondragon, Lourdes Esteva, Leslie Chávez-Galán. A mathematical model for cellular immunology of tuberculosis. Mathematical Biosciences & Engineering, 2011, 8 (4) : 973-986. doi: 10.3934/mbe.2011.8.973

[17]

Frank Fiedler. Small Golay sequences. Advances in Mathematics of Communications, 2013, 7 (4) : 379-407. doi: 10.3934/amc.2013.7.379

[18]

E. Camouzis, H. Kollias, I. Leventides. Stable manifold market sequences. Journal of Dynamics & Games, 2018, 5 (2) : 165-185. doi: 10.3934/jdg.2018010

[19]

Ryszard Rudnicki. An ergodic theory approach to chaos. Discrete & Continuous Dynamical Systems - A, 2015, 35 (2) : 757-770. doi: 10.3934/dcds.2015.35.757

[20]

Roy Adler, Bruce Kitchens, Michael Shub. Stably ergodic skew products. Discrete & Continuous Dynamical Systems - A, 1996, 2 (3) : 349-350. doi: 10.3934/dcds.1996.2.349

2016 Impact Factor: 1.099

Metrics

  • PDF downloads (3)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]