¿Existen generadores de números aleatorios sin estado?

Question

¿Hay alguna diferencia entre generar múltiples números usando un único 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 deben parecer aleatorios desde el punto de vista de cada cliente. ¿Significa esto que necesito retener un RNG aleatorio separado 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 ¿Un subconjunto de una secuencia aleatoria también es aleatorio?

Answer 1

Un generador de números aleatorios tiene un estado, que en realidad es una característica necesaria. El siguiente "aleatorio" número 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 no son, en realidad, aleatorios.

La secuencia de valores aleatorios es finita y se repite.

Piense en un generador de números aleatorios como barajar una colección de números y luego repartirlos en un orden aleatorio. La semilla se usa para barajar. 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 lo suficientemente largo como para que nadie se dé cuenta de que se repite. Un generador de números aleatorios de 48 bits producirá varios cientos de billones de números aleatorios antes de que se repita, con (AFAIK) cualquier valor inicial de 32 bits.

Un generador solo generará valores similares al azar cuando le dé una sola semilla y deje que arroje valores. Si cambia las semillas, entonces los números generados con el nuevo valor de la semilla pueden no aparecer al azar en comparación con los valores generados por la semilla anterior; todas las apuestas se cancelan cuando cambia las semillas. Entonces no lo hagas.

Un enfoque sólido es tener un generador y "tratar" los números a sus distintos clientes. No te metas con crear y descartar generadores. No te metas con el cambio de semillas.

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

Algunas distribuciones de 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 valores más o menos aleatorios, pero funcionan "recogiendo ruido". de eventos aleatorios del sistema. Úselos con moderación para que haya muchos eventos aleatorios entre usos.

Answer 2

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

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

Answer 3

Generadores de números aleatorios verdaderos basados ??en hardware [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 "desintegración radiactiva" en combinación con " generador de números aleatorios " debería devolver algunos éxitos.

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

Como han señalado otros, los sistemas de software son solo pseudoaleatorios y deben mantener el estado.

Un compromiso es utilizar un RNG basado en hardware para proporcionar un grupo 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 sobre cuán aleatorias son realmente las entradas predeterminadas al grupo de entropía / dev / random.

---

Notas al pie:

1. modula cualquier problema con nuestra comprensión de la física
2. porque estás esperando un proceso aleatorio
3. / dev / random presenta acceso directo al grupo de entropía sembrado 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 la entopia se agota, se emplea un hash criptográfico que hace que el grupo de entropía sea efectivamente un PRNG con estado

Answer 4

Si crea un RNG y genera un único número aleatorio a partir de él, descarte el RNG, el número generado es tan aleatorio como la semilla utilizada para iniciar el RNG.

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

Answer 5

Como la gente ya ha dicho, es mucho mejor sembrar el PRNG una vez y reutilizarlo. Un PRNG seguro es simplemente uno que es adecuado para aplicaciones criptográficas. La única manera de volver a sembrar cada vez dará resultados razonablemente aleatorios es de donde proviene un mundo real genuinamente aleatorio. fuente - es decir, hardware especializado. Incluso entonces, es posible que la fuente esté sesgada y, en teoría, será mejor usar el mismo PRNG.

Answer 6

Normalmente, sembrar un nuevo estado lleva bastante tiempo para un PRNG serio, y hacer nuevos cada vez realmente no ayudará mucho. El único caso en el que puedo pensar en dónde podrías querer más de un PRNG es para diferentes sistemas, por ejemplo, en un juego de casino tienes un generador para barajar cartas y otro para generar comentarios hechos por los personajes de control de la computadora, de esta manera REALMENTE dedicado los usuarios 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) , suministran al azar números 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, si no fuera por otra razón que 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 la programación

Answer 7

Vale la pena mencionar que Haskell es un lenguaje que intenta eliminar por completo el estado mutable. Para conciliar este objetivo con requisitos estrictos como IO (que requiere alguna forma de mutabilidad), las mónadas deben usarse para enhebrar el estado de un cálculo al siguiente. De esta manera, Haskell implementa su generador de números pseudoaleatorios. Hablando estrictamente, la generación de números aleatorios es una operación inherentemente con estado, pero Haskell puede ocultar este hecho moviendo el estado "mutación". en la operación de enlace ( > > = ).

Esto probablemente suena un poco abstracto, y realmente no responde a su pregunta por completo, pero creo que todavía es aplicable. Desde un punto de vista teórico, es imposible trabajar con un RNG sin involucrar al estado. En cualquier caso, existen técnicas que pueden utilizarse para mitigar esta interacción y hacer que parezca como si toda la operación fuera de estado.

Answer 8

Generalmente es mejor crear un PRNG único y extraer múltiples valores de él. Crear varias instancias 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 comentario aparte, hay mejores " verdadero " Generadores de números aleatorios, pero generalmente requieren hardware especializado que haga cosas como derivar datos aleatorios de la variación de la señal eléctrica dentro de la computadora. A menos que esté realmente preocupado por eso, diría que los generadores de números pseudoaleatorios integrados en las bibliotecas de idiomas y / o el sistema operativo probablemente sean suficientes, siempre que su valor semilla no sea fácilmente predecible.

Answer 9

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

Los PRNG seguros son mucho más lentos y pueden requerir que las bibliotecas realicen operaciones de precisión arbitraria y pruebas de primalidad, etc., etc.

Answer 10

Bueno, mientras se siembren de manera diferente cada vez que se crean, entonces no, no creo que haya ninguna diferencia; sin embargo, si dependiera de algo como el tiempo, entonces probablemente no serían uniformes, debido a la semilla sesgada.