ВИБІР ДЖЕРЕЛА ВИПАДКОВОСТІ ДЛЯ КОМП’ЮТЕРНОГО МОДЕЛЮВАННЯ
DOI:
https://doi.org/10.18372/2310-5461.59.17944Ключові слова:
моделювання, стохастичний процес, генератор Xorshift, метод оберненої функції, критерій хі-квадрат Пірсона, постобробка чисельного потокуАнотація
У статті розглядаються проблеми вибору джерела випадковості для комп’ютерного моделювання стохастичних процесів, що використовується для дослідження характеристик потоків подій безпеки в розподілених комп’ютерних мережах, на етапі проектування складних автоматизованих систем та процесів, які мають місце в управлінні виробництвом та інфраструктурними об’єктами. Складовою частиною комп’ютерної моделі є джерело випадковості, яке формує рівномірно розподілений потік випадкових цілих або дійсних чисел. Воно повинно формувати потік рівномірно розподілених чисел і, в той же час, бути економічним з точки зору обчислювальних ресурсів. В роботі надано аналіз простих генераторів псевдовипадкових чисел, в алгоритмі яких використовуються прості комп’ютерні операції. До складу таких генераторів віднесені генератор Фібоначчі з запізненням та запропонований Дж. Марсальєю генератор Xorshift128. Відзначено, що будь-яка нерівномірність розподілення чисел на виході генератора, суттєво впливає на якість процесу, який підлягає моделюванню. На основі результатів проведених досліджень існуючих способів постоброблення вихідних послідовностей, зроблено висновок про те, для забезпечення ефективності алгоритму формування потоку рівномірно роз-поділених псевдовипадкових чисел, процедури додаткового оброблення повинні бути достатньо економічними з точки зору задіяних методів обчислення. Оцінка нерівномірності розподілення числового потоку виконувалась з використанням показника хі-квадрат Пірсона. Для корекції вихідного числового потоку запропоновано і обґрунтовано спосіб екстракції з нього тої його частини, ентропія якої найбільша. Також, обґрунтовано параметри гістограми, що дають хороші результати оцінки вихідного розподілення. Показано, що комбінація простого і економічного генератора псевдовипадкових чисел в сукупності з постобробленням дає хороші результати при мінімальних обчислювальних ресурсах.
Посилання
Mark A. Pinsky, Samuel Karlin. An Introduction to Stochastic Modeling, Fourth Edition., Academic Press, 2010. URL: https://faculty.ksu.edu.sa/ sites/default/files/an_introd_to_stoch_modeling_4th_ed.pdf. (access date 15/07/2023)
Knuth, D. E. The Art of Computer Programming. Volume 2. Seminumerical Algorithms. 3rd edition / D. E. Knuth. – Boston, Mass, USA : Addison-Wesley, Longman Publishing, 1997. – 762 p. ISBN 0-201-89683-4. URL: https://www.pdfdrive. com/art-of-computer-programming-knuth-vol-v2-e57538699.html. (access date 18/07/2023)
Bruce Schneier. Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C. 1996. Wiley Computer Publishing, John Wiley & Sons, Inc. URL: https://dut.edu.ua/uploads/ l_1134_27449793.pdf (access date 15/07/2023)
Lemire Daniel. Fast Random Integer Generation in an Interval. ACM Transactions on Modeling and Computer SimulationVolume 29. Issue 1. Article No.: 3 pp 1–12 URL: https://arxiv.org/pdf/ 1805.10941.pdf (access date 15/07/2023)
Tin Ni Ni Kyaw, Akio Tsuneda. Generation of chaos-based random bit sequences with prescribed auto-correlations by post-processing using linear feedback shift registers. DOI: 10.1587/nolta.8.224
Mario Stipčević, True Random Number Generators. Open Problems in Mathematics and Computational Science, Open Problems in Mathematics and Computational Science 275–315) doi:10.1007/978-3-319-10683-0_12
J. von Neumann. Various techniques for use in connection with random digits. Applied Math Series, Notes by G. E. Forsythe, in National Bureau of Standards, Vol. 12, 36–38, 1951. URL: https://mcnp.lanl.gov/pdf_files/nbs_vonneumann.pdf. (access date 15/07/2023)
Trevisan L. Extractors and Pseudorandom Generators 1999. Journal of the ACM URL: http://theory.stanford.edu/~trevisan/pubs/extractor-full.pdf. (access date 25/07/2023)
Siew-Hwee Kwok, Yen-Ling Ee, Guanhan Chew, Kanghong Zheng, Khoongming Khoo, Chik-How Tan. A Comparison of Post-Processing Techniques for Biased Random Number Generators. WISTP 2011: Information Security Theory and Practice. Security and Privacy of Mobile Devices in Wireless Communication. PP. 175–190. URL: https://link.springer.com/content/pdf/10.1007/978-3-540-74619-5_9.pdf. (access date 15/07/2023)
Yurii Shcherbina, Nadiia Kazakova, Oleksii Fraze-Frazenko. Using the Xorshift generator to simulate stochastic processes. Processing, transmission and security of information – 5 December 2022. URL: https://www.engineerxxi. ath.eu/publikacja/processing-transmission-and-security-of-information-2022/.
George Marsaglia. Xorshift RNGs. 2003. DOI:10.18637/jss.v008.i14.
Laptiev, O., Sobchuk, V.,Subach, I., Barabash, A., Salanda, I. The Method of Detecting Radio Signals Using the Approximation of Spectral Function. CEUR Workshop Proceedings, 2022, 3384, pp. 52– 61.
Valentyn Sobchuk , Iryna Zelenska and Oleksandr Laptiev. Algorithm for solution of systems of singularly perturbed differential equations with a differential turning point. Bulletin of the Polish Academy of Sciences Technical Sciences, Vol.71, No 3, 2023, Article number: e145682. DOI: 10.24425/bpasts. 2023.145682.
