Generador de números aleatorios basado en contador

Un generador de números aleatorios basado en contador ( CBRNG , también conocido como generador de números pseudoaleatorios basado en contador o CBPRNG) es un tipo de generador de números pseudoaleatorios que utiliza únicamente un contador entero como estado interno. Generalmente se utilizan para generar números pseudoaleatorios para grandes cálculos paralelos.

Podemos pensar en un generador de números pseudoaleatorios (PRNG, por sus siglas en inglés) como una función que transforma una serie de bits, conocidos como estado , en un nuevo estado y un número aleatorio.

Es decir, dada una función PRNG y un estado inicial${\displaystyle \mathrm {estado} _ {0}}$Podemos utilizar repetidamente el generador de números pseudoaleatorios para generar una secuencia de estados y números aleatorios.

$${\displaystyle {\begin{alineado}\mathrm {PRNG} (\mathrm {estado} _{0})&=\mathrm {estado} _{1},\ \mathrm {num} _{1}\\\mathrm {PRNG} (\mathrm {estado} _{1})&=\mathrm {estado} _{2},\ \mathrm {num} _{2}\\\mathrm {PRNG} (\mathrm {estado} _{2})&=\mathrm {estado} _{3},\ \mathrm {num} _{3}\\\mathrm {PRNG} (\mathrm {estado} _{3})&=\ldots \end{aligned}}}$$

En algunos PRNG, como el Mersenne Twister , el estado es grande, más de 2048 bytes. En otros PRNG, como xorshift ,${\displaystyle \mathrm {estado} _{i}}$y${\displaystyle \mathrm {num} _ {i}}$son uno y lo mismo (y por lo tanto el estado es pequeño, solo 4, 8 o 16 bytes, dependiendo del tamaño de los números que se generan). Pero en ambos casos, y de hecho en la mayoría de los PRNG tradicionales, el estado evoluciona de forma impredecible, por lo que si desea calcular un en particular${\displaystyle \mathrm {estado} _{i}}$dado un estado inicial${\displaystyle \mathrm {estado} _ {0}}$, tienes que calcular${\displaystyle \mathrm {estado} _ {1}}$,${\displaystyle \mathrm {estado} _ {2}}$y así sucesivamente, ejecutando el generador de números pseudoaleatorios (PRNG)${\displaystyle i}$veces.

Estos algoritmos son inherentemente secuenciales y no se prestan a ejecutarse en máquinas paralelas como CPU multinúcleo y GPU .

En cambio, un generador de números aleatorios basado en contadores (CBRNG) es un PRNG donde el estado "evoluciona" de una manera particularmente simple:${\displaystyle \mathrm {estado} _{i}=i}$De esta forma, puedes generar cada número de forma independiente, sin conocer el resultado de la llamada anterior al generador de números pseudoaleatorios.

Esta propiedad facilita la ejecución de un CBRNG en múltiples hilos de CPU o en una GPU. Por ejemplo, para generar${\displaystyle n}$números aleatorios en una GPU, podría generar${\displaystyle n}$hilos y tener el${\displaystyle i}$th hilo calcular${\displaystyle \mathrm {PRNG} (i)}$.

Algunos generadores de números aleatorios basados ​​en códigos (CBRNG) se basan en versiones de menor seguridad de cifrados por bloques . A continuación, explicamos cómo funciona esto.

Al utilizar un cifrado de bloques criptográfico en modo contador , se genera una serie de bloques de bits aleatorios.${\displaystyle i}$El bloque se calcula cifrando el número${\displaystyle i}$utilizando la clave de cifrado${\displaystyle k}$:${\displaystyle \mathrm {Bloque} _{i}=E(i,k)}$.

Esto es similar a un CBRNG, donde se calcula el${\displaystyle i}$el número aleatorio como${\displaystyle \mathrm {PRNG} (i)}$De hecho, cualquier cifrado de bloques puede usarse como un generador de números aleatorios de bloques; simplemente deje que${\displaystyle \mathrm {PRNG} (i)=E(i,\mathrm {semilla} )}$¡

Esto proporciona una fuente de aleatoriedad robusta y criptográficamente segura . Sin embargo, los generadores de números pseudoaleatorios criptográficamente seguros tienden a ser lentos en comparación con los generadores de números pseudoaleatorios inseguros, y en la práctica, muchos usos de los números aleatorios no requieren este grado de seguridad.

En 2011, Salmon et al. de DE Shaw Research presentaron ^{[ 1 ]} dos CBRNG basados ​​en versiones de fuerza reducida de cifrados de bloques.

• Threefry utiliza una versión de menor seguridad del cifrado de bloques Threefish . (Los peces jóvenes se conocen como " alevines ").

• ARS utiliza una versión de menor seguridad del cifrado por bloques AES . ("ARS" es un juego de palabras con "AES"; "AES" significa "estándar de cifrado avanzado" y "ARS" significa "sistema de aleatorización avanzado" ^{[ 2 ]} ).

ARS se utiliza en versiones recientes de la biblioteca Math Kernel de Intel ^{[ 3 ]} y obtiene un buen rendimiento al utilizar instrucciones del conjunto de instrucciones AES-NI , que aceleran específicamente el cifrado AES.

El código que implementa Threefry, ARS y Philox (ver más abajo) está disponible a través de los autores. ^{[ 4 ]}

Además de Threefry y ARS, Salmon et al. describieron un tercer PRNG basado en contadores, Philox , ^{[ 1 ]} basado en multiplicaciones amplias; por ejemplo, multiplicar dos números de 32 bits y producir un número de 64 bits, o multiplicar dos números de 64 bits y producir un número de 128 bits.

En 2020, Philox era popular en CPU y GPU. En las GPU, la biblioteca cuRAND de nVidia ^{[ 5 ]} y TensorFlow ^{[ 6 ]} ofrecen implementaciones de Philox. En las CPU, MKL de Intel ofrece una implementación.

Un nuevo CBRNG basado en la multiplicación es el Squares RNG. ^{[ 7 ]} Este generador pasa pruebas rigurosas de aleatoriedad ^{[ 8 ]} y es considerablemente más rápido que Philox.