A study on comparison of pseudorandom number generator

Padányi, Viktória; Herendi, Tamás

doi:10.2478/ijmce-2023-0003

Abstract

In this paper, we have collected some theoretical and practical pseudorandom number generators (PRNGs) with uniform distribution. We have also analyzed some of the most prevalent statistical tests and we present some observations and statistical tests of the sequences generated by the described generators.

References

Kolmogorov A.N., On tables of random numbers, Theoretical Computer Science, 207(2), 387-395, 1998.
Search in Google Scholar Back to article
Kolmogorov A.N., Three approaches to the quantitative definition of information, Problems of Information Transmission, 1(1), 1-7, 1965.
Search in Google Scholar Back to article
Chaitin G.J., On the simplicity and speed of programs for computing infinite sets of natural numbers, Journal of the ACM, 16(3), 407-422, 1969.
Search in Google Scholar Back to article
Solomono R., A formal theory of inductive inference: Part I and Part II, Information and Control, 7(1) and (2), 1-22 and 224-254, 1964.
Search in Google Scholar Back to article
Niederreiter H., Random Number Generation and Quasi-Monte Carlo Methods, Society for Industrial and Applied Mathematics (SIAM), USA, 1992.
Search in Google Scholar Back to article
Mauduit C., Sárközy A., On finite pseudorandom binary sequences I: Measure of pseudorandomness, the Legendre symbol, Acta Arithmetica, 82(4), 365-377, 1997.
Search in Google Scholar Back to article
Weyl H., Üeber die Gleichverteilung von Zahlen mod. eins, Mathematische Annalen, 77, 313-352, 1916.
Search in Google Scholar Back to article
Van Der Corput J.G., Verteilungsfunktionen (erste mitteilung), Proceedings of the Koninklijke Akademie van Wetenschappen te Amsterdam, 38, 813-821, 1935.
Search in Google Scholar Back to article
Herendi T., Construction of uniformly distributed linear recurring sequences modulo powers of 2, Uniform Distribution Theory, 13(1), 109-129, 2018.
Search in Google Scholar Back to article
Borel M.E., Les probabilités dénombrables et leurs applications arithmétiques, Rendiconti del Circolo Matematico di Palermo, 27, 247-271, 1909.
Search in Google Scholar Back to article
Bruijn N.G., A combinatorial problem, Koninklijke Nederlandse Akademie v. Wetenschappen, 49, 758-764, 1946.
Search in Google Scholar Back to article
Knuth D.E., The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Addison Wesley, 1981.
Search in Google Scholar Back to article
Lehmer D.H., Mathematical methods in large-scale computing units, Proceedings of a Second Symposium on Large-Scale Digital Calculating, 26, 141-146, 1951.
Search in Google Scholar Back to article
Lewis T.G., Payne W.H., Generalized Feedback Shift Register Pseudorandom Number Algorithm, Journal of the ACM, 20(3), 456-468, 1973.
Search in Google Scholar Back to article
Kurita Y., Matsumoto M., Twisted GFSR generators, ACM Transactions on Modeling and Computer Simulation, 2(3), 179-194, 1992.
Search in Google Scholar Back to article
Kurita Y., Matsumoto M., Twisted GFSR generators II. ACM Transactions on Modeling and Computer Simulation, 4(3), 245-466, 1994.
Search in Google Scholar Back to article
Thomson W.E., A Modified Congruence Method of Generating Pseudo-random Numbers, The Computer Journal, 1(2), 83, 1958.
Search in Google Scholar Back to article
Rotenberg A., A New Pseudo-Random Number Generator, Journal of the ACM, 7(1), 75-77, 1960.
Search in Google Scholar Back to article
Matsumoto M., Nishimura T., Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator, ACM Transactions on Modeling and Computer Simulation, 8(1), 3-30, 1998.
Search in Google Scholar Back to article
Panneton F., LEcuyer P., Matsumoto M., Improved long-period generators based on linear recurrences modulo 2, ACM Transactions on Mathematical Software, 32(1), 1-16, 2006.
Search in Google Scholar Back to article
Wichmann B.A., Hill I.D., Algorithm AS 183: An Efficient and Portable Pseudo-Random Number Generator, Journal of the Royal Statistical Society: Series C (Applied Statistics), 30(2), 188-190, 1982.
Search in Google Scholar Back to article
Wichmann B.A., Hill I.D., Generating good pseudo-random numbers, Computational Statistics Data Analysis, 51(3), 1614-1622, 2006.
Search in Google Scholar Back to article
Wikramaratna R.S., ACORN-A new method for generating sequences of uniformly distributed Pseudo-Random Numbers, Journal of Computational Physics, 83(1), 16-31, 1989.
Search in Google Scholar Back to article
ONeill M.E., PCG: A family of simple fast space-efficient statistically good algorithms for random number generation, Harvey Mudd College, HMC-CS-2014-0905, 2014.
Search in Google Scholar Back to article
Blum L., Blum M., Shub M., A Simple Unpredictable Pseudo-Random Number Generator, SIAM Journal on Computing, 15(2), 364-383, 1986.
Search in Google Scholar Back to article
Eichenauer J., Lehn J., A non-linear congruential pseudo random number generator, Statistische Hefte, 27, 315-326, 1986.
Search in Google Scholar Back to article
Neumann J.V., Various techniques used in connection with random digits, Applied Mathematics Series, Notes by G.E. Forsythe, in National Bureau of Standards, 12, 36-38, 1951.
Search in Google Scholar Back to article
Padányi V., Herendi T., Generalized Middle-Square Method, Annales Mathematicae et Informaticae, 56, 95-108, 2022.
Search in Google Scholar Back to article
Widynski B., Middle-Square weyl sequence RNG, arXiv:1704.00358 [cs.CR], 2022.
Search in Google Scholar Back to article
Schneier B., Applied Cryptography: Second Edition: Protocols, Algorithms and Source Code in C (Cloth), John Wiley Sons, 1996.
Search in Google Scholar Back to article
Marsaglia G., Xorshift RNGs, Journal of Statistical Software, 8(14), 1-6, 2003.
Search in Google Scholar Back to article
Damgård I.B., On the randomness of legendre and jacobi sequences, Conference on the Theory and Application of Cryptography CRYPTO 1988: Advances in Cryptology CRYPTO 88, 163-172, Part of the Lecture Notes in Computer Science, 403, 163-172, 1990.
Search in Google Scholar Back to article
FIPS-81. DES Modes of Operation. https://csrc.nist.gov/csrc/media/publications/fips/81/archive/1980-12-02/documents/fips81.pdf, 1980.
Search in Google Scholar Back to article
Akopov N.Z., Martirosyan N.H., The optimal approach for Kolmogorov-Smirnov test calculation in high dimensional space, Mathematical Problems of Computer Science, 44, 138-144, 2021.
Search in Google Scholar Back to article
Dieharder.https://webhome.phy.duke.edu/rgb/General/dieharder.php. Website.
Search in Google Scholar Back to article
Lecuyer P., Simard R., TestU01: A C library for empirical testing of random number generators, ACM Transactions on Mathematical Software, 33(4), 1-40, 2007.
Search in Google Scholar Back to article
National Institute of Standards and Technology. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications: NIST SP 800-822, 2012.
Search in Google Scholar Back to article
Rukhin A.L., Soto J., Nechvatal J.R., Smid M.E., Barker E.B., Leigh S.D., Levenson M., Vangel M., Banks D.L., Heck-ert N.A., Dray J.F., Vo S.C., A statistical test suite for random and pseudorandom number generators for cryptographic applications, NIST Special Publication, 800-822, 2001.
Search in Google Scholar Back to article

A study on comparison of pseudorandom number generator

Abstract

Paradigm

My account