Generador de números pseudoaleatorios

Un generador de números pseudoaleatorios (PRNG), también conocido como generador de bits aleatorios deterministas (DRBG), es un algoritmo para generar una secuencia de números cuyas propiedades se aproximan a las propiedades de secuencias de números aleatorios. La secuencia generada por PRNG no es verdaderamente aleatoria, porque está completamente determinada por un valor inicial, llamado semilla de PRNG (que puede incluir valores verdaderamente aleatorios). Aunque las secuencias que están más cerca de lo verdaderamente aleatorio pueden generarse utilizando generadores de números aleatorios de hardware, los generadores de números pseudoaleatorios son importantes en la práctica por su velocidad en la generación de números y su reproducibilidad.

Los PRNG son fundamentales en aplicaciones como simulaciones (p. ej., para el método Monte Carlo), juegos electrónicos (p. ej., para la generación de procedimientos) y criptografía. Las aplicaciones criptográficas requieren que la salida no sea predecible a partir de salidas anteriores, y se necesitan algoritmos más elaborados, que no heredan la linealidad de los PRNG más simples.

Las buenas propiedades estadísticas son un requisito central para la salida de un PRNG. En general, se requiere un análisis matemático cuidadoso para tener la certeza de que un PRNG genera números lo suficientemente cercanos a la aleatoriedad para adaptarse al uso previsto. John von Neumann advirtió sobre la mala interpretación de un PRNG como un generador verdaderamente aleatorio, bromeando diciendo que "Cualquiera que considere métodos aritméticos para producir dígitos aleatorios está, por supuesto, en un estado de pecado".

Posibles problemas

En la práctica, la salida de muchos PRNG comunes presenta artefactos que hacen que no superen las pruebas estadísticas de detección de patrones. Éstos incluyen:

• Períodos más cortos de lo esperado para algunos estados de semillas (como los estados de semillas pueden llamarse "mojados" en este contexto);
• Falta de uniformidad de distribución para grandes cantidades de números generados;
• Correlación de valores sucesivos;
• Distribución dimensional deficiente de la secuencia de salida;
• Las distancias entre donde ocurren ciertos valores se distribuyen de manera diferente a las de una distribución de secuencia aleatoria.

Los defectos exhibidos por los PRNG defectuosos van desde imperceptibles (y desconocidos) hasta muy obvios. Un ejemplo fue el algoritmo de números aleatorios RANDU utilizado durante décadas en las computadoras centrales. Tenía serias fallas, pero su inadecuación pasó desapercibida durante mucho tiempo.

En muchos campos, el trabajo de investigación anterior al siglo XXI que se basaba en la selección aleatoria o en simulaciones de Monte Carlo, o que de otra manera dependía de los PRNG, era mucho menos confiable que lo ideal como resultado del uso de PRNG de mala calidad. Incluso hoy en día, a veces se requiere precaución, como lo ilustra la siguiente advertencia en la Enciclopedia internacional de ciencia estadística (2010).

La lista de generadores ampliamente utilizados que deben ser descartados es mucho más larga [que la lista de buenos generadores]. No confíe ciegamente en los proveedores de software. Revise el RNG predeterminado de su software favorito y esté listo para reemplazarlo si es necesario. Esta última recomendación se ha formulado una y otra vez en los últimos 40 años. Tal vez sorprendentemente, sigue siendo tan relevante hoy como lo fue hace 40 años.

Como ilustración, considere el lenguaje de programación ampliamente utilizado Java. Hasta 2020, Java todavía dependía de un generador lineal congruente (LCG) para su PRNG, que es de baja calidad (ver más abajo). El soporte de Java se actualizó con Java 17.

Un PRNG bien conocido para evitar problemas importantes y seguir ejecutándose con bastante rapidez es el Mersenne Twister (discutido a continuación), que se publicó en 1998. Otros PRNG de mayor calidad, tanto en términos de rendimiento computacional como estadístico, se desarrollaron antes y después de esta fecha; estos se pueden identificar en la Lista de generadores de números pseudoaleatorios.

Generadores basados en recurrencias lineales

En la segunda mitad del siglo XX, la clase estándar de algoritmos utilizados para los PRNG comprendía generadores lineales congruentes. Se sabía que la calidad de los LCG era inadecuada, pero no se disponía de mejores métodos. Press et al. (2007) describieron el resultado así: “Si todos los artículos científicos cuyos resultados están en duda debido a [LCG y relacionados] desaparecieran de los estantes de las bibliotecas, habría un espacio en cada estante del tamaño de un puño. "

Un gran avance en la construcción de generadores pseudoaleatorios fue la introducción de técnicas basadas en recurrencias lineales en el campo de dos elementos; tales generadores están relacionados con registros de desplazamiento de retroalimentación lineal.

La invención de 1997 del Mersenne Twister, en particular, evitó muchos de los problemas con los generadores anteriores. El Mersenne Twister tiene un período de 2^{19 937}−1 iteraciones (≈4,3×10⁶⁰⁰¹), se ha demostrado que está equidistribuido en (hasta) 623 dimensiones (para valores de 32 bits), y en el momento de su introducción funcionaba más rápido que otros generadores estadísticamente razonables.

En 2003, George Marsaglia presentó la familia de generadores xorshift, nuevamente basados en una recurrencia lineal. Dichos generadores son extremadamente rápidos y, combinados con una operación no lineal, pasan fuertes pruebas estadísticas.

En 2006, se desarrolló la familia de generadores WELL. Los generadores WELL de alguna manera mejoran la calidad del Mersenne Twister, que tiene un espacio de estado demasiado grande y una recuperación muy lenta de los espacios de estado con una gran cantidad de ceros.

PRNG criptográficos

Un PRNG adecuado para aplicaciones criptográficas se denomina PRNG criptográficamente seguro (CSPRNG). Un requisito para un CSPRNG es que un adversario que no conozca la semilla solo tenga una ventaja insignificante para distinguir la secuencia de salida del generador de una secuencia aleatoria. En otras palabras, mientras que un PRNG solo debe pasar ciertas pruebas estadísticas, un CSPRNG debe pasar todas las pruebas estadísticas que están restringidas al tiempo polinomial en el tamaño de la semilla. Aunque una prueba de esta propiedad está más allá del estado actual del arte de la teoría de la complejidad computacional, se puede proporcionar una fuerte evidencia al reducir el CSPRNG a un problema que se supone que es difícil, como la factorización de enteros. En general, pueden ser necesarios años de revisión antes de que un algoritmo pueda certificarse como CSPRNG.

Algunas clases de CSPRNG incluyen lo siguiente:

• ciferos de corriente
• bloque cifers funcionando en modo de retroalimentación de contador o salida
• PRNGs que han sido diseñados específicamente para ser criptográficamente seguros, como Microsoft Cryptographic Application Programming Interface function CryptGenRandom, el algoritmo Yarrow (incorporado en Mac OS X y FreeBSD), y Fortuna
• combinación de PRNGs que intentan combinar varios algoritmos primitivos PRNG con el objetivo de eliminar cualquier no aleatoria detectable
• diseños especiales basados en hipótesis de dureza matemática: ejemplos incluyen los Generador Micali-Schnorr, función de seudorandad Naor-Reingold y el algoritmo Blum Blum Shub, que proporcionan una prueba de seguridad fuerte (estos algoritmos son bastante lentos en comparación con las construcciones tradicionales, y poco práctico para muchas aplicaciones)
• PRNGs genéricos: mientras se ha demostrado que un PRNG seguro (criptográfico) se puede construir genéricamente de cualquier función de un solo sentido, esta construcción genérica es extremadamente lenta en la práctica, así que es principalmente de interés teórico.

Se ha demostrado que es probable que la NSA haya insertado una puerta trasera asimétrica en el generador de números pseudoaleatorios Dual_EC_DRBG certificado por el NIST.

La mayoría de los algoritmos PRNG producen secuencias que se distribuyen uniformemente mediante cualquiera de varias pruebas. Es una pregunta abierta, y fundamental para la teoría y la práctica de la criptografía, si hay alguna forma de distinguir la salida de un PRNG de alta calidad de una secuencia verdaderamente aleatoria. En esta configuración, el distinguidor sabe que se usó el algoritmo PRNG conocido (pero no el estado con el que se inicializó) o se usó un algoritmo verdaderamente aleatorio, y tiene que distinguir entre los dos. La seguridad de la mayoría de los algoritmos y protocolos criptográficos que utilizan PRNG se basa en la suposición de que no es factible distinguir el uso de un PRNG adecuado del uso de una secuencia verdaderamente aleatoria. Los ejemplos más simples de esta dependencia son los cifrados de flujo, que (en la mayoría de los casos) funcionan mediante la combinación or-exclusiva del texto sin formato de un mensaje con la salida de un PRNG, lo que produce texto cifrado. El diseño de PRNG criptográficamente adecuados es extremadamente difícil porque deben cumplir criterios adicionales. El tamaño de su período es un factor importante en la idoneidad criptográfica de un PRNG, pero no el único.

Criterios de evaluación BSI

La Oficina Federal Alemana para la Seguridad de la Información (en alemán: Bundesamt für Sicherheit in der Informationstechnik, BSI) ha establecido cuatro criterios para la calidad de los generadores de números aleatorios deterministas. Se resumen aquí:

• K1 – Debe haber una alta probabilidad de que las secuencias generadas de números aleatorios sean diferentes entre sí.
• K2 – Una secuencia de números es indistinguible de números "verdaderamente aleatorios" de acuerdo a pruebas estadísticas especificadas. Las pruebas son monobit test (igual número de uno y ceros en la secuencia), poker prueba (un caso especial de la prueba de la chi-squared), carreras prueba (cuenta la frecuencia de las carreras de varias longitudes), longruns prueba (comprueba si existe una carrera de longitud 34 o mayor en 20 000 bits de la secuencia)—tanto desde BSI como NIST, como autocorrelación Prueba. En esencia, estos requisitos son una prueba de cuán bien un bit secuencia: tiene ceros y otros igualmente a menudo; después de una secuencia de n ceros (o unos), el siguiente bit a uno (o cero) con probabilidad de una mitad; y cualquier subsecuencia seleccionada no contiene información sobre el siguiente elemento(s) en la secuencia.
• K3 – Debe ser imposible para un atacante (para todos los fines prácticos) calcular, o adivinar, de cualquier subsequencia dada, cualquier valor anterior o futuro en la secuencia, ni ningún estado interno del generador.
• K4 – Debe ser imposible, para todos los propósitos prácticos, que un atacante calcule, o adivine desde un estado interno del generador, cualquier número anterior en la secuencia o cualquier estado interno anterior del generador.

Para aplicaciones criptográficas, solo se aceptan generadores que cumplan con los estándares K3 o K4.

Definición matemática

Dado:

• P{displaystyle P} – una distribución de probabilidad en ()R,B){displaystyle left(mathbb {R}{mathfrak {B}right)} (donde) B{displaystyle {Mathfrak}} es el estándar Borel en la línea real)
• F{displaystyle {Mathfrak}} – una colección no vacía de conjuntos Borel F⊆ ⊆ B{displaystyle {Mathfrak {}subseteq {Mathfrak}, por ejemplo. F={}()− − JUEGO JUEGO ,t]:t▪ ▪ R}{displaystyle {mathfrak}=leftleft(-inftytright):tin #. Si F{displaystyle {Mathfrak}} no se especifica, puede ser B{displaystyle {Mathfrak}} o {}()− − JUEGO JUEGO ,t]:t▪ ▪ R}{displaystyle left{left(-inftytright): tin mathbb {R} right}, dependiendo del contexto.
• A⊆ ⊆ R{displaystyle Asubseteq mathbb {R} – un conjunto no vacío (no necesariamente un conjunto Borel). A menudo A{displaystyle A} es un conjunto entre P{displaystyle P}'s soporte y su interior; por ejemplo, si P{displaystyle P} es la distribución uniforme en el intervalo ()0,1]{displaystyle left(0,1right)}, A{displaystyle A} podría ser ()0,1]{displaystyle left(0,1right)}. Si A{displaystyle A} no se especifica, se supone que es un conjunto contenido en el apoyo de P{displaystyle P} y que contiene su interior, dependiendo del contexto.

Llamamos a una función f:N1→ → R{displaystyle f:mathbb {N} _{1}rightarrow mathbb {R} (donde) N1={}1,2,3,...... }{displaystyle mathbb {N} _{1}=left{1,2,3,dots right}} es el conjunto de enteros positivos) a generador de números pseudo-aleatorios para P{displaystyle P} dado F{displaystyle {Mathfrak}} tomar valores en A{displaystyle A} si y sólo si:

• f()N1)⊆ ⊆ A{displaystyle fleft(mathbb Subseteq A.
• 0quad exists Nin mathbb {N} _{1}quad forall ngeq N,quad left|{frac {#left{iin left{1,2,dotsnright}:f(i)in Eright}}{n}}-P(E)right|О О E▪ ▪ FО О ε ε ■0∃ ∃ N▪ ▪ N1О О n≥ ≥ N,Silencio# # {}i▪ ▪ {}1,2,...... ,n}:f()i)▪ ▪ E}n− − P()E)Silencio.ε ε {displaystyle forall Ein {Mathfrak {F}quad forall varepsilon √0quad exists Nin mathbb {N} _{1}quad forall ngeq N,quad left sometida{frac {#left{iin left{1,2,dotsnright}:f(i)in Eright}{n}}}}} {e)derech]derech}0quad exists Nin mathbb {N} _{1}quad forall ngeq N,quad left|{frac {#left{iin left{1,2,dotsnright}:f(i)in Eright}}{n}}-P(E)right|

()# # S{displaystyle {cHFF} denota el número de elementos en el conjunto finito S{displaystyle S..)

Se puede demostrar que si f{displaystyle f} es un generador de números pseudo-aleatorios para la distribución uniforme en ()0,1){displaystyle left(0,1right)} y si F{displaystyle F} es el CDF de alguna distribución de probabilidad dada P{displaystyle P}, entonces FAlternativa Alternativa ∘ ∘ f{displaystyle F^{*}circ f} es un generador número pseudo-aleatorio para P{displaystyle P}, donde FAlternativa Alternativa :()0,1)→ → R{displaystyle F^{*}:left(0,1right)rightarrow mathbb {R} es el percentil de P{displaystyle P}, es decir. FAlternativa Alternativa ()x):=inf{}t▪ ▪ R:x≤ ≤ F()t)}{displaystyle F^{*}(x):=inf left{tin mathbb {R}:xleq F(t)rightright}. Intuitivamente, una distribución arbitraria se puede simular a partir de una simulación de la distribución uniforme estándar.

Aproximaciones tempranas

Un PRNG temprano basado en computadora, sugerido por John von Neumann en 1946, se conoce como el método del cuadrado medio. El algoritmo es el siguiente: tome cualquier número, elévelo al cuadrado, elimine los dígitos del medio del número resultante como el "número aleatorio", luego use ese número como semilla para la próxima iteración. Por ejemplo, elevar al cuadrado el número "1111" produce "1234321", que se puede escribir como "01234321", un número de 8 dígitos que es el cuadrado de un número de 4 dígitos. Esto da "2343" como el "aleatorio" número. Repitiendo este procedimiento da "4896" como el siguiente resultado, y así sucesivamente. Von Neumann usó números de 10 dígitos, pero el proceso fue el mismo.

Un problema con el "cuadrado del medio" El método es que todas las secuencias finalmente se repiten, algunas muy rápidamente, como "0000". Von Neumann estaba al tanto de esto, pero encontró que el enfoque era suficiente para sus propósitos y le preocupaba que las "soluciones" simplemente ocultaría los errores en lugar de eliminarlos.

Von Neumann consideró que los generadores de números aleatorios de hardware no eran adecuados porque, si no registraban la salida generada, no podían probarse posteriormente para detectar errores. Si registraran su salida, agotarían las memorias limitadas de la computadora disponibles en ese momento y, por lo tanto, la capacidad de la computadora para leer y escribir números. Si los números estuvieran escritos en tarjetas, tomaría mucho más tiempo escribirlos y leerlos. En la computadora ENIAC que estaba usando, el "cuadrado del medio" El método generó números a una velocidad cien veces más rápida que la lectura de números de tarjetas perforadas.

Desde entonces, el método del cuadrado medio ha sido reemplazado por generadores más elaborados.

Una innovación reciente es combinar el cuadrado central con una secuencia de Weyl. Este método produce una salida de alta calidad durante un largo período (consulte el método del cuadrado central).

Implementación

El siguiente es un ejemplo PRNG muy simple escrito en JavaScript. Utiliza una secuencia de multiplicaciones para generar un valor aparentemente aleatorio que luego se normaliza para estar en el rango de 0 a 1. En este ejemplo, 15485863 es el número primo 1 000 000 y 2038074743 el 100 000 000.

clase PRNG{} constructor()semillas) {} //Volverá en el rango 0 a 1 si seed √≥= 0 y -1 a 0 si seed 0 se hizo 0. esto.semillas = semillas; } Siguiente() {} esto.semillas++; Deja a = esto.semillas * 15485863; retorno ()a * a * a % 2038074743) / 2038074743; }}

El ejemplo devuelve resultados muy similares a la función Math.random() de JavaScript.

Generadores no uniformes

Los números seleccionados de una distribución de probabilidad no uniforme se pueden generar utilizando una distribución uniforme PRNG y una función que relaciona las dos distribuciones.

Primero, se necesita la función de distribución acumulativa F()b){displaystyle F(b)} de la distribución de objetivos f()b){displaystyle f(b)}:

F()b)=∫ ∫ − − JUEGO JUEGO bf()b.)db.{displaystyle F(b)=int _{-infty

Note que 0=F()− − JUEGO JUEGO )≤ ≤ F()b)≤ ≤ F()JUEGO JUEGO )=1{displaystyle 0=F(-infty)leq F(b)leq F(infty)=1}. Usando un número aleatorio c de una distribución uniforme como la densidad de probabilidad a "pasar por", obtenemos

F()b)=c{displaystyle F(b)=c}

para que

b=F− − 1()c){displaystyle b=F^{-1}(c)}

es un número seleccionado al azar de la distribución f()b){displaystyle f(b)}. Esto se basa en el muestreo de transformación inversa.

Por ejemplo, el inverso de la distribución Gausiana acumulativa er− − 1⁡ ⁡ ()x){displaystyle operatorname {erf} ^{-1}(x)} con un uniforme PRNG ideal con rango (0, 1) como entrada x{displaystyle x} produciría una secuencia de valores (positivos solamente) con una distribución Gaussiana; sin embargo

• Al utilizar representaciones de números prácticos, los infinitos "tails" de la distribución tienen que ser truncados a valores finitos.
• Recalculación repetitiva de er− − 1⁡ ⁡ ()x){displaystyle operatorname {erf} ^{-1}(x)} debe reducirse por medios como el algoritmo ziggurat para una generación más rápida.

Se aplican consideraciones similares a la generación de otras distribuciones no uniformes, como Rayleigh y Poisson.