|

Генератор равномерных случайных величин по технологии полного вихревого массива

Авторы: Деон А.Ф., Меняев Ю.А. Опубликовано: 12.04.2017
Опубликовано в выпуске: #2(113)/2017  
DOI: 10.18698/0236-3933-2017-2-86-110

 
Раздел: Информатика, вычислительная техника и управление | Рубрика: Системный анализ, управление и обработка информации  
Ключевые слова: генератор псевдослучайных величин, случайные последовательности, конгруэнтная величина, вихревой генератор

Генераторы равномерно распределенных случайных величин активно используются в различных приложениях, начиная от математики, моделирования радиоэлектронных и технических конструкций вплоть до медицинских и биологических исследований. Предложен новый подход к генерации случайных величин на основе объединения возможностей начального конгруэнтного массива с глобальным вихрем кольцевой технологии для полных стохастических последовательностей. Экспериментально подтверждено, что для полных последовательностей такой тип генерации обеспечивает равномерное распределение случайных величин. Предлагаемое программное обеспечение допускает методы настройки технологии генерации, где случайные величины могут принимать любую битовую длину. Рассмотрено автоматическое переключение параметров генератора, таких как начальные значения и конгруэнтные константы, что позволяет увеличивать число вариантов генерируемых последовательностей. Приведенные результаты тестирования подтверждают абсолютную равномерность распределения без каких-либо повторений или пропусков в генерируемых последовательностях случайных величин.

Литература

[1] Cryptanalysis of DES implemented on computers with cache / Y. Tusnoo, T. Saito, T. Suzaki, M. Shigeri, H. Miyauchi // Proc. Cryptographic Hardware and Embedded Systems - CHES 2003. 5th International Workshop. 2003. Р. 62-76. DOI: 10.1007/978-3-540-45238-6_6 URL: http://link.springer.com/chapter/10.1007%2F978-3-540-45238-6_6

[2] Ozturk E., Sunar В., Savas Е. Low-power elliptic curve cryptography using scaled modular arithmetic // Proc. Cryptographic Hardware and Embedded Systems - CHES 2004. 6th International Workshop. Р. 92-106. DOI: 10.1007/978-3-540-28632-5_7 URL: http://link.springer.com/chapter/10.1007%2F978-3-540-28632-5_7

[3] Panneton F., L

[4] Deon A.F., Menyaev Yu.A. The complete set simulation of stochastic sequences without repeated and skipped elements // Journal of Universal Computer Science. 2016. Vol. 22. No. 8. P. 1023-1047. DOI: 10.3217/jucs-022-08-1023 URL: http://www.jucs.org/jucs_22_8/the_complete_set_simulation

[5] Entacher K. Bad subsequences of well-known linear congruential pseudorandom number generators // ACM TOMACS. 1998. Vol. 8. No.1. Р. 61-70. DOI: 10.1145/272991.273009 URL: http://dl.acm.org/citation.cfm?doid=272991.273009

[6] Leeb H., Wegenkittl S. Inversive and linear congruential pseudorandom number generators in empirical tests // ACM TOMACS, 1997. Vol. 7. Р. 272-286. DOI: 10.1145/249204.249208 URL: http://dl.acm.org/citation.cfm?doid=249204.249208

[7] Park S.K., Miller K.W. Random number generators: good ones are hard to find // Communication of the ACM. 1988. Vol. 31. No. 10. Р. 1192-1201. DOI: 10.1145/63039.63042 URL: http://dl.acm.org/citation.cfm?doid=63039.63042

[8] Optical clearing in photoacoustic flow cytometry / Yu.A. Menyaev, D.A. Nedosekin, M. Sarimollaoglu, M.A. Juratli, E.I. Galanzha, V.V. Tuchin, V.P. Zharov // Biomed. Opt. Express. 2013. Vol. 4. No. 12. Р. 3030-3041. DOI: 10.1364/BOE.4.003030 URL: https://www.osapublishing.org/boe/abstract.cfm?uri=boe-4-12-3030

[9] Wiese K.C., Hendriks А., Deschenes А., Youssef В.В. The impact of pseudorandom number quality on P-RnaPredict, a parallel genetic algorithm for RNA secondary structure prediction // GECCO ’05. Proc. 7th Annual Conf. on Genetic and Evolutionary Computation. 2005. Р. 479-480. DOI: 10.1145/1068009.1068089 URL: http://dl.acm.org/citation.cfm?doid=1068009.1068089

[10] Leonard P., Jackson D. Efficient evolution of high entropy RNGs using single node genetic programming // GECCO ’15. Proc. of the 2015 Annual Conf. on Genetic and Evolutionary Computation. 2015. Р. 1071-1078. DOI: 10.1145/2739480.2754820 URL: http://dl.acm.org/citation.cfm?doid=2739480.2754820

[11] Niederreiter H. Some linear and nonlinear methods for pseudorandom number generation // WSC ’95. Proc. of the 27th Conf. on Winter Simulation. 1995. Р. 250-254. DOI: 10.1145/224401.224611 URL: http://dl.acm.org/citation.cfm?doid=224401.224611

[12] Entacher K. Parallel streams of linear random numbers in the spectral test // ACM TOMACS. 1999. Vol. 9. No.1. Р. 31-44. DOI: 10.1145/301677.301682 URL: http://dl.acm.org/citation.cfm?doid=301677.301682

[13] Matsumoto M., Nishimura Т. Mersenne twister: a 623-dimensionnally equidistributed uniform pseudorandom number generator // ACM TOMACS. 1998. Vol. 8. No. 1. Р. 3-30. DOI: 10.1145/272991.272995 URL: http://dl.acm.org/citation.cfm?doid=272991.272995

[14] Nishimura T. Tables of 64-bit Mersenne twisters // ACM TOMACS. 2000. Vol. 10. No. 4. Р. 348-357. DOI: 10.1145/369534.369540 URL: http://dl.acm.org/citation.cfm?doid=369534.369540

[15] Makino J. Lagged-Fibonacci random number generators on parallel computers // Parallel Comput. 1994. Vol. 20. No. 9. Р. 1357-1367. DOI: 10.1016/0167-8191(94)90042-6 URL: http://www.sciencedirect.com/science/article/pii/0167819194900426?via%3Dihub

[16] Aluru S. Lagged Fibonacci random number generators for distributed memory parallel computers // J. Parallel Distr. Com. 1997. Vol. 45. No. 1. Р. 1-12. DOI: 10.1006/jpdc.1997.1363 URL: http://www.sciencedirect.com/science/article/pii/S0743731597913630?via%3Dihub

[17] Blum L., Blum М., Shub М. A Simple unpredictable pseudo-random number generator // SIAM Journal on Computing.1986. Vol. 15. No. 2. Р. 364-383. DOI: 10.1137/0215025 URL: http://epubs.siam.org/doi/10.1137/0215025

[18] Schildt H. C# 4.0: the complete reference. New York: The McGraw-Hill Companies, 2010. 949 p.

[19] Saito M., Matsumoto М. SIMD-oriented fast Mersenne twister: a 128-bit pseudorandom number generator // Monte Carlo and quasi-Monte Carlo methods 2006. Heidelberg, Berlin: Springer, 2008. Р. 607-622. DOI: 10.1007/978-3-540-74496-2_36 URL: http://link.springer.com/chapter/10.1007%2F978-3-540-74496-2_36

[20] Lewis T.G., Payne W.H. Generalized feedback shift register pseudorandom number algorithm // J. ACM. 1973. Vol. 20. No. 3. Р. 456-486. DOI: 10.1145/321765.321777 URL: http://dl.acm.org/citation.cfm?doid=321765.321777

[21] Ghandrasekaran S., Аmira А. High performance FPGA implementation of the Mersenne twister // DELTA. IEEE International Workshop on Electronic Design, Test and Applications. 2008. Р. 482-485. DOI: 10.1109/DELTA.2008.113 URL: http://ieeexplore.ieee.org/document/4459598

[22] Pellicer-Lostao С., Lopez-Ruiz R. Pseudo-random bit generation based on 2D chaotic maps of logistic type and its applications in chaotic cryptography // Proc. Computational Science and its Applications - ICCSA 2008 Int. Conf. 2008. Part. II. Vol. 5073. Р. 784-796. DOI: 10.1007/978-3-540-69848-7_62 URL: http://link.springer.com/chapter/10.1007%2F978-3-540-69848-7_62

[23] Bos J.W., Kleinjung Т., Lenstra А.К., Montgomery P.L. Efficient SIMD arithmetic modulo a Mersenne number // ARITH ’11. Proc. IEEE 20 th Symposium on Computer Arithmetic. 2011. Р. 213-221. DOI: 10.1109/ARITH.2011.37 URL: http://ieeexplore.ieee.org/document/5992129

[24] Rahimov H., Babaie М., Hassanabadi Н. Improving middle square method RNG using chaotic map // Appl. Math. 2011. Vol. 2. Р. 482-486. DOI: 10.4236/am.2011.24062 URL: http://file.scirp.org/pdf/AM20110400016_12226152.pdf

[25] Deon А.В., Menyaev Yu.А. Parametrical tuning of twisting generator // Journal of Computer Science. 2016. Vol. 12. No. 8. Р. 363-378. DOI: 10.3844/jcssp.2016.363.378 URL: http://thescipub.com/abstract/10.3844/jcssp.2016.363.378