Menu
Publications
2024
2023
2022
2021
2020
2019
2018
2017
2016
2015
2014
2013
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
Editor-in-Chief
Nikiforov
Vladimir O.
D.Sc., Prof.
Partners
doi: 10.17586/2226-1494-2018-18-5-894-900
PSEUDORANDOM NUMBER GENERATOR ON CELLULAR AUTOMATA
Read the full article
';
Article in Russian
For citation:
Abstract
For citation:
Mukhamedjanov D.D., Levina A.B. Pseudorandom number generator on cellular automata. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2018, vol. 18, no. 5, pp. 894–900 (in Russian). doi: 10.17586/2226-1494-2018-18-5-894-900
Abstract
Subject of Research. The paper presents an algorithm for pseudorandom number generationbased on properties of cellular automata. Cellular automata have high potential, high speed of calculations, especially at realization in parallel architecture. Method. In the presented algorithm pseudorandom numbers are generated by means of rules of transitions in cells of the cellular automaton depending on templates of the neighborhood and the output data of cells of "neighbors". Through several transitions at the choice of a generation technique the sequence of pseudorandom numbers turns out from zeroes and units. Main Results. The developed algorithm is tested on NIST-tests. The results of testing have shown that the algorithm makes the sequence with uniform distribution with probability of 99-100%. Comparison of the proposed algorithm with linearly congruent method, the main up-to-date method of generation of pseudorandom numbers, is carried out on NIST-tests. According to all tests the developed generator of pseudorandom numbers has shown the best results. The algorithm has the high speed, easy realization and also scaling possibility. Practical Relevance. The generator can be used in various applications, such as the theory of coding or lightweight cryptography. The cryptographic firmness is reached at tests by standard quality estimation techniques for the generator of pseudorandom numbers.
Keywords: cryptography, pseudorandom number generator, cellular automata, homogenous structures, NIST, random numbers
References
References
-
Rukhin A. et al. A statistical test suite for random and pseudorandom number generators for cryptographic applications. NIST Special Publication 800-22, 2001, 152 p.
-
Tomassini M., Sipper M., Perrenoud M. On the generation of high-quality random numbers by two-dimensional cellular automata. IEEE Transactions on Computers, 2000, vol. 49, no. 10, pp. 1146–1151. doi: 10.1109/12.888056
-
Ilachinski A. Cellular Automata: A Discrete Universe. World Scientific Publishing Company, 2001, 840 p. doi: 10.1142/4702
-
Tomassini M., Perrenoud M. Cryptography with cellular automata. Applied Soft Computing, 2001, vol. 1, no. 2, pp. 151–160. doi: 10.1016/s1568-4946(01)00015-1
-
Tomassini M., Sipper M., Zolla M., Perrenoud M. Generating high-quality random numbers in parallel by cellular automata. Future Generation Computer Systems, 1999, vol. 16, no. 2-3, pp. 291–305. doi: 10.1016/s0167-739x(99)00053-9
-
Wolfram S. Random sequence generation by cellular automata. Advances in Applied Mathematics, 1986, vol. 7, no. 2, pp. 123–169.
-
Gardner M. The fantastic combinations of John Conway’s new solitaire game "Life". Scientific American, 1970, vol. 223,pp. 120–123.
-
Kudryavtsev V.B., Podkolzin A.S. Cellular automata. Intellektual'nye Sistemy, 2006, vol. 10, no. 4, pp. 657–692. (in Russian)
-
Tomassini M. Spatially Structured Evolutionary Algorithms: Artificial Evolution in Space and Time. Springer, 2005, 193 p. doi: 10.1007/3-540-29938-6
-
Naumov L.A., Shalyto A.A. Cellular automata. Implementation and experiments. Mir PK, 2003, no. 8,
pp. 64–71. (in Russian) -
Astaf'ev G.B., Koronovskii A.A., Khramov A.E. Cellular Automata. Saratov, Kolledzh Publ., 2003, 24 p. (in Russian)
-
Zhukov A.E. Cellular automata in cryptography. Part 2. Cybersecurity Issues, 2017, no. 4, pp. 47–66. doi: 10.21681/2311-3456-2017-4-47-66
-
Moore E.F. Gedanken-experiments on sequential machines. In: Automata Studies. Eds. C.E. Shannon, J. McCarthy. Princeton University Press, 1956,pp. 129–154. doi: 10.1515/9781400882618-006
-
Aspray W. John von Neumann and the Origins of Modern Computing. MIT Press, 1990, 376 p.
-
Cattaneo G., Dennunzio A., Formenti E., Provillard E. Non-uniform cellular automata. Lecture Notes in Computer Science, 2009, vol. 5457, pp. 302–313. doi: 10.1007/978-3-642-00982-2_26
-
Wolfram S. Tables of cellular automaton properties. In Theory and Applications of Cellular Automata (Including Selected Papers 1983–1986). World Scientific Publ., 1986, pp. 485–557.
