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

Мухамеджанов Данияр Давлетович, Левина А.Б.

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

2018 , ТОМ 18, НОМЕР 5 ( сентябрь-октябрь )

ISSN 2226-1494 (print), ISSN 2500-0373 (online)

Меню

Публикации

Главный редактор

НИКИФОРОВ
Владимир Олегович
д.т.н., профессор

Партнеры

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, случайные числа

Список литературы

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

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License