РЕАЛИЗАЦИЯ И ИССЛЕДОВАНИЕ ГЕНЕРАТОРА СЛУЧАЙНЫХ ЧИСЕЛ НА ОСНОВЕ ПАРАЛЛЕЛЬНОГО ПЕРЕМЕШИВАНИЯ

  • Н.В. Драгныш Южный федеральный университет
Ключевые слова: Генератор случайных чисел, перемешивание случайных чисел, параллельное программирование, тесты генераторов случайных чисел

Аннотация

Использование генераторов случайных чисел находит широкое распространение.
Программные генераторы как правило выдают псевдослучайные числа. Для улучшения ха-
рактеристик, необходим источник “хаоса”. В данной статье рассматривается реализа-
ция генератора случайных чисел, использующего идею перемешивания полного набора чисел
в параллельном потоке. На работу процессора в таком режиме оказывают влияние мно-
жество случайных факторов, что позволяет выдавать случайные числа. У предложенного
генератора каждое последующее число не зависит от предыдущего. Генератор может
выдать любое число заданного диапазона, несмотря на то сколько и какие числа выпадали
ранее. В том числе может выпасть с малой вероятностью одно и тоже число несколько
раз подряд. Отсутствует заранее определенная последовательность выдачи случайных
чисел. Период, свойственный программным генераторам псевдослучайных чисел, также
отсутствует. Но при этом снижается быстродействие выдачи случайных чисел, в срав-
нении с программными генераторами псевдослучайных чисел. Целью исследования было
оценить свойства предложенного генератора, в первую очередь статистические характе-
ристики генерируемых чисел. В статье рассмотрены вопросы идеи параллельного переме-
шивания. Вопросы реализации на языке программирования. Представлен программный ин-
терфейс класса MixRandomBase и особенности реализации класса MixRandomByte, исполь-
зующего рабочий массив из байтов. Для проверки качества работы генераторов случайных
и псевдослучайных чисел применяют различные тесты. Приведены результаты проверки
работы генератора такими тестами как распределение на плоскости, тест равномерно-
сти, тест “стопка книг”. Результаты тестирования позволяют судить о хороших ста-
тистических характеристиках разработанного генератора. Оценено быстродействие
генератора. В сравнении с линейными конгруэнтными генераторами псевдослучайных чи-
сел время выдачи последовательности чисел больше в сотни раз.

Литература

1. Kel'ton V. Lou A. Imitatsionnoe modelirovanie. Klassika CS [Simulation modeling. CS classic].
Saint Petersburg: Piter; Kiev: Izdatel'skaya gruppa BHV, 2004, 847 p.
2. Dragnysh N.V. Ispol'zovanie metodov imitatsionnogo modelirovaniya dlya prepodavaniya
kursa «Teoriya veroyatnostey i matematicheskaya statistika» [The use of simulation methods
for teaching the course "Probability Theory and Mathematical Statistics"], Aktual'nye
problemy gumanitarnykh i estestvennykh nauk [Actual problems of the humanities and natural
sciences], 2011, No. 12, pp. 26-29.
3. Dragnysh N.V. Ispol'zovanie innovatsionnykh tekhnologiy dlya prepodavaniya kursa "Teoriya
veroyatnostey i matematicheskaya statistika"[The use of innovative technologies for teaching the course
"Probability Theory and Mathematical Statistics"], Diskussiya [Discussion], 2010, No. 8, pp. 80-83.
4. Knut D.E. Iskusstvo programmirovaniya. T. 2: Poluchislennye algoritmy [The art of programming.
Vol. 2: Obtained algorithms]. Moscow: Izd. dom “Vil'yams”, 2019, 832 p.
5. Ivanov M.A., Chugunkov I.V. Teoriya, primenenie i otsenka kachestva generatorov
psevdosluchaynykh posledovatele'nostey [Theory, application and evaluation of the quality of
generators of pseudo-random sequences]. Moscow: KUDITS-OBRAZ, 2003, 240 p.
6. L’Ecuyer P. Tables of linear congruential generators of different sizes and good lattice structure,
Math. of Comp., 1999, Vol. 68, pp. 249-260.
7. Podorozhnyy I.V. Obzor apparatnykh generatorov sluchaynykh chisel [Overview of hardware random
number generators], Molodoy uchenyy [Young scientist], 2016, No. 1 (105), pp. 190-194.
8. Zadkov V.N., Vladimirova Yu.V. Klassicheskie i kvantovye generatory sluchaynykh chisel
[Classical and quantum random number generators], Superkomp'yutery [Supercomputers],
2013, No. 2, pp. 12-20.
9. Recommendation for Random Number Generation Using Deterministic Random Bit Generators.
Available at: http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-90Ar1.pdf
(accessed 05 November 2022).
10. Recommendation for the Entropy Sources Used for Random Bit Generation. Available at:
http://csrc.nist.gov/publications/drafts/800-90/sp800-90b_second_draft.pdf (accessed 05 November
2022).
11. Recommendation for Random Bit Generator (RBG) Constructions. Available at:
http://csrc.nist.gov/publications/drafts/800-90/draft-sp800-90c.pdf (accessed 05 November 2022).
12. Dragnysh N.V. Postroenie generatora sluchaynykh chisel na osnove parallel'nogo
peremeshivaniya [Building a random number generator based on parallel mixing], Nauka,
tekhnika i obrazovanie [Science, technology and education], 2015, No. 6 (12), pp. 12-14.
13. Grigor'ev A.Yu. Metody testirovaniya generatorov sluchaynykh i psevdosluchaynykh
posledovatel'nostey [Methods for testing generators of random and pseudo-random sequences],
Uchenye zapiski UlGU. Ser. Matematika i informatsionnye tekhnologii [Uchenye zapiski UlGU.
Ser. Mathematics and Information Technology. UlGU. Electron. Magazine], 2017, No. 1, pp. 22-28.
14. NIST Statistical Test Suite. Available at: http://csrc.nist.gov/groups/ST/toolkit/rng/documentation_
software.html (accessed 05 November 2022).
15. Rukhin A. and others. A Statistical Test Suite for Random and Pseudorandom Number Generators
for Cryptographic Applications. NIST Special Publication 800-22 (with revisions dated
May 15, 2001) NIST Statistical Test Suite. Available at: http://csrc.nist.gov/groups/ST/toolkit/
rng/documentation_software.html (accessed 05 November 2022).
16. R 50.1.033–2001. Rekomendatsii po standartizatsii. Prikladnaya statistika. Pravila proverki
soglasiya opytnogo raspredeleniya s teoreticheskim. Ch. I. Kriterii tipa khi-kvadrat
[R 50.1.033–2001. Recommendations for standardization. Applied Statistics. Rules for checking
the agreement between the experimental distribution and the theoretical one. Part I. Chisquare
tests]. Moscow: Izd-vo standartov. 2002, 87 p.
17. Ryabko B.Ya., Pestunov A.I. “Stopka knig” kak novyy statisticheskiy test dlya sluchaynykh
chisel [“Pack of books” as a new statistical test for random numbers], Problemy peredachi
informatsii [Problems. transfer of information], 2004, Vol. 40, Issue 1, pp. 73-78.
18. Pestunov A.I. Teoreticheskoe issledovanie svoystv statisticheskogo testa “stopka knig” [Theoretical
study of the properties of the "stack of books" statistical test], Vychislitel'nye
tekhnologii [Computational technologies], 2006, Vol. 11, No. 6, pp. 96-103.
19. Minenko A.I. Eksperimental'noe issledovanie effektivnosti testov dlya proverki generatorov
sluchaynykh chisel [Experimental study of the effectiveness of tests for testing random number
generators], Vestnik SibGUT [Vestnik SibSUTI], 2010, No. 4, pp. 36-46.
20. Ryabko B., Monarev V. Using information theory approach for randomness testing, J. of Statistical
Planning and Reference, 2005, Vol. 133, No. 1, pp. 95-110.
21. Ryabko B., Stognienko V., Shokin Yu. A new test for randomness and its application to some cryptographic
problems, J. of Statistical Planning and Reference, 2004, Vol. 123, No. 2, pp. 365-376.
Опубликован
2022-12-27
Выпуск
Раздел
РАЗДЕЛ I. МОДЕЛИ И МЕТОДЫ ОБРАБОТКИ ИНФОРМАЦИИ