¿Qué hace que un generador pseudoaleatorio sea de alta calidad?

8

Leyendo esta respuesta a esta pregunta SO: ¿Por qué no combinamos generadores de números aleatorios? , habla de

PRNG (generador de números pseudoaleatorios) de muy alta calidad

así que me pregunto qué constituye un PRNG de alta calidad, supongo que puedes resumirlo como "más aleatorio", pero

  • Pregunta 1: ¿Qué cualidades de un PRNG se usan para describir cuán 'aleatorio' o 'bueno' es?

  • Pregunta 2: Si tiene un PRNG de 'mala calidad', ¿hay alguna manera de mejorarlo?

randomness pseudo-random-generators random-number-generator Jose
fuente
Relevante stackoverflow.com/questions/2130621/…
adrianN
2
También debe distinguir los PRNG mundanos de los RNG criptográficamente seguros.
adrianN
1
Un PRNG es "mejor" si es más difícil distinguir su salida de bits completamente aleatorios.
Yuval Filmus

Respuestas:

9

Existen varios criterios para la calidad de un PRNG:

  • Que rapido es. Esto incluye qué tan rápido es configurarlo y qué tan rápido es producir un solo bit (amortizado).
  • Qué difícil es adivinar el siguiente bit dados todos los bits anteriores.
  • Qué difícil es distinguir entre la salida del PRNG y los bits verdaderamente aleatorios.

Los dos últimos criterios están fuertemente relacionados.

Si tiene un PRNG de mala calidad, a menudo puede mejorarlo mediante la amplificación de dureza . Tome varias copias del PRNG (usando diferentes claves aleatorias) y XOR juntas. En muchos casos (aunque no en todos) esto mejorará significativamente su calidad.

Yuval Filmus
fuente
Otra pregunta más: ¿por qué usar un PRNG que causará la misma secuencia si se usa la misma semilla dos veces, y no solo una nueva semilla (reloj de la CPU, por ejemplo) cada vez que se necesita un nuevo número aleatorio? ¿No sería este enfoque más aleatorio?
José
2
@Jose Esto es por diseño. En muchos casos, desea poder generar exactamente la misma secuencia muchas veces. Dos ejemplos son los experimentos de Monte Carlo (que deberían ser repetibles) y la criptografía (donde queremos que dos usuarios posean la misma secuencia aleatoria, utilizada como clave).
Yuval Filmus
Los experimentos de Monte Carlo rara vez necesitan un PRNG criptográfico.
Xavier Combelle
2

Hay consideraciones prácticas: ¿Qué tan fácil de usar? ¿Qué rápido? ¿Qué tan fácil es producir una secuencia diferente de números aleatorios? ¿Qué tan fácil es reproducir los números aleatorios (por ejemplo, si generó 10 mil millones de números aleatorios, ¿puede generar exactamente los mismos 10 mil millones de números aleatorios nuevamente?)

La gran pregunta: ¿los números generados se comportan como una secuencia de números aleatorios? El primer PRNG que utilicé tenía la extraña propiedad de que de dos valores consecutivos, el segundo era más grande con una probabilidad de alrededor de 0.6. No muy al azar. Por lo tanto, puede ejecutar todo tipo de pruebas estadísticas y verificar si su generador de números aleatorios se comporta de manera aleatoria. Cuanto más se comporta como al azar, mejor.

Y luego viene la aleatoriedad criptográfica. Si le doy los últimos n números aleatorios, y completo conocimiento de cómo se comporta el generador de números aleatorios, ¿puede predecir el próximo número aleatorio? Si es así, eso lo hace inadecuado en situaciones en las que tienes adversarios.

gnasher729
fuente
0

Agregaría una distribución uniforme a la lista de cualidades deseadas.

Maciek Łoziński
fuente
En general, se entiende que un PRNG genera una distribución uniforme (o casi).
vonbrand