×

zbMATH — the first resource for mathematics

Random number generation using decimal cellular automata. (English) Zbl 07264504
Summary: This paper illustrates the potentiality of decimal CAs as source of pseudo-randomness. Some desirable properties for a CA to be a good source of pseudo-randomness are identified. As the rule space is huge, greedy strategies are taken to select CAs satisfying these properties. Finally, two heuristic algorithms are given to synthesize such CAs. As application of pseudo-randomness, two schemes are reported to develop pseudo-random number generators (PRNGs) using these CAs. To generate a number from a configuration, we have used the concept of window. It is observed that, our PRNGs are at least as good as the best known PRNGs existing in literature.
MSC:
68Q Theory of computing
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Wolfram, S., Origins of randomness in physical systems, Phys Rev Lett, 55, 449-452 (1985)
[2] Kurka, P., Languages, equicontinuity and attractors in cellular automata, Ergodic Theory Dynam Syst, 17, 02, 417-433 (1997) · Zbl 0876.68075
[3] Kamilya, S.; Das, S., A study of chaos in cellular automata, Int J Bifurcat Chaos, 28, 03, 1830008 (2018) · Zbl 1387.37018
[4] Hortensius, P. D.; Leod, R. D.M.; Pries, W.; Miller, D. M.; Card, H. C., Cellular automata-based pseudorandom number generators for built-in self-test, IEEE Trans Comput Aided Des Integr Circuit Syst, 8, 8, 842-859 (1989)
[5] Chaudhuri, P. P.; Chowdhury, D. R.; Nandi, S.; Chattopadhyay, S., Additive cellular automata – theory and applications, vol. 1 (1997), IEEE computer society press: IEEE computer society press USA
[6] Das, S.; Dey, D.; Sen, S.; Sikdar, B. K.; Chaudhuri, P. P., An efficient design of non-linear CA based PRPG for VLSI circuit testing, Proceedings of the asia and south pacific design automation conference, 110-112 (2004)
[7] Das, S.; Sikdar, B. K., A scalable test structure for multicore chip, IEEE Trans Comput Aided Des Integr Circuit Syst, 29, 1, 127-137 (2010)
[8] Sipper, M.; Tomassini, M., Generating parallel random number generators by cellular programming, Int J Modern Phys C, 7, 2, 180-190 (1996)
[10] Bhattacharjee, K.; Paul, D.; Das, S., Pseudo-random number generation using a 3-state cellular automaton, Int J Modern Phys C, 28, 06, 1750078 (2017)
[11] Bhattacharjee, K.; Das, S., A list of tri-state cellular automata which are potential pseudo-random number generators, Int J Modern Phys C, 29, 09, 1850088 (2018)
[12] L’Ecuyer, P.; Simard, R., TestU01: A C library for empirical testing of random number generators, ACM Trans Math Software, 33, 4 (2007) · Zbl 1365.65008
[13] Knuth, D. E., The art of computer programming – seminumerical algorithms (2000), Pearson Education
[15] Soto, J., Statistical testing of random number generators, Proceedings of the 22nd national information systems security conference, Vol. 10, 12 (1999), NIST: NIST Gaithersburg, MD
[16] Vattulainen, I.; Ala-Nissila, T.; Kankaala, K., Physical models as tests of randomness, Phys Rev E, 52, 3205-3214 (1995) · Zbl 0873.65004
[17] Rukhin, A.; Soto, J.; Nechvatal, J.; Smid, M.; Barker, E., A statistical test suite for random and pseudorandom number generators for cryptographic applications, Tech rep, DTIC Document (2001)
[18] Meier, W.; Staffelbach, O., Nonlinearity criteria for cryptographic functions (1990), Springer: Springer Berlin Heidelberg · Zbl 0724.94009
[19] Kamilya, S.; Das, S., A study of chaos in non-uniform cellular automata, Commun Nonlinear Sci Numer Simul, 76, 116-131 (2019)
[20] Bhattacharjee, K.; Das, S., Reversibility of \(d\)-state finite cellular automata, J Cell Autom, 11, 2-3, 213-245 (2016)
[22] Cattaneo, G.; Formenti, E.; Margara, L.; Mauri, G., On the dynamical behavior of chaotic cellular automata, Theor Comput Sci, 217, 1, 31-51 (1999) · Zbl 0933.68096
[23] Kůrka, P., Topological dynamics of cellular automata (2009), Springer: Springer New York
[24] Sutner, K., On the computational complexity of finite cellular automata, J Comput Syst Sci, 50, 1, 87-97 (1995) · Zbl 0827.68078
[25] Hazari, R.; Das, S., Number conservation property of elementary cellular automata under asynchronous update, Complex Syst, 23, 177-195 (2014) · Zbl 1357.68121
[26] Tiernan, J. C., An efficient search algorithm to find the elementary circuits of a graph, Commun ACM, 13, 12, 722-726 (1970) · Zbl 0225.94027
[27] Tarjan, R., Enumeration of the elementary circuits of a directed graph, SIAM J Comput, 2, 3, 211-216 (1973) · Zbl 0274.05106
[29] Johnson, D. B., Finding all the elementary circuits of a directed graph, SIAM J Comput, 4, 1, 77-84 (1975) · Zbl 0275.05112
[30] Wolfram, S., Random sequence generation by cellular automata, Adv Appl Math, 7, 2, 123-169 (1986) · Zbl 0603.68053
[32] L’Ecuyer, P.; Touzin, R., Fast combined multiple recursive generators with multipliers of the form \(a = \pm 2^q \pm 2^r\), Proceedings of the 32nd conference on winter simulation, 683-689 (2000)
[34] L’ecuyer, P., Maximally equidistributed combined tausworthe generators, Math Comput, 65, 213, 203-213 (1996) · Zbl 0853.65007
[36] Marsaglia, G., Xorshift RNGs, J Stat Softw, 8, 14, 1-6 (2003)
[37] Vigna, S., An experimental exploration of Marsaglia’s Xorshift generators, scrambled, ACM Trans Math Softw, 42, 4 (2016) · Zbl 1369.65009
[38] Matsumoto, M.; Nishimura, T., Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator, ACM Trans Model Comput Simul, 8, 1, 3-30 (1998) · Zbl 0917.65005
[39] Saito, M.; Matsumoto, M., SIMD-Oriented fast Mersenne Twister: a 128-bit Pseudorandom number generator, 7th international conference on Monte Carlo and Quasi-Monte Carlo methods in scientific computing, 607-622 (2008), Springer: Springer Berlin Heidelberg · Zbl 1141.65319
[40] Saito, M.; Matsumoto, M., A PRNG specialized in double precision floating point numbers using an affine transition, 8th international conference on Monte Carlo and Quasi-Monte Carlo methods in scientific computing, 589-602 (2009), Springer: Springer Berlin Heidelberg · Zbl 1184.65013
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.