¿Existen generadores de números aleatorios sin estado?

Question

¿Hay alguna diferencia entre generar múltiples números usando un solo generador de números aleatorios (RNG) versus generar un número por generador y descartarlo? ¿Ambas implementaciones generan números que son igualmente aleatorios? ¿Hay alguna diferencia entre los RNG normales y los RNG seguros para esto?

Tengo una aplicación web que se supone que genera una lista de números aleatorios en nombre de los clientes. Es decir, los números deberían parecer aleatorios desde el punto de vista de cada cliente. ¿Significa esto que necesito retener un RNG aleatorio por sesión de cliente? ¿O puedo compartir un solo RNG en todas las sesiones? ¿O puedo crear y descartar un RNG por solicitud?

ACTUALIZACIÓN: Esta pregunta está relacionada con Is a subset of a random sequence also random?

Answer 1

Un generador de números aleatorios tiene un estado, eso es realmente una característica necesaria. El siguiente número "aleatorio" es una función del número anterior y la semilla/estado. Los puristas los llaman generadores de números pseudoaleatorios. Los números pasarán pruebas estadísticas de aleatoriedad, pero en realidad no son aleatorios.

La secuencia de valores aleatorios es finita y se repite.

Imagine que un generador de números aleatorios mezcla una colección de números y los distribuye en orden aleatorio. La semilla se usa para "mezclar" los números. Una vez que se establece la semilla, la secuencia de números es fija y muy difícil de predecir. Algunas semillas se repetirán antes que otras.

La mayoría de los generadores tienen un período que es suficientemente largo para que nadie lo note repitiendo. Un generador de números aleatorios de 48 bits producirá varios cientos de miles de millones de números aleatorios antes de que se repita, con (AFAIK) cualquier valor de inicialización de 32 bits.

Un generador dará solo generará valores aleatorios cuando le dé una sola semilla y permita que arroje valores. Si cambia las semillas, los números generados con el nuevo valor inicial pueden no parecer aleatorios en comparación con los valores generados por la semilla anterior: todas las apuestas se desactivan cuando se cambian las semillas. Entonces no.

Un enfoque sensato es tener un generador y "repartir" los números entre sus diferentes clientes. No te metas con crear y descartar generadores. No te metas con el cambio de semillas.

Sobre todo, nunca intente escribir su propio generador de números aleatorios. Los generadores incorporados en la mayoría de las bibliotecas de idiomas son realmente buenos. Especialmente los modernos que usan más de 32 bits.

Algunas distribuciones Linux tienen un dispositivo /dev/random y /dev/urandom. Puede leerlos una vez para sembrar el generador de números aleatorios de su aplicación. Estos tienen más o menos valores aleatorios, pero funcionan mediante la "acumulación de ruido" de eventos aleatorios del sistema. Úselos con moderación para que haya muchos eventos aleatorios entre los usos.

Answer 2

Bueno, siempre y cuando se siembran manera diferente cada vez que están creados, entonces no, no creo que no habría ninguna diferencia; sin embargo, si dependía de algo así como el tiempo, entonces probablemente no serían uniformes, debido a la semilla sesgada.

Answer 3

Recomendaría usar un único generador varias veces. Hasta donde yo sé, todos los generadores tienen un estado. Cuando siembras un generador, estableces su estado en algo basado en la semilla. Si sigues generando otros nuevos, es probable que las semillas que elijas no sean tan aleatorias como los números generados al usar solo un generador.

Esto es especialmente cierto con la mayoría de los generadores que he usado, que utilizan el tiempo actual en milisegundos como semilla.

Answer 4

Si crea un RNG y genera un solo número aleatorio a partir de él, entonces descarte el RNG, el número generado es solo tan aleatorio como el que se usó para iniciar el RNG.

Sería mucho mejor crear un único RNG y sacar muchos números de él.

Answer 5

Por lo general, es mejor crear un único PRNG y extraer varios valores del mismo. La creación de instancias múltiples significa que debe asegurarse de que las semillas de las instancias estén garantizadas como únicas, lo que requerirá incorporar información específica de la instancia.

Como un lado, hay mejores generadores de números aleatorios "verdaderos", pero generalmente requieren hardware especializado que hace cosas como derivar datos aleatorios de la varianza de la señal eléctrica dentro de la computadora. A menos que esté realmente preocupado por eso, diría que los Pseudo generadores de números aleatorios integrados en las bibliotecas de idiomas y/o sistema operativo son probablemente suficientes, siempre y cuando el valor inicial no sea fácilmente predecible.

Answer 6

Como ya se ha dicho, es mucho mejor sembrar el PRNG una vez y volver a utilizarlo. Un PRNG seguro es simplemente uno que es adecuado para aplicaciones criptográficas. La única manera en que la nueva siembra en cada ocasión dará resultados razonablemente aleatorios es cuando proviene de una fuente genuinamente aleatoria del "mundo real", es decir, hardware especializado. Incluso entonces, es posible que la fuente esté sesgada y que teóricamente sea mejor usar el mismo PRNG.

Answer 7

Normalmente sembrar un nuevo estado toma bastante tiempo para un PRNG serio, y hacer nuevos cada vez no ayudará mucho. El único caso en el que podría pensar que podría necesitar más de un PRNG es para diferentes sistemas, por ejemplo, en un juego de casino tiene un generador para barajar cartas y otro para generar comentarios hechos por los personajes de control de computadora, de esta manera REALMENTE los usuarios dedicados no pueden adivinar los resultados en función de los comportamientos de los personajes.

Una buena solución para la siembra es usar this (Random.org), proporcionan números aleatorios generados por el ruido atmosférico de forma gratuita.Podría ser una mejor fuente de siembra que usar el tiempo.

Editar: En su caso, definitivamente usaría un PRNG por cliente, solo por buenos estándares de programación. De todos modos, si comparte un PRNG entre los clientes, seguirá proporcionando valores pseudoaleatorios a cada uno, de una calidad igual a la calidad de su PRNG. Entonces, esa es una opción viable, pero parece una mala política para programar

Answer 8

Vale la pena mencionar que Haskell es un lenguaje que intenta eliminar completamente el estado mutable. Con el fin de conciliar este objetivo con requisitos exigentes como IO (que requiere alguna forma de mutabilidad), las mónadas se deben usar para enhebrar el estado de un cálculo al siguiente. De esta forma, Haskell implementa su generador de números pseudoaleatorios. Estrictamente hablando, la generación de números aleatorios es una operación inherentemente con estado, pero Haskell puede ocultar este hecho al mover la "mutación" del estado a la operación de vinculación (>>=).

Esto probablemente suene un poco abstracto, y realmente no responde completamente su pregunta, pero creo que sigue siendo aplicable. Desde un punto de vista teórico, es imposible trabajar con un RNG sin involucrar el estado. De todos modos, hay técnicas que se pueden usar para mitigar esta interacción y hacer que aparezca como si toda la operación fuera de naturaleza sin estado.

Answer 9

Generadores de números aleatorios basados ​​en hardware, verdaderos [1] son ​​posibles, pero no triviales y, a menudo tienen tasas medias bajas. La disponibilidad también puede ser un problema [2].Buscar en Google "ruido de disparo" o "deterioro radioactivo" en combinación con "generador de números aleatorios" debería devolver algunos resultados.

Estos sistemas no necesitan mantener el estado. Probablemente no sea lo que estabas buscando.

Como señalaron otros, los sistemas de software son solo pseudoaleatorios, y deben mantenerse en estado.

Un compromiso es utilizar un RNG basado en hardware para proporcionar un conjunto de entropía (estado almacenado) que está disponible para inicializar un PRNG. Esto se hace de manera bastante explícita en la implementación de Linux de/dev/random [3] y/dev/urandom [4].

Estos son algunos argumentos acerca de cuán aleatorias son realmente las entradas predeterminadas para/dev/random entropy pool.

---

Notas al pie:

1. modulo ningún problema con nuestra comprensión de la física
2. porque está a la espera de un proceso aleatorio
3. /dev/características aleatorias acceso directo a la piscina entropía cabeza de serie de varias fuentes que se cree que son reales o casi aleatorias, y bloquea cuando la entropía se agota
4. /dev/urandom es como/dev/random, pero cuando se agota la entopia una criptografía se emplea Raphic hash, lo que hace que la entropía sea efectivamente un PRNG con estado

Answer 10

El uso de un PRNG seguro depende de su aplicación. ¿Para qué se usan los números aleatorios? Si tienen algún valor real (por ejemplo, algo relacionado criptográficamente), no querrás usar menos.

PRNG seguros son mucho más lentas, y pueden requerir bibliotecas de hacer la operación de precisión arbitraria, y la prueba de primalidad, etc, etc ...