Generador de números pseudoaleatorios para niños
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». 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».
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 | 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 | 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 | 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 | 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 | 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 | 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 | Generador basado en autómatas celulares. | |
| Blum Blum Shub | 1986 | Manuel Blum;Leonore Blum; Michael Shub | 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 | 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 | 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 | Una modificación de los generadores Lagged-Fibonacci. | |
| Subtract-with-borrow | 1991 | G. Marsaglia; A. Zaman | Algoritmo derivado de los generadores Lagged-Fibonacci. | |
| ISAAC | 1993 | R. J. Jenkins | Generador criptográfico seguro (CSPRNG) desarrollado por Robert J. Jenkins. | |
| Mersenne twister | 1998 | M. Matsumoto; T. Nishimura | 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 | 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 | 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 | 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 | Un modelo derivado del Método Lineal Congruencial. | |
| Random Cycle Bit Generator (RCB) | 2016 | R. Cookman | 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 | 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 | Una implementación de generadores lineales F2 de 64 bits con el período primario de Mersenne. | |
| Squares RNG | 2020 | B. Widynski | Generador derivado del método del cuadrado medio propuesto por Jhon von Neumman. | |
| Itamaracá (Ita) | 2021 | D. H. Pereira | 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. |
Véase también
En inglés: Pseudorandom number generator Facts for Kids
