doi: 10.17586/2226-1494-2018-18-5-894-900


D. D. Mukhamedjanov, A. B. Levina

Read the full article  ';
Article in Russian

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

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

  1. 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.
  2. 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
  3. Ilachinski A. Cellular Automata: A Discrete Universe. World Scientific Publishing Company, 2001, 840 p. doi: 10.1142/4702
  4. 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
  5. 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
  6. Wolfram S. Random sequence generation by cellular automata. Advances in Applied Mathematics, 1986, vol. 7, no. 2, pp. 123–169.
  7. Gardner M. The fantastic combinations of John Conway’s new solitaire game "Life". Scientific American, 1970, vol. 223,pp. 120–123.
  8. Kudryavtsev V.B., Podkolzin A.S. Cellular automata. Intellektual'nye Sistemy, 2006, vol. 10, no. 4, pp. 657–692. (in Russian)
  9. Tomassini M. Spatially Structured Evolutionary Algorithms: Artificial Evolution in Space and Time. Springer, 2005, 193 p. doi: 10.1007/3-540-29938-6
  10. Naumov L.A., Shalyto A.A. Cellular automata. Implementation and experiments. Mir PK, 2003, no. 8,
    pp. 64–71. (in Russian)
  11. Astaf'ev G.B., Koronovskii A.A., Khramov A.E. Cellular Automata. Saratov, Kolledzh Publ., 2003, 24 p. (in Russian)
  12. 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
  13. 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
  14. Aspray W. John von Neumann and the Origins of Modern Computing. MIT Press, 1990, 376 p.
  15. 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
  16. 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.

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
Copyright 2001-2021 ©
Scientific and Technical Journal
of Information Technologies, Mechanics and Optics.
All rights reserved.