Дослідження множини початкових значень генераторів псевдовипадкових чисел на основі арифметики з рухомою комою

DOI: 10.31673/2409-7292.2024.020011

Анотація

У даній статті досліджено статистичні характеристики та період повторення запропонованих раніше генераторів псевдовипадкових чисел (ГПВЧ), побудованих на основі наближених методів обчислення елементарних функцій в арифметиці з рухомою комою. Метою роботи була оцінка якості згенерованих послідовностей, визначення допустимих діапазонів початкових значень та вибору параметрів генератора із найкращими характеристиками. Досліджено використання тотожної функції, алгоритму наближеного обчислення оберненого значення та шести алгоритмів зворотного квадратного кореня у двох режимах генерації та для п’яти можливих комбінацій параметрів ГПВЧ залежно від вибору початкових значень. Для тестування запропонованих варіантів генераторів формувались послідовності псевдовипадкових чисел розміру 2 Гб для фіксованого набору їх початкових значень. З’ясовано, що період повторення залежить від вибору початкового значення генератора, параметру bytesCount та елементарної функції. Виконано статистичне тестування послідовностей на основі набору тестів NIST, графічного тесту та аналізу гістограм. Запропоновано діапазони вибору початкових значень залежно від параметрів генератора та вибрано три генератори із найкращими характеристиками. Зокрема, більш як 82% сформованих послідовностей генератора rsqrt2dc_everyBit з параметрами bytesCount = 1 та offset = 0 (максимальний період – 222,12 Мб) проходять всі тести NIST. Встановлено, що для вибору початкових значень оптимальною є множина розмірності близько 2⁶⁰ елементів, x₀ ϵ [0,5; 10¹³⁵). Виявлено певні статистичні закономірності та недоліки окремих генераторів. Додатково продемонстровано, що алгоритми апроксимації елементарних функцій в арифметиці з рухомою комою можуть використовуватись для побудови ГПВЧ із непоганими характеристиками.

Ключові слова: псевдовипадкова послідовність, генератори псевдовипадкових чисел, елементарна функція, апроксимаційні методи, арифметика з рухомою комою, статистичні тести NIST, період повторення.

Перелік посилань
1. Kietzmann, P. A guideline on pseudorandom number generation (PRNG) in the IoT [Electronic resource] / P. Kietzmann, T.C. Schmidt, M. Wahlisch // ACM computing surveys. – 2021. – Vol. 54, no. 6. – P. 1–38. – Mode of access: https://doi.org/10.1145/3453159.
2. Генератори псевдовипадкових бітових послідовностей на основі чисельних методів в арифметиці з рухомою комою [Електронний ресурс] / В. Максимович [та ін.] // Сучасна спеціальна техніка. – 2021. – Т. 64, № 1. – С. 81–92. – Режим доступу: https://doi.org/10.36486/mst2411-3816.2021.1(64).7.
3. Matsumoto, M. Pseudorandom number generation: impossibility and compromise [Electronic resource] / M. Matsumoto, M. Saito, H. Haramoto // Journal of universal computer science. – 2006. – Vol. 12, no. 6. – P. 672–690. – Mode of access: https://doi.org/10.3217/jucs-012-06-0672.
4. Rani, S. Steganography on digital color image using modulo function and pseudo-random number generator [Electronic resource] / S. Rani, A. Kurniawardhani, Y. A. W. Rendani // International journal on advanced science engineering and information technology. – 2021. – Vol. 11, no. 6. – 2470. – Mode of access: https://doi.org/10.18517/ijaseit.11.6.12687.
5. Kordov, K. Steganography in color images with random order of pixel selection and encrypted text message embedding [Electronic resource] / K. Kordov, S. Zhelezov // PeerJ computer science. – 2021. – Vol. 7, no. 11. – e380. – Mode of access: https://doi.org/10.7717/peerj-cs.380.
6. Wang, L. Pseudo-random number generator based on logistic chaotic system [Electronic resource] / L. Wang, H. Cheng // Entropy. – 2019. – Vol. 21, no. 10. – 960. – Mode of access: https://doi.org/10.3390/e21100960.
7. Datcu, O. Chaos based cryptographic pseudo-random number generator template with dynamic state change [Electronic resource] / O. Datcu, C. Macovei, R. Hobincu // Applied sciences. – 2020. – Vol. 10, no. 2. – 451. – Mode of access: https://doi.org/10.3390/app10020451.
8. Demchik, V. Pseudo-random number generators for Monte Carlo simulations on graphics processing units [Electronic resource] / V. Demchik. – Ithaca, NY, USA : ArXiv, 2010. – 31 p. – (Preprint / Cornell University ; 1003.1898v1). – Mode of access: https://arxiv.org/pdf/1003.1898v1 (date of access: 10.05.2024).
9. IEEE 754-2019. Standard for floating-point arithmetic [Electronic resource]. – Replaces IEEE 754-2008 ; effective from 2019-07-22. – Official edition. – 2019. – 84 p. – Mode of access: https://doi.org/10.1109/IEEESTD.2019.8766229.
10. Cotrina, G. Gaussian pseudorandom number generator using linear feedback shift registers in extended fields [Electronic resource] / G. Cotrina, A. Peinado, A. Ortiz // Mathematics. – 2021. – Vol. 9, no. 5. – 556. – Mode of access: https://doi.org/10.3390/math9050556.
11. Harase, S. Implementing 64-bit maximally equidistributed F2-linear generators with Mersenne prime period [Electronic resource] / S. Harase, T. Kimoto // ACM transactions on mathematical software. – 2018. – Vol. 44, no. 3. – 30. – Mode of access: https://doi.org/10.1145/3159444.
12. Marsaglia, G. On the randomness of pi and other decimal expansions [Electronic resource] / G. Marsaglia // InterStat: statistics on the Internet. – 2005. – P. 1–17. – Mode of access: http://yaroslavvb.com/papers/marsaglia-on.pdf (date of access: 23.05.2024).