Generador de números pseudoaleatorios

Un generador pseudoaleatorio de números (GPAN) es un algoritmo que produce una sucesión de números que es una muy buena aproximación a un conjunto aleatorio de números. La sucesión no es exactamente aleatoria en el sentido de que queda completamente determinada por un conjunto relativamente pequeño de valores iniciales, llamados el estado del GPAN. Si bien es posible generar sucesiones mediante generadores de números aleatorios por dispositivos mecánicos que son mejores aproximaciones a una sucesión aleatoria, los números pseudoaleatorios son importantes en la práctica para simulaciones (por ejemplo, de sistemas físicos mediante el método de Montecarlo), y desempeñan un papel central en la criptografía.

La mayoría de los algoritmos de generadores pseudoaleatorios producen sucesiones que poseen una distribución uniforme según varios tipos de pruebas. Las clases más comunes de estos algoritmos son generadores lineales congruentes, generadores Fibonacci demorados, desplazamiento de registros con retroalimentación lineal y desplazamientos de registros con retroalimentación generalizada. Entre los desarrollos más recientes de algoritmos pseudoaleatorios se encuentran Blum Blum Shub, Fortuna, y el Mersenne twister.

Se requiere de un cuidadoso análisis matemático para tener algún tipo de confianza en que un dado GPAN genera números que son suficientemente "aleatorios" para ser útiles para el propósito para el que se los precisa. Robert R. Coveyou del Oak Ridge National Laboratory escribió un artículo titulado «La generación de números aleatorios es demasiado importante como para ser dejado al azar».[1] Y como John von Neumann decía en broma, «todo el que desarrolla métodos aritméticos para producir dígitos aleatorios esta desde luego en pecado».[2]

Problemas de los generadores determinísticos

En la práctica, los resultados de muchos GPAN presentan artefactos matemáticos que hacen que los mismos fallen en pruebas de detección de parámetros estadísticos. Entre estos se incluyen:

  • Períodos más cortos que lo esperado para algunos estados semilla; en este contexto dichos estados semilla pueden ser llamados 'débiles'
  • Falta de uniformidad de la distribución
  • Correlación de valores sucesivos
  • Pobre distribución dimensional de la sucesión resultado
  • Las distancias entre la ocurrencia de ciertos valores están distribuidas de manera distinta que la que corresponde a una sucesión aleatoria
  • Algunas secuencias de bits son 'más aleatorias' que otras

Los defectos que son exhibidos por los GPAN van desde un rango de lo imperceptible hasta lo absolutamente obvio. El algoritmo de números aleatorios RANDU utilizado por décadas en grandes computadoras tipo mainframe poseía serias deficiencias, y como consecuencia mucho del trabajo de investigación producido en ese período es menos confiable de lo que podría haber sido.

Lista de Generadores de Números Pseudoaleatorios

En esta sección se presenta una lista de generadores que marcaron históricamente el campo de estudio del proceso de generación de números pseudoaleatorios, ya sea por su importancia histórica o por ser un modelo innovador teniendo en cuenta sus respectivas épocas. Además, a pesar de ser PRNGs (Generadores de Números Pseudoaleatorios, en inglés) algunos de ellos pueden ser aplicables dentro del campo de la criptografía, como es el caso del fuerte algoritmo Blum Blum Shub y Fortuna como se ha presentado anteriormente.

Algoritmo Año Autores Referencias Descripción
Cuadrado Medio 1946 John von Neumann [3] Un PRNG considerado de baja calidad pero de gran relevancia histórica por ser uno de los algoritmos pioneros.
Generador de Lehmer 1951 D. H. Lehmer [4] También conocido como método Congruente Lineal Multiplicativo y de gran influencia en este campo de estudio.
Generador lineal congruencial 1958 W. E. Thomson [5] Modelo derivado de Lehmer (1951) de gran influencia y muy estudiado en todo el mundo.
Generador Lagged Fibonacci (LFG) 1958 G. J. Mitchell; D.P. Moore [6] Un algoritmo muy influyente en el campo del estudio de los procesos de generación de números aleatorios que inspiró a otros grandes autores en los siguientes años como George Marsaglia, creador del valorado test de calidad de números aleatorios llamado "Diehard", por ejemplo.
Linear-feedback Shift Register 1965 R. C. Tausworthe [7] Un generador cuyo diseño influyó en muchos otros PRNG posteriores. Por lo tanto, es muy importante desde el punto de vista histórico. También conocido como el generador Tausworthe.
Generador de Wichmann-Hill 1982 B. A. Wichmann; D. I. Hill [8] Una combinación de tres pequeños LCGs, adecuados para CPUs de 16 bits. Ampliamente utilizado en muchos programas, por ejemplo se utilizó en Excel 2003 y algunas versiones posteriores para la función RAND de Excel y fue el generador por defecto en el lenguaje Python hasta la versión 2.2.
Rule 30 1983 Stephen Wolfram [9] Generador basado en autómatas celulares.
Blum Blum Shub 1986 Manuel Blum;Leonore Blum; Michael Shub [10] Considerado uno de los generadores más seguros desde el punto de vista criptográfico, debido principalmente a la implementación en su fórmula de estudios y conceptos derivados de la teoría de números.
Generador de Park-Miller 1988 S. K. Park; K. W. Miller [11] Una implementación específica de un generador de Lehmer, ampliamente utilizada porque se incluye en C++ como la función minstd_rand0 a partir de C++11.
MIXMAX 1991 G. K. Savvidy; N. G. Ter-Arutyunyan-Savvidy [12] Es un generador que pertenece a la clase de generador lineal congruente matricial, una generalización del Método Congruente Lineal. La lógica de la familia de generadores MIXMAX se basa en los resultados de la teoría ergódica y la mecánica clásica.
Add-with-carry (ACW) 1991 G. Marsaglia; A. Zaman [13] Una modificación de los generadores Lagged-Fibonacci.
Subtract-with-borrow 1991 G. Marsaglia; A. Zaman [13] Algoritmo derivado de los generadores Lagged-Fibonacci.
ISAAC 1993 R. J. Jenkins [14] Generador criptográfico seguro (CSPRNG) desarrollado por Robert J. Jenkins.
Mersenne twister 1998 M. Matsumoto; T. Nishimura [15] Probablemente sea el generador más conocido de esta lista, principalmente porque es un algoritmo implementado en las funciones RAND de los lenguajes de programación Python y R, además de su gran presencia en juegos electrónicos como el Pro Evolution Soccer (PES).
Xorshift 2003 G. Marsaglia [16] Es un subtipo muy rápido de generadores LFSR. Marsaglia también propuso como mejora el generador xorwow, en el que la salida de un generador xorshift se suma con una secuencia de Weyl. El generador xorwow es el generador por defecto de la biblioteca CURAND de la interfaz de programación de aplicaciones nVidia CUDA para unidades de procesamiento gráfico.
Fortuna 2003 Bruce Schneier; Niels Ferguson Algoritmo considerado criptográficamente seguro. Un CSPRNG muy conocido por ser implementado en los sistemas y productos de Apple.
Well equidistributed long-period linear (WELL) 2006 F. Panneton; P. L'Ecuyer; M. Matsumoto [17] Algoritmo conocido por ser complementario al Mersenne Twister (MT), buscando deliberadamente cubrir sus puntos débiles.
Advanced Randomization System (ARS) 2011 J. Salmon; M. Moraes; R. Dror; D. Shaw [18] Una versión simplificada del cifrado en bloque AES, que permite un rendimiento muy rápido en el sistema que soporta AES-NI.
Permuted Congruential Generator (PCG) 2014 M. E. O'Neill [19] Un modelo derivado del Método Lineal Congruencial.
Random Cycle Bit Generator (RCB) 2016 R. Cookman [20] El RCB se describe como un generador de patrones de bits hecho para superar algunas de las deficiencias con el Mersenne Twister (MT) y la restricción de duración de período/bit corto de los generadores de desplazamiento/módulo.
Xoroshiro128+ 2018 D. Blackman; S. Vigna [21] Una modificación de los generadores Xorshift de G. Marsaglia, uno de los generadores más rápidos en las CPUs modernas de 64 bits. Los generadores relacionados son xoroshiro128**, xoshiro256+ y xoshiro256***.
64-bit MELG (MELG-64) 2018 S. Harase; T. Kimoto [22] Una implementación de generadores lineales F2 de 64 bits con el período primario de Mersenne.
Squares RNG 2020 B. Widynski [23] Generador derivado del método del cuadrado medio propuesto por Jhon von Neumman.
Itamaracá (Ita) 2021 D. H. Pereira [24] Conocido por ser el primer algoritmo PRNG que tiene la Función de Valor Absoluto en su base. Itamaracá también se presenta como un modelo sencillo y rápido que genera secuencias de números aleatorios aperiódicos.

Notas
  1. Peterson, Ivars. The Jungles of Randomness: A Mathematical Safari. Wiley, NY, 1998. (pp. 178) ISBN 0-471-16449-6
  2. "Various techniques used in connection with random digits", Applied Mathematics Series, no. 12, 36-38 (1951).
  3. Annual report 1951 National Bureau of Standards. National Institute of Standards and Technology. 1951. Consultado el 12 de mayo de 2022.
  4. Curtiss, J. H. (1947-04). «A Symposium of Large Scale Digital Calculating Machinery». Mathematical Tables and Other Aids to Computation 2 (18): 229. ISSN 0891-6837. doi:10.2307/2002294. Consultado el 12 de mayo de 2022.
  5. «Validate User». academic.oup.com. doi:10.1093/comjnl/1.2.83. Consultado el 12 de mayo de 2022.
  6. Wrench, J. W. (1970). «Table errata: The art of computer programming, Vol. 2: Seminumerical algorithms (Addison-Wesley, Reading, Mass., 1969) by Donald E. Knuth». Mathematics of Computation (en inglés) 24 (110): 504. ISSN 0025-5718. doi:10.1090/S0025-5718-1970-0400642-2. Consultado el 12 de mayo de 2022.
  7. Tausworthe, Robert C. (1965). «Random numbers generated by linear recurrence modulo two». Mathematics of Computation (en inglés) 19 (90): 201-209. ISSN 0025-5718. doi:10.1090/S0025-5718-1965-0184406-1. Consultado el 12 de mayo de 2022.
  8. Wichmann, B. A.; Hill, I. D. (1982). «Algorithm AS 183: An Efficient and Portable Pseudo-Random Number Generator». Journal of the Royal Statistical Society. Series C (Applied Statistics) 31 (2): 188-190. ISSN 0035-9254. doi:10.2307/2347988. Consultado el 12 de mayo de 2022.
  9. Wolfram, Stephen (1 de julio de 1983). «Statistical mechanics of cellular automata». Reviews of Modern Physics 55 (3): 601-644. doi:10.1103/RevModPhys.55.601. Consultado el 12 de mayo de 2022.
  10. Blum, L.; Blum, M.; Shub, M. (1 de mayo de 1986). «A Simple Unpredictable Pseudo-Random Number Generator». SIAM Journal on Computing 15 (2): 364-383. ISSN 0097-5397. doi:10.1137/0215025. Consultado el 12 de mayo de 2022.
  11. Park, S. K.; Miller, K. W. (1 de octubre de 1988). «Random number generators: good ones are hard to find». Communications of the ACM 31 (10): 1192-1201. ISSN 0001-0782. doi:10.1145/63039.63042. Consultado el 12 de mayo de 2022.
  12. Savvidy, G. K; Ter-Arutyunyan-Savvidy, N. G (1 de diciembre de 1991). «On the Monte Carlo simulation of physical systems». Journal of Computational Physics (en inglés) 97 (2): 566-572. ISSN 0021-9991. doi:10.1016/0021-9991(91)90015-D. Consultado el 12 de mayo de 2022.
  13. Marsaglia, George; Zaman, Arif (1991-08). «A New Class of Random Number Generators». The Annals of Applied Probability 1 (3): 462-480. ISSN 1050-5164. doi:10.1214/aoap/1177005878. Consultado el 12 de mayo de 2022.
  14. «burtleburtleburtleburtleburtle». www.burtleburtle.net. Consultado el 12 de mayo de 2022.
  15. Matsumoto, Makoto; Nishimura, Takuji (1 de enero de 1998). «Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator». ACM Transactions on Modeling and Computer Simulation 8 (1): 3-30. ISSN 1049-3301. doi:10.1145/272991.272995. Consultado el 12 de mayo de 2022.
  16. Marsaglia, George (4 de julio de 2003). «Xorshift RNGs». Journal of Statistical Software (en inglés) 8: 1-6. ISSN 1548-7660. doi:10.18637/jss.v008.i14. Consultado el 12 de mayo de 2022.
  17. Panneton, François; L'Ecuyer, Pierre; Matsumoto, Makoto (1 de marzo de 2006). «Improved long-period generators based on linear recurrences modulo 2». ACM Transactions on Mathematical Software 32 (1): 1-16. ISSN 0098-3500. doi:10.1145/1132973.1132974. Consultado el 12 de mayo de 2022.
  18. Salmon, John K.; Moraes, Mark A.; Dror, Ron O.; Shaw, David E. (12 de noviembre de 2011). «Parallel random numbers: as easy as 1, 2, 3». Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis. SC '11 (Association for Computing Machinery): 1-12. ISBN 978-1-4503-0771-0. doi:10.1145/2063384.2063405. Consultado el 12 de mayo de 2022.
  19. Sileshi, B.G.; Ferrer, C.; Oliver, J. (2014-11). «Accelerating hardware Gaussian random number generation using Ziggurat and CORDIC algorithms». IEEE SENSORS 2014 Proceedings (en inglés estadounidense) (IEEE). doi:10.1109/icsens.2014.6985457. Consultado el 12 de mayo de 2022.
  20. «Random Bit Generator». SpringerReference (Springer-Verlag). Consultado el 12 de mayo de 2022.
  21. Blackman, David; Vigna, Sebastiano (28 de marzo de 2022). «Scrambled Linear Pseudorandom Number Generators». arXiv:1805.01407 [cs]. Consultado el 12 de mayo de 2022.
  22. Harase, Shin; Kimoto, Takamitsu (3 de enero de 2018). «Implementing 64-bit Maximally Equidistributed F2-Linear Generators with Mersenne Prime Period». ACM Transactions on Mathematical Software 44 (3): 30:1-30:11. ISSN 0098-3500. doi:10.1145/3159444. Consultado el 12 de mayo de 2022.
  23. Widynski, Bernard (13 de marzo de 2022). «Squares: A Fast Counter-Based RNG». arXiv:2004.06278 [cs]. Consultado el 12 de mayo de 2022.
  24. Pereira, Daniel Henrique (25 de enero de 2022). Itamaracá: A Novel Simple Way to Generate Pseudo-random Numbers (en inglés). doi:10.33774/coe-2022-zsw6t. Consultado el 12 de mayo de 2022.

Referencias
  • Michael Luby, Pseudorandomness and Cryptographic Applications, Princeton Univ Press, 1996. A definitive source of techniques for provably random sequences.
  • Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Chapter 3, pp. 1–193. Extensive coverage of statistical tests for non-randomness.
  • R. Matthews Maximally Periodic Reciprocals Bulletin of the Institute of Mathematics and its Applications 28 147-148 1992
  • J. Viega, Practical Random Number Generation in Software, in Proc. 19th Annual Computer Security Applications Conference, Dec. 2003.
  • John von Neumann, "Various techniques used in connection with random digits," in A.S. Householder, G.E. Forsythe, and H.H. Germond, eds., Montecarlo Method, National Bureau of Standards Applied Mathematics Series, 12 (Washington, D.C.: U.S. Government Printing Office, 1951): 36-38.
  • NIST Recommendation for Random Number Generation Using Deterministic Random Bit Generators

Enlaces externos
Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.