American Institute of Mathematical Sciences

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

An asymptotically perfect pseudorandom generator

Marcela Mejía 1, and  J. Urías 2,

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.
Keywords: pseudorandom sequences., Cellular automata, ergodic transformations.
Mathematics Subject Classification: 37N9.
Citation: Marcela Mejía, J. Urías. An asymptotically perfect pseudorandom generator. Discrete & 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 & 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 & Heterogeneous Media, 2019, 14 (1) : 1-22. doi: 10.3934/nhm.2019001
[3]

Marcus Pivato. Invariant measures for bipermutative cellular automata. Discrete & 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 & 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 & 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 & 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 & 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]

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

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

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

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

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

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

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

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

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

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

Sarah Bailey Frick. Limited scope adic transformations. Discrete & Continuous Dynamical Systems - S, 2009, 2 (2) : 269-285. doi: 10.3934/dcdss.2009.2.269

2020 Impact Factor: 1.392

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences