IMPLEMENTATION AND STUDY OF THE RANDOM NUMBER GENERATOR BASED ON PARALLEL MIXING
Abstract
The use of random number generators is widespread. Software generators usually produce
pseudo-random numbers. To improve characteristics, it needs a source of "chaos". This article
discusses the implementation of a random number generator that uses the idea of mixing a complete
set of numbers in a parallel thread. The operation of the processor in this mode is influenced by many random factors, which allows issuing random numbers. For the proposed generator, each
subsequent number does not depend on the previous one. The generator can give out any number
of the given range, regardless of how many and what numbers fell out earlier. Including the same
number can fall out with a low probability several times in a row. There is no predetermined sequence
of issuing random numbers. The period inherent in software pseudo-random number generators
is also missing. However, at the same time, the speed of issuing random numbers decreases,
in comparison with software pseudo-random number generators. The purpose of research was
to evaluate the properties of the proposed generator, primarily the statistical characteristics of the
generated numbers. The article deals with the idea of parallel mixing. Implementation issues in a
programming language. The programming interface of the MixRandomBase class and implementation
features of the MixRandomByte class, which uses a working array of bytes, are presented.
Various tests are used to check the quality of the work of random and pseudo-random number
generators. The results of checking the operation of the generator by such tests as the distribution
on the plane, the uniformity test, the “stack of books” test are given. The test results make it possible
to judge the good statistical characteristics of the developed generator. The speed of the generator
is estimated. In comparison with linear congruent pseudo-random number generators, the
time for issuing a sequence of numbers is hundreds of times longer.
References
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.
