МЕТОДИ ВИБОРУ ГЕНЕРАТОРА ВИПАДКОВИХ ЧИСЕЛ ДЛЯ МОДЕЛЮВАННЯ СТОХАСТИЧНИХ ПРОЦЕСІВ
DOI:
https://doi.org/10.18372/2225-5036.30.18613Ключові слова:
моделювання, лінійний конгруентний генератор, генератор Вихор Мерсенна, Xorshift генератор, метод зворотної функції, метод Монте-Карло, критерій хі-квадрат Пірсона, постоброблення числового потоку, алгоритм, метод, персональні дані, особиста інформація, фазовий портрет, нелінійна система, стійкість, запізнення, конфіденційність, прогнозування, інформаційні технологіїАнотація
Сучасне комп'ютерне моделювання – це важливий етап проектування систем управління розподіленням інформаційних потоків в обчислювальних мережах та у сучасних системах управління складними технологічних процесами. Ядром будь-якої комп’ютерної моделі є джерело випадковості, яке повинно формувати рівномірно розподілений потік випадкових цілих або дійсних чисел. Крім рівномірності розподілення, таке джерело повинно задовольняти вимогам економічного використання ресурсів обчислювальної системи. Наведено аналіз простих арифметичних генераторів і, на його основі, показано, що у якості генератора для потреб моделювання стохастичних процесів підходять такі генератори, як генератор послідовності Фібоначчі з запізненням та запропонований Дж. Марсальєю генератор Xorshift, які є альтернативою генераторам випадкових чисел, вбудованих в існуючі середовища програмування. На основі проведених досліджень зроблено висновок про те, що будь-яка нерівномірність чисел на виході генератора, обраного у якості джерела випадковості, суттєво впливає на якість процесу, який підлягає моделюванню, і, через це, числові потоки від таких генераторів мають бути додатково оброблені методами екстракції тої їх частини, яка забезпечує максимальну випадковість. Наведено методику виконання такої екстракції шляхом “проріжування” вхідного потоку, критерії, які при цьому використовуються, та результати його експериментального дослідження для генератора Xorshift128. Зроблено висновок про переваги використання простих і економічних генераторів в купі з процедурами постоброблення, що виконується на рівні цілих або дійсних чисел. Наведено результати оцінки роботи Xorshift генератора з урахування описаних в роботі методик та зроблено висновок про доцільність його використання для потреб моделювання стохастичних процесів.
Посилання
Smile Markovski, Danilo Gligoroski, Ljupco Kocarev. Unbiased Random Sequences from Qua-sigroup String Transformations. Part of the Lecture Notes in Computer Science book series (LNSC, volume 3557). URL: https:// www.iacr.org /archive/fse2005/35570161 /355¬70161.pdf.
Dichtl, M.: Bad and good ways of post-processing biased physical random numbers. In: Biryu-kov, A. (ed.) FSE 2007. LNCS, vol. 4593, pp. 127-152. Springer, Heidelberg (2007) URL: https://link.springer.com/content/pdf/10.1007/978-3-540-74619-5_9.pdf.
Smile Markovski, Danilo Gligoroski Ljupco Kocarev. Unbiased Random Sequences from Qua-sigroup String Transformations. International Work-shop on Fast Software Encryption FSE 2005: Fast Soft-ware Encryption pp 163-180 URL: https://www.iacr.org/archive/fse2005 /35570161/35570161.pdf.
Makoto Matsumoto and Takuji Nishimura. 1998. Mersenne Twister: A 623-dimensionally Equidis-tributed Uniform Pseudo-Random Number Generator. ACM Trans. Model. Comput. Simul. 8, 1 (Jan. 1998), 3-30. https://doi.org/10.1145/272991.272995 URL: https://dl. acm.org/doi/pdf/10.1145/272991.272995.
François Panneton and Pierre L’Ecuyer. 2005. On the Xorshift Random Number Generators. ACM Trans. Model. Comput. Simul. 15, 4 (Oct. 2005), 346-361. https://doi.org/10.1145/1113316.1113319. URL: https: //web.archive.org/web/20210126143346/http://www. iro.umontreal.ca/~lecuyer/myftp/papers/xorshift.pdf.
Niederreiter H. Quasi-Monte Carlo methods and pseudo-random number. doi: https://doi.org/10. 1090/S0002-9904-1978-14532-7. URL: https://www.ams. org/journals/bull/1978-84-06/S0002-9904-1978-14532-7/S0002-9904-1978-14532-7.pdf.
D. E. Knuth. The Art of Computer Program-ming, Volume 2: Seminumerical Algorithms, 3rd. ed., Boston, Mass, USA: Addison-Wesley, Longman Pub-lishing, Addison-Wesley, Reading, Mass, 1998. URL: http:// publ.lib.ru/ARCHIVES/K / KNUT_Donal%27d_ Ervin/ Knut_D.E._I skusstvo _ programmirovaniya._T.2. (2001). [djv-fax].zip.
Yurii Shcherbyna, Nadiia Kazakova, Oleksii Fraze-Frazenko. The Mersenne Twister Output Stream Postprocessing. INTERNATIONAL SCIENTIFIC AND PRACTICAL CONFERENCE. September 2021. pp 277-285 URL: https://ceur-ws.org/Vol-3200/paper39.pdf.
J. von Neumann. Various techniques for use in connection with random digits. Applied Math Series, Notes by G. E. Forsythe, in National Bureau of Stand-ards, Vol. 12, 36-38, 1951. URL: https://mcnp.lanl.gov/pdf_ files/nbs_vonneumann.pdf.
Trevisan L. Extractors and Pseudorandom Ge¬ nerators 1999. Journal of the ACM. URL: http://theory.stanford.edu/~trevisan/pubs/extractor-full.pdf.
Siew-Hwee Kwok, Yen-Ling Ee, Guanhan Chew, Kanghong Zheng, Khoongming Khoo, Chik-How Tan. A Comparison of Post-Processing Tech-niques for Biased Random Number Generators. WISTP 2011: Information Security Theory and Practice. Securi-ty and Privacy of Mobile Devices in Wireless Commu-nication. pp 175–190. URL: https://link.springer.com/content/pdf/ 10.1007/978-3-540-74619-5_9.pdf.
George Marsaglia. Random Number Genera-tors. 2003. DOI 10.22237/jmasm/1051747320 URL: https: //digitalcommons.wayne.edu/jmasm/vol2/iss1/2/.
George Marsaglia. Xorshift RNGs. 2003. DOI: 10.18637/jss.v008.i14. URL: https: // www.researchgate. net/publication/5142825_Xorshift_RNGs.
Shcherbyna, Y. Using the Xorshift generator to simulate stochastic processes // Przetwarzanie, transmit¬sja i bezpieczeństwo informacji // monografia / Yurii SHCHERBYNA, Nadiia KAZAKOVA, Oleksii FRAZE-FRAZENKO; Bielsko - Biała: Wydawnictwo Naukowe Akademii Techniczno-Humanistycznej w Bielsku-Białej, 2022. pp 313-144. ISBN 978-83-67652-00-1 DOI: https:// doi.org/10.53052/9788367652001.
The Mersenne Twister Output Stream Post-processing. Shcherbyna, Y., Kazakova, N., Fraze-Frazenko, O. CEUR Workshop https://ceur-ws.org/Vol-3200/paper39.pdf, 2021, 3200, pp. 265-273.
Yevseiev, S., Melenti, Y., Voitko, O., Hrebe-niuk, V., Korchenko, A., Mykus, S., Milov, O., Pro-kopenko, O., Sievierinov, O., Chopenko, D. Develop-ment of a Concept for Building a Critical Infrastructure Facilities Security System (2021) Eastern-European Journal of Enterprise Technologies, 3, pp. 63-83. DOI: 10.15587/1729-4061.2021. 233533.
