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


УДК 004.056

ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ НА ОСНОВЕ КЛЕТОЧНЫХ АВТОМАТОВ

Мухамеджанов Д.Д., Левина А.Б.


Читать статью полностью 
Язык статьи - русский

Ссылка для цитирования:
Мухамеджанов Д.Д., Левина А.Б. Генератор псевдослучайных чисел на основе клеточных автоматов // Научно-технический вестник информационных технологий, механики и оптики. 2018. Т. 18. № 5. С. 894–900. doi: 10.17586/2226-1494-2018-18-5-894-900


Аннотация
Предмет исследования.Разработан алгоритм генерации псевдослучайных чисел, основанный на свойствах клеточных автоматов. Клеточные автоматы имеют большой потенциал, обладают высокой скоростью вычислений, особенно при реализации в параллельной архитектуре. Метод. В представленном алгоритме псевдослучайные числа генерируются с помощью правил переходов в ячейках клеточного автомата в зависимости от шаблонов соседства и выходных данных ячеек «соседей». Через несколько переходов по выбору методики генерирования получается последовательность псевдослучайных чисел из нулей и единиц. Основные результаты. Разработанный алгоритм протестирован на NIST-тестах. Результаты тестирования показали, что алгоритм производит последовательность с равномерным распределением с вероятностью 99–100%. На NIST-тестах проведено сравнение предложенного алгоритма с линейно конгруэнтным методом – основным методом генерации псевдослучайных чисел в настоящее время. По всем тестам разработанный генератор псевдослучайных чисел показал лучшие результаты. Алгоритм обладает высокой скоростью и легкостью реализации, а также возможностью масштабирования. Практическая значимость. Генератор может использоваться в различных приложениях, таких как теория кодирования или легковесная криптография. Достигается криптографическая стойкость при испытаниях по стандартным методикам оценивания качества генератора псевдослучайных чисел.

Ключевые слова: криптография, генератор псевдослучайных чисел, клеточные автоматы, однородные структуры, NIST, случайные числа

Список литературы
  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. V. 49. N 10. P. 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. V. 1. N 2.
    P. 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. V. 16. N 2-3. P. 291–305. doi: 10.1016/s0167-739x(99)00053-9
  6. Wolfram S. Random sequence generation by cellular automata // Advances in Applied Mathematics. 1986. V. 7. N 2.
    P. 123–169.
  7. Gardner M. The fantastic combinations of John Conway’s new solitaire game "Life" // Scientific American. 1970. V. 223. P. 120–123.
  8. Кудрявцев В.Б., Подколзин А.С. Клеточные автоматы // Интеллектуальные системы. 2006. Т. 10. № 1-4. С. 657–692.
  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. Наумов Л.А., Шалыто А.А. Клеточные автоматы. Реализация и эксперименты // Мир ПК. 2003. № 8. С. 64–71.
  11. Астафьев Г.Б., Короновский А.А., Храмов А.Е. Клеточные автоматы. Саратов: Центр «Колледж», 2003.24 с.
  12. Жуков А.Е. Клеточные автоматы в криптографии. Часть 2 // Вопросы кибербезопасности. 2017. № 4(22). С. 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. P. 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. V. 5457. P. 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. P. 485–557.


Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
Информация 2001-2024 ©
Научно-технический вестник информационных технологий, механики и оптики.
Все права защищены.

Яндекс.Метрика