¿Cómo funcionan los generadores de números aleatorios? ¿Cómo se asegura de que los números sean aleatorios? ¿Existe algún verdadero generador de números aleatorios, tal vez en la naturaleza?

Answer 1

La aleatoriedad es un recurso invaluable en muchas áreas de la ciencia y la tecnología, desde simulaciones de Monte Carlo hasta métodos de cifrado seguros. Si bien los números aleatorios generados por computadora pueden usarse para algunas aplicaciones, permanecen fundamentalmente no aleatorios en el sentido de que cualquier cosa generada por un algoritmo es al menos en principio predecible. Sin embargo, la física cuántica proporciona aleatoriedad con imprevisibilidad inherente basada en las leyes fundamentales de la naturaleza.

En realidad, la mayoría de los números aleatorios utilizados en los programas de computadora son pseudoaleatorios, lo que significa que se generan de manera predecible utilizando una fórmula matemática. Esto está bien para muchos propósitos, pero puede no ser aleatorio de la manera que espera si está acostumbrado a tirar dados y sorteos de lotería.

Los generadores de números aleatorios tienen aplicaciones en juegos de azar, muestreo estadístico, simulación por computadora, criptografía, diseño completamente al azar y otras áreas donde es deseable producir un resultado impredecible.

Tenga en cuenta que, en general, donde la imprevisibilidad es primordial, como en las aplicaciones de seguridad, los generadores de hardware generalmente se prefieren (cuando sea posible) sobre los algoritmos pseudoaleatorios. Los primeros métodos para generar números aleatorios (dados, lanzamiento de monedas, ruedas de ruleta) todavía se usan hoy en día, principalmente en juegos y juegos de azar, ya que tienden a ser demasiado lentos para la mayoría de las aplicaciones en estadística y criptografía. En 2010, Kanter et al. En la Universidad de Bar-Ilan, se creó un generador de bits aleatorio físico que funciona a una velocidad de 300 gigabits por segundo, el más rápido creado hasta el momento.

Existen varios métodos computacionales para la generación de números aleatorios. Muchos no alcanzan el objetivo de la aleatoriedad verdadera, aunque pueden cumplir, con mayor o menor éxito, algunas de las pruebas estadísticas de aleatoriedad destinadas a medir cuán impredecibles son sus resultados (es decir, hasta qué punto sus patrones son discernibles). Sin embargo, existen métodos cuidadosamente diseñados criptográficamente seguros basados ​​en computación para generar números aleatorios, como los basados ​​en el algoritmo Yarrow y el Fortuna (PRNG) (el primero es la base de la fuente de entropía / dev / random en FreeBSD, AIX, Mac OS X, NetBSD y otros.)

Generador de números aleatorios basado en óptica cuántica:

Investigadores de la Universidad Nacional de Australia (ANU) están generando verdaderos números aleatorios a partir de una fuente cuántica física. Lo hacen dividiendo un haz de luz en dos haces y luego midiendo la potencia en cada haz. Como la luz está cuantizada, la intensidad de la luz en cada haz fluctúa alrededor de la media. Esas fluctuaciones, debido en última instancia al vacío cuántico, se pueden convertir en una fuente de números aleatorios. Cada número se genera aleatoriamente en tiempo real y no se puede predecir de antemano.

Implementación de RNG verdadero basado en Quantum:

http://www.random.org/ (utiliza variaciones en la amplitud del ruido atmosférico grabado con una radio normal).

Answer 2

De ninguna manera soy un experto en números aleatorios o un asistente de matemática / estadística, pero aquí están mis experiencias prácticas con números aleatorios principalmente como estudiante de ciencias de la computación e ingeniería …

Mi primera experiencia con números aleatorios fue en el lenguaje de programación Lua. Intentaba entender por qué el generador de números aleatorios siempre producía los mismos números cuando ejecutaba mi programa. “¡Que molesto! se supone que esos números son aleatorios, ¡pero son los mismos que la última vez! ”… Entonces aprendí que debes darle al generador de números aleatorios un valor inicial, como por ejemplo la hora actual.

Mi siguiente experiencia con números aleatorios fue en la universidad cuando implementamos nuestro propio sistema informático en un FPGA y lo hicimos cargar y ejecutar un juego de tetris que escribimos en C y ensamblado. Como sabes, los bloques que caen en tetris deben parecer aleatorios para que el juego sea divertido, por lo que generamos una lista de 100 números aleatorios con Java y codificamos esa lista en el programa C. El generador de números aleatorios en nuestro juego de tetris simplemente incrementaría un contador y elegiría un número de la lista. Creo que también “sembramos” el programa de alguna manera para comenzar desde una nueva posición en la lista cada vez que comenzó el juego. Recuerdo que discutimos el uso del número de ciclos de reloj entre las entradas del teclado como candidato para los valores iniciales.

Más tarde, hice un curso sobre simulación estocástica donde, entre otras técnicas, aprendí sobre la autocorrelación como medida para evaluar una lista de números “supuestamente” generados al azar. En una de las primeras tareas, implementé el algoritmo generador de congruencia lineal (un algoritmo para generar números aleatorios) y tracé algunos experimentos diferentes.

Aquí está mi antiguo código F # para mi implementación del generador congruencial:

let congruential_method (initial: int) (a: int) (b: int) (M: int) =
let rec loop prev = seq {
let x = (a * prev + b)% M
rendimiento flotante x / flotante M
¡rendimiento! lazo x}
seq {rendimiento flotante inicial / flotante M
¡rendimiento! bucle inicial

Genere 1000 números con algunas entradas específicas

dejar semilla = 3
dejar a = 16807
dejar b = 0
dejar M = 2147483647
let U1 = congruential_method seed ab M |> Seq.take 1000

y trazó los resultados en un histograma (izquierda) y una gráfica de autocorrelación (derecha):

Desde el punto de vista de los programadores, la autocorrelación para, por ejemplo, el Retardo 15 puede explicarse simplemente de la siguiente manera: tome su lista de números supuestamente aleatorios y genere dos nuevas listas de números basadas en esta lista. Una lista que es la lista original sin los últimos 15 números, y otra lista que es la lista original sin los primeros 15 números. Ahora solo necesita medir la correlación (Correlación y dependencia) entre estas dos listas … Ahora solo debe hacer lo mismo para todos los otros rezagos y trazar los valores de correlación.

Según el histograma, generalmente podemos tener una idea de cómo es la distribución. En este caso, debe ser uniforme, sin embargo, es un poco difícil confiar en este argumento. Quizás una muestra más grande hubiera sido mejor. El gráfico de autocorrelación a la derecha nos revela que realmente no hay ninguna correlación significativa entre todos los “retrasos” hasta 30 en la muestra. Esto es bueno si queremos que los números se dibujen de manera uniforme al azar. También realicé una prueba de Kolmogorov-Smirnov de una muestra que arrojó un valor P de 0,91. Como el valor P era tan alto, podría rechazar la hipótesis nula “de que la distribución no sigue una distribución uniforme”, en palabras del programador ahora sabemos que not(distribution != uniform) = True sin embargo, de esto no se sigue eso (distribution == uniform) = True . (¡Suena extraño, pero así es como funcionan los valores P! Incluso los estudiantes de PHD y los científicos se confunden con los valores P y publican resultados vergonzosos incorrectos)

(Tenga en cuenta que la autocorrelación y el histograma son dos cosas muy diferentes. El histograma es solo la imagen general de los datos finales, mientras que la autocorrelación ilustra cuán aleatoriamente se generan las series de números en relación con los números generados en el pasado).

Procedí a generar y trazar una nueva lista de números usando mi función de generador congruente. Esta vez quería intentar generar el número de manera que no se dibujaran de manera uniforme y aleatoria.

dejar seed2 = 5
dejar a2 = 1373
dejar b2 = 899
dejar M2 = 7777
let U2 = congruential_method seed2 a2 b2 M2 |> Seq.take 10000

En este caso, el histograma parece muy sospechoso si esperábamos una distribución uniforme, parece que hay algún patrón extraño en la distribución. La autocorrelación definitivamente nos dice que los números no se generan de manera aleatoria de manera uniforme, ya que tiene picos de correlación significativos en varios rezagos. La prueba de Kolmogorov-Smirnov arrojó un pequeño valor de 2.2e-16 que nos permite aceptar la hipótesis nula “de que la distribución no sigue una distribución uniforme”, en otras palabras (distribution != uniform) = True .

Para tener una idea visual de la correlación en el retraso 20, tracé las dos listas para el retraso 20 como un diagrama de dispersión.

La conclusión de todo este discurso de autocorrelación es que sentí que ahora finalmente tenía algunas buenas herramientas para evaluar y comprender la aleatoriedad de un generador de números aleatorios y las describo aquí para que otros puedan usarlas para comprender la aleatoriedad.

Finalmente, quiero mencionar brevemente los aspectos filosóficos de la aleatoriedad. Si crees como Einstein “que Dios no juega a los dados”, ¿entonces quizás no hay “aleatoriedad real”? o tal vez podamos comprometernos y decir que, como vemos, la aleatoriedad podría ser simplemente valores generados a partir de una función sembrada como la función generadora congruencial. ¿Quizás solo estamos viviendo en una simulación donde una función genera números aleatorios? Debido a este problema filosófico, no me gusta usar el término pseudoaleatorio. Nadie puede estar 100% seguro de lo que significa “aleatoriedad real” de todos modos, a menos que demuestren o desaprueben que el mundo es determinista. Entonces el término pseudoaleatorio de repente deja de tener sentido …

Answer 3

Una forma de hacerlo en hardware es utilizando un circuito de Registro de desplazamiento de retroalimentación lineal (LFSR). Como la mayoría de los generadores deterministas de números aleatorios, es pseudoaleatorio, no verdaderamente aleatorio.

Este circuito es un simple LFSR de 4 bits. Produce 15 números diferentes (todo cero no está permitido; descubra por qué), siempre en la misma secuencia. Como tal, es bastante inútil, pero se puede ampliar a longitudes de bits mucho más largas utilizando diferentes ‘puntos de derivación’, como se llaman las conexiones de retroalimentación.

La secuencia que produce puede deducirse de la traza lógica, pero si no es obvio, es:

1111 – 15
0111 – 7
1011 – 11
0101 – 5
1010 – 10
1101 – 13
0110 – 6
0011 – 3
1001 – 9
0100 – 4
0010 – 2
0001 – 1
1000 – 8
1100 – 12
1110 – 14

Una longitud máxima LFSR produce [matemática] 2 ^ n – 1 [/ matemática] estados, donde n es el número de bits o etapas en el registro (4 aquí). Las secuencias pseudoaleatorias son útiles precisamente porque son deterministas. Si tiene una secuencia muy larga, parecerá aleatoria, pero se repetirá exactamente. Si no sabe dónde se encuentra en la secuencia, puede ser difícil saber su longitud y, por lo tanto, cuál será el próximo bit, pero si conoce la longitud, puede predecirla exactamente. Eso puede ser útil, por ejemplo, al mantener sincronizados un transmisor y un receptor cuando se utiliza el salto de frecuencia: el LFSR elige la frecuencia y cada extremo tiene uno idéntico. Pero un espía tendrá dificultades para predecir a qué frecuencia saltará a continuación, por lo que es una forma simple de cifrado para las comunicaciones.

Por cierto, lo anterior, por supuesto, no es hardware en absoluto, es un programa de software que simula hardware. Puede implementar un LFSR en software fácilmente (¡y no necesita construir un simulador lógico real para hacerlo! – aunque en este caso lo hice :).

Answer 4

Como han notado los demás, generalmente terminas con un pseudo RNG. Es decir, algún software que intenta aproximar un número aleatorio a través de algún algoritmo.

Hay equipos especializados que usan datos físicos del mundo real para extraer un número “aleatorio”, pero que luego asume que el objeto físico del mundo real produce algunos eventos verdaderamente aleatorios.

Como muestra de la respuesta de Peter, usar números de comercio de acciones parece una buena opción (si la frecuencia requerida de números aleatorios es baja). ¿Pero qué hacer cuando el mercado estaba cerrado ese día? Por lo tanto, sería una buena idea usar esto si necesita un número aleatorio mientras el mercado de valores está realmente en funcionamiento.

Otro medio que generalmente se considera un generador aleatorio “verdaderamente” es usar la desintegración radio activa. Dado que ocurre a una velocidad constante pero a intervalos aleatorios (o al menos eso es lo que los científicos pensaron), se considera un muy buen RNG. Eso es hasta que esto se observó: las tasas de disminución radioactiva pueden no ser constantes después de todo. Por lo tanto, uno de esos supuestos se demuestra incorrecto (y extrañamente es sobre el que los físicos estaban más “seguros”), pero al menos solo sucede en circunstancias especiales. Por lo general, los datos siguen siendo útiles, aunque menos confiables que antes.

Answer 5

Creo que puedo responder en lenguaje sencillo. La forma en que los programas de computadora suelen obtener números aleatorios es a través de una combinación de dos dispositivos importantes:

1. Obtenga la hora del sistema como el número aleatorio “semilla”. Esto comienza una secuencia de números.
2. Utilice un generador de números pseudoaleatorios una vez que (1) haya iniciado una secuencia, de modo que la relación entre un número y el siguiente en la secuencia no sea detectable. Esto se hace aplicando una compleja transformación matemática.

Necesitas ambas cosas, por buenas razones. Solo uno u otro por sí solo no lo cortará.

Cuando obtiene la hora del sistema, en milisegundos, supongo, está obteniendo un número que aumenta gradualmente, pero como un humano típico (supongo que no es Superman y no lleva un dispositivo especial para medir el tiempo en milisegundos), no podrá predecir cuáles son los últimos dígitos.

Luego, el generador psuedo-random transforma esa semilla en el siguiente número en la secuencia “pseudoaleatoria”.

Este generador pseudoaleatorio crea una especie de ” efecto mariposa “. En pocas palabras, las pequeñas diferencias entre los valores iniciales de “semilla” (el tiempo del sistema, recuerde) dan como resultado diferencias enormes e impredecibles en el segundo elemento de la secuencia producida por el algoritmo . Ese segundo elemento se puede utilizar como el primer número “aleatorio”.

¡Y así es como los programas de computadora producen números aleatorios! Son aleatorios en el sentido de que desafían la predicción humana y la capacidad humana de detectar patrones.

Los números no son aleatorios en principio. Sin embargo, desafían cualquier previsibilidad que pueda ser observada por todos menos unos pocos humanos:

El número inicial producido depende del número preciso devuelto por la función “hora del sistema”.

Pero a medida que el tiempo del sistema cambia incluso en la cantidad más pequeña, esto da como resultado cambios arbitrariamente grandes en el segundo número de la serie “aleatoria”.

La serie aleatoria en sí misma es determinista, pero la ingeniería inversa de la serie es deliberadamente difícil debido a la naturaleza del algoritmo, que es una transformación matemática compleja que elude patrones obvios.

Entonces, por ejemplo, nada tan obvio como impar / par / impar / par surgirá de un buen generador de números aleatorios.

• Tenga en cuenta que la “aleatoriedad”, que se cumple para todos los fines prácticos, depende tanto de la semilla del tiempo del sistema como de tener un algoritmo adecuado para obtener el siguiente número en la secuencia. Si se utilizó la misma semilla durante cada ejecución del programa, el usuario debería esperar ver los mismos resultados, sesión tras sesión.
• Por el contrario, si el tiempo del sistema se usa como la “semilla”, pero el algoritmo de números aleatorios es deficiente, es probable que el usuario detecte un patrón emergente de un evento “aleatorio” al siguiente. Pero la esencia de la aleatoriedad es no tener un patrón discernible o una fusión de previsibilidad.

Con estos dos elementos, la entrada inicial de una fuente externa, como la hora del sistema, y ​​un buen algoritmo de números aleatorios, el comportamiento del programa debería parecer bastante aleatorio para un usuario humano.

Puede surgir un problema potencial por el hecho de que después de N salidas, una secuencia pseudoaleatoria finalmente vuelve a su estado inicial y luego comienza a repetirse. No importa cuán sofisticado sea un generador de números aleatorios, solo puede tener un número finito de estados. Sin embargo, algunos generadores pueden producir astronómicamente muchas salidas antes de alcanzar un estado anterior.

Answer 6

Como la mayoría ha señalado, no lo hacen.

Cualquier número aleatorio generado por software es producido por un algoritmo, lo que significa que si conoce la entrada y la secuencia de operaciones realizadas en la entrada, puede predecir la salida. Es por eso que se llaman generadores de números pseudoaleatorios (PRNG).

Los PRNG pueden ser muy buenos, pero producen una larga cadena de números repetidos y la parte aleatoria es donde comienza la cadena de números. Comenzar en el mismo lugar produce los mismos números. En realidad, esta es una característica importante cuando se trata de una gran cantidad de simulaciones por computadora que contienen elementos que son “aleatorios”. Al escribir el código de simulación, iniciar el PRNG en el mismo lugar garantiza que sucederán los mismos eventos, lo que le permite depurar el código, ya que diferentes números aleatorios pueden producir diferentes resultados en las ejecuciones de la simulación, haciéndolo fijo, facilita determinar si fue una simulación válida evento o un error. Lo mismo ocurre con la programación del juego.

La generación de números aleatorios reales (es decir, impredecibles) requiere un hardware especializado. También hay algunos de estos, como un fotómetro que cuenta cuántos fotones lo golpean y produce un voltaje basado en este recuento, lo que lo convierte en un dispositivo analógico que se alimenta a través de una conversión analógica a digital para hacer ese número digital aleatorio .

Otros incluyen ruido de disparo, amplificación de un transistor de polarización inversa, energía térmica, ruido de avalancha e incluso desintegración nuclear. Todos estos utilizan algún efecto físico para crear una secuencia de números aleatorios e impredecibles.

Uno de los primeros para mí fue el chip SID en el Commodore 64.

Produjo sonido, pero el chip en sí era parcialmente analógico, y una de las formas de onda para el sonido era “ruido”. Esto usó una porción analógica del chip para producir ruido aleatorio en el canal que era realmente aleatorio. Al configurar uno de los canales como ruido, puede leer los valores del oscilador y obtener números aleatorios. Solo el canal tres permitió leer el oscilador, por lo que es la opción para números aleatorios. Como a menudo se usaba para hacer ruidos de batería en la música, es posible que esté leyendo desde el chip mientras se reproducía la rutina de interrupción de la música, pero aún así funcionó bien ya que el oscilador estaba funcionando incluso cuando no se generaba un sonido (silenciado) .

Para configurar el canal 3 hiciste algo como esto:

LDA # $ FF; valor de frecuencia máxima
STA $ D40E; voz 3 frecuencia bajo byte
STA $ D40F; voz 3 frecuencia byte alto
LDA # $ 80; forma de onda de ruido, puerta desactivada
STA $ D412; registro de control de voz 3
RTS

Entonces un simple

LDA $ D41B; leer un byte aleatorio de SID

números aleatorios cosechados un byte a la vez.

Entre los dos hay un PRNG que se alimenta de Entropía (aleatoriedad) de algunos dispositivos que es aleatorio. Estos funcionan mediante el uso de una fuente de eventos aleatorios que ocurren con menos frecuencia de la que podría necesitarlos, y los alimentan al estado interno del PRNG para mantener alta la entropía.

Usted mencionó Linux /dev/random . Este es solo un dispositivo mantenido por el kernel de Linux. Utiliza la sincronización de los controladores del dispositivo, como la interrupción del teclado, las interrupciones del disco y el mouse. Estos provienen de fuentes externas y deben ser aleatorios. Esto se alimenta a un PRNG con un grupo de entropía para crear números aleatorios criptográficamente seguros (en sistemas que tienen suficiente entrada del usuario). /dev/random se bloqueará cuando la entropía sea pequeña, donde as /dev/urandom (random ilimitado) no.

Answer 7

Primero, no existe un solo número aleatorio; por ejemplo, ¿es 4 un número aleatorio? Solo podemos decir que una secuencia de números es aleatoria si tiene ciertas propiedades matemáticas. Puede obtener verdaderos números aleatorios lanzando una moneda o tirando un par de dados repetidamente. Los generadores de números pseudoaleatorios (PRNG) son algoritmos deterministas que producen secuencias de números que parecen aleatorios.

La propiedad más importante de los PRNG es que los números producidos se distribuyen uniformemente en un rango dado , de modo que los valores en el rango ocurren con probabilidades iguales. Por ejemplo, un lanzamiento de moneda puede tener dos resultados posibles, cara o cruz, cada uno con probabilidad [matemática] p = \ frac {1} {2} [/ matemática]; tirar un dado justo puede producir cualquier número del 1 al 6 con probabilidad [matemática] p = \ frac {1} {6} [/ matemática]. El núcleo de la mayoría de las bibliotecas de generación de números aleatorios es una función, como rand() de la biblioteca estándar C, que genera números enteros distribuidos uniformemente entre 0 y un valor RAND_MAX . Se pueden obtener otros rangos y distribuciones transformando los números generados de esta manera (por ejemplo, para obtener números de una distribución exponencial con media [matemática] \ mu [/ matemática] puede usar la fórmula [matemática] E_i = – \ mu \ En U_i [/ ​​matemáticas]). Los generadores de números aleatorios deben inicializarse llamando a una función para proporcionar una semilla, un número a partir del cual se generan todos los números posteriores. En la biblioteca estándar de C, esta función se llama srand() . Una práctica común es sembrar PRNG con la hora actual. Debido a que los generadores de números aleatorios son programas de computadora deterministas, dos secuencias generadas usando el mismo algoritmo y comenzando desde la misma semilla serán idénticas (un error de programación común es sembrar el generador con un valor constante antes de generar cada número aleatorio; esto dará como resultado generando el mismo número repetidamente).

Para ilustrar cómo funciona esto, explicaré uno de los primeros algoritmos para la generación de números aleatorios, el método lineal congruencial (LC) . El método LC se rige por tres parámetros:

• [matemáticas] M [/ matemáticas], el módulo; [matemáticas] 0
• [matemáticas] A [/ matemáticas], el multiplicador; [matemáticas] 0 \ leq A
• [matemáticas] B [/ matemáticas], el incremento; [matemáticas] 0 \ leq B

Este método genera una secuencia de números sin signo [matemática] X_0 [/ matemática], [matemática] X_1 [/ matemática],…. La función de inicialización inicializa [math] X_0 [/ math]. Cada invocación del generador de números aleatorios producirá un nuevo número [matemática] X_ {i + 1} [/ matemática] al transformar el último número en la secuencia [matemática] X_i [/ ​​matemática] con la siguiente fórmula:

[matemáticas] X_ {i + 1} = (A X_i + B) \ bmod M [/ matemáticas]

Por ejemplo, cuando [matemática] M = 10 [/ matemática] y [matemática] X_0 = A = B = 7 [/ matemática] la secuencia resultante es 7, 6, 9, 0, 7, 6, 9, 0 ... .. (este ejemplo es de Knuth vol. 2; BTW, ese libro tiene más de lo que siempre quisiste saber sobre la generación de números aleatorios). Porque la secuencia [math] X_i [/ ​​math] se calcula módulo [math] M [/ math] , los números se generan en el rango entre [matemática] 0 [/ matemática] y [matemática] M-1 [/ matemática]. Si [math] M = 2 ^ {32} [/ math] y está utilizando variables unsigned para estas operaciones, la operación de módulo generalmente puede omitirse (en las CPU x86 de 32 y 64 bits, los números unsigned se representan en 32 bits y unsigned operaciones unsigned se realizan módulo [matemática] 2 ^ {32} [/ matemática]).

Todos los generadores LC entran en una órbita periódica, un ciclo de números que se repiten, como se ve en el ejemplo anterior. Un PRNG debe tener un período lo más largo posible; Algunas aplicaciones requieren millones de números aleatorios que no se repiten. El período más largo posible es el módulo [matemática] M [/ matemática], en cuyo caso la órbita es una permutación completa: cada número en el rango se genera exactamente una vez. Aquí hay una lista de parámetros que proporcionan esta propiedad.

Para asegurarse de que la secuencia generada sea aleatoria, puede verificar que tenga las propiedades matemáticas deseadas aplicando varias pruebas de aleatoriedad . Por ejemplo, puede usar la prueba de chi-cuadrado para determinar si las frecuencias de aparición de los números generados son consistentes con la distribución uniforme. Esta prueba implica dividir el rango de números generados en múltiples contenedores, contando cuántos números caen en cada bin y cuántos se esperaría que caigan en cada bin, dada la distribución uniforme, y calculando una estadística de prueba a partir de las diferencias entre estos conteos. Si el estadístico de prueba es demasiado alto, entonces es poco probable que la secuencia provenga de una distribución uniforme; de lo contrario, decimos que la secuencia es consistente con la distribución uniforme porque no tenemos evidencia de lo contrario. Todas las pruebas de aleatoriedad funcionan así: pueden determinar si las secuencias generadas son consistentes con ciertas propiedades matemáticas, pero ninguna prueba puede probar que los números son aleatorios . Como resultado, la falla es que los algoritmos PRNG a menudo son difíciles de encontrar, como en el caso del algoritmo Dual_EC_DRBG que supuestamente incluía una puerta trasera insertada por la NSA.

La capacidad de predecir el próximo valor generado por un PRNG tiene muchas aplicaciones en seguridad, tanto para fines de ataque como de defensa. Por ejemplo, puede descifrar conexiones TLS, reconstruir claves privadas, inferir el árbol de quién infectado de quién de un gusano de Internet o secuestrar una botnet que se basa en algoritmos de generación de dominio. Debido a que los PRNG son algoritmos deterministas, puede predecir la secuencia generada si conoce la semilla o el estado interno del generador. Para evitar esto, los PRNG criptográficamente seguros tienen requisitos estrictos para evitar tales filtraciones de información. Esto a menudo se logra mediante la recopilación de múltiples fuentes de entropía, como movimientos del mouse, golpes de teclado, entradas de cámara o micrófono, para la semilla y el uso de la salida de un cifrado de bloque, como AES, como el número generado.

Para responder a sus últimas preguntas, sí, existen generadores de números aleatorios en la naturaleza. Por ejemplo, en una sustancia radiactiva que emite una partícula alfa cada [math] \ mu [/ math] segundos en promedio, el tiempo entre emisiones sucesivas sigue una distribución exponencial con media [math] \ mu [/ math]. Esta aleatoriedad es fundamental para la física cuántica, hasta un punto que incomoda a algunos científicos; Por ejemplo, Einstein dijo que “Dios no juega a los dados con el universo” (estaba equivocado).

Como otros han señalado, estos efectos físicos se han utilizado para implementar generadores de números aleatorios en el hardware. Quizás la más utilizada hoy en día es la instrucción RDRAND de Intel, disponible en todas las CPU modernas x86. La implementación de RDRAND ha sido analizada ampliamente y generalmente se considera una buena fuente de aleatoriedad. Es particularmente útil cuando necesita una buena semilla y no está dispuesto a esperar /dev/random , que bloquea hasta que reúne suficiente entropía. Sin embargo, como con cualquier RNG, la ausencia de fallas y puertas traseras realmente no se puede probar. Por lo tanto, algunas personas argumentan que es más seguro confiar en implementaciones de software de código abierto que han sido analizadas en busca de errores (que tal vez sean más fáciles de encontrar que los troyanos de hardware) y en diversas fuentes de entropía.

Answer 8

En mis días de Ciencias de la Computación, especializándome en UCSB en 1983/1984, programé un programa no determinista genuinamente aleatorio que se ejecutaba en la computadora Digital VAX del campus. Todo lo que era era un programa en C que bifurca un montón de procesos (tareas) separados usando la bifurcación (); comando, y luego todos competirían para abrir el mismo archivo y escribir su propio valor de dígito distinto. Depende del sistema operativo determinar qué tarea se realizó primero, segundo, etc.

Esto funcionó porque era una computadora multiusuario y tenía algunas propiedades interesantes debido a eso. En las raras ocasiones en que sería la única persona, su respuesta era tan determinista como cualquier otro programa que se pudiera ejecutar, pero por lo general, a medida que las cosas se ponían más ocupadas, las respuestas diferían más y más, y en esos plazos de asignación tan grandes como se acercaban cuando docenas de estudiantes trabajan frenéticamente toda la noche en grandes proyectos, trabajando en teclados, editando (usando vi principalmente), compilando, ejecutando trabajos en segundo plano, ejecutando programas de diagnóstico de depuración, enviándose correos electrónicos, imprimiendo cosas en la impresora y bebiendo mucho café (que yo solo me negué a hacer), incluso el sesgo hacia un resultado específico se perdería en la verdadera no determinación del programa.

¡Supongo que se podría argumentar que incluso con la máxima no determinación todavía habría tenido un sesgo en eso (como lo codifiqué originalmente) habría terminado con los dígitos ASCII “1” a “8” en cualquiera de 8! combinaciones posibles (factoriales) (leídas como un número decimal de ocho dígitos), lo que significa que el valor más pequeño posible fue “12345678” y el mayor “87654321” y todos los demás valores no distribuidos uniformemente entre ellos.

Por lo tanto, no requiere ningún hardware especial para crear una verdadera no determinación en una computadora, solo muchos usuarios comparten y realizan múltiples tareas en una sola computadora mainframe. Algo igualmente no determinista podría obtenerse igualmente, por ejemplo, mediante el uso del generador de números pseudoaleatorios para seleccionar ubicaciones en la memoria física que se utilizan activamente para la memoria virtual de proyectos de múltiples usuarios. Incluso el mismo lugar, al ser revisado algún tiempo después, probablemente estaría sirviendo a las diferentes tareas de un usuario diferente en una capacidad diferente.

Answer 9

Puede haber varias formas de generar números aleatorios. En hardware, una forma muy común es mediante LFSR (Registro de desplazamiento de retroalimentación lineal). Consiste en un registro (ubicación de memoria de hardware que almacena datos binarios) y una lógica XOR. La idea es ‘aprovechar’ algunas de las ubicaciones de bits del registro, implementar la lógica XOR en ellos y alimentarlo de nuevo a un extremo si este registro, mientras se desplazan linealmente los datos en una dirección. Entonces, en cada reloj, genera un nuevo número que puede considerarse números aleatorios generados uniformemente.

Cabe señalar que tocar los bits desde cualquier ubicación de bits o implementar cualquier lógica XOR no funcionará. Hay pocas restricciones que deben tenerse cuidado para generar realmente números ‘aleatorios’.

Answer 10

Hay dos tipos de generadores de números aleatorios: físicos y basados ​​en computadora. Estos últimos no son verdaderos RNG.

Los métodos físicos implican cosas como elegir bolas de un conjunto bien mezclado y también cosas como usar los últimos dos dígitos del volumen de acciones negociadas en una bolsa de valores. Estos son lo más cercanos al azar que puede obtener y están bien si solo necesita unos pocos números.

Los algoritmos basados ​​en computadora son realmente generadores de números pseudoaleatorios . Funcionan tomando una semilla que seleccionas (o puedes usar la hora del reloj como semilla) y aplicando uno de los muchos algoritmos para que la serie posterior tenga muchas propiedades de aleatoriedad. Los buenos paquetes estadísticos tienen PRNG incorporados. R, por ejemplo, ofrece varios. Por defecto utiliza el “Mersenne twister”:

“Mersenne-Twister”:
De Matsumoto y Nishimura (1998). Un GFSR retorcido con período 2 ^ 19937 – 1 y equidistribución en 623 dimensiones consecutivas (durante todo el período). La ‘semilla’ es un conjunto de 624 dimensiones de enteros de 32 bits más una posición actual en ese conjunto.

donde GFSR significa ” registro de desplazamiento de retroalimentación generalizada”

Answer 11

Ellos no. Los algoritmos pueden generar una secuencia de números que aparecen principalmente al azar para un observador externo. La generación de la secuencia sigue siendo determinista y repetible dado el algoritmo, la entrada y el estado inicial.

Las computadoras también pueden recolectar entropía del entorno circundante. Los tiempos, los sonidos de temperatura de múltiples eventos independientes son un comienzo. La medición de procesos aleatorios independientes reales es mejor, como la desintegración radiactiva o la colisión de electrones en un circuito son aún mejores. Esas mediciones se pueden alimentar al algoritmo de secuencia pseudoaleatoria y generar algo mucho más cercano a lo aleatorio, pero aún determinista. Las secuencias controladas por entropía son útiles cuando los números impredecibles son útiles, como por seguridad.

Answer 12

Definir aleatoriedad no es tan simple. Las máquinas son hechas por el hombre y son altamente deterministas. Entonces, la noción de RNG (generador de números aleatorios) es solo un acrónimo difuso de lo que realmente es solo un generador pseudoaleatorio. La generación de tales números está vinculada al reloj de la CPU. En Cifrado y Redes, predominantemente para sincronización y señalización, juega un papel importante. Si quieres ver qué tan profundo puede ser la madriguera del conejo, solo ten en cuenta que incluso cuando lanzas un dado o lanzas una moneda justa, lo único que es “aleatorio” es la fuerza que aplicas que conduce a tu CPU, es decir, al cerebro impulsos envían a tu brazo. La masa de la moneda o el dado se mantiene constante.

Answer 13

El gobierno británico posee un generador de números aleatorios bastante bueno, llamado ERNIE, el equipo electrónico de indicación de números aleatorios. Se utiliza para elegir números en nuestra lotería nacional más antigua, el esquema de Bonos Premium.

Los Bonos Premium son un préstamo al gobierno donde los intereses no se pagan directamente, sino que se agrupan y pagan al azar a un puñado de tenedores de bonos.

El primer ERNIE fue construido en 1956 y ahora está en el Museo de Ciencias de Londres. El actual se construyó en 2008. Todos ellos han funcionado de manera similar: utilizan una fuente de ruido térmico y un contador. La primera fuente de ruido fue un indicador de neón, el último un par de uniones de semiconductores. El sorteo de cada mes está sujeto a una batería de pruebas estadísticas de aleatoriedad por parte de los actuarios gubernamentales.

ERNIE | NS&I

Answer 14

Los procesos informáticos que intentan generar números aleatorios son más precisamente generadores de números pseudoaleatorios. Los generadores de números pseudoaleatorios realizan operaciones matemáticas en un número llamado “semilla”. Las operaciones matemáticas se eligen para que el número resultante se vea completamente diferente de la “semilla”. Los generadores de números pseudoaleatorios luego usan este número o uno derivado de para generar el siguiente número. Como resultado, el PRNG tiene solo un número finito de estados. En algún momento, es seguro repetir, produciendo la misma secuencia que producía antes. Por lo tanto, es pseudo o no aleatorio.

La página en sourceware.org proporciona el código C para la función rand (). Tales algoritmos generalmente usan combinaciones de multiplicar, sumar y desplazar (y ocasionalmente dividir) para generar secuencias de números aleatorios. Tal tratamiento puede dar lugar a algoritmos como RANDU que resultaron producir secuencias con patrones ocultos mal ocultos.

Answer 15

En un sistema con un número establecido de variables, se puede predecir cualquier resultado. Por ejemplo. Tienes una manzana en la mano que dejas ir, ¿puedes predecir lo que sucederá después? Más probable. Es cuando comienzas a expandirte sobre el conjunto de variables que las cosas se vuelven más aleatorias. Las más variables que no puede tener en cuenta es un buen indicador del nivel de aleatoriedad que puede producir. Pero verdaderamente, con la excepción de
posiblemente mecánica cuántica, no existe un verdadero azar en ningún sentido.

En términos de hacer algo al azar hasta el punto en que se vuelve irrelevante para el usuario, como un juego de lanzamiento de monedas entre amigos, lo mejor que podemos hacer es lo siguiente.

“Se basan en procesos impredecibles como el ruido térmico o atmosférico en lugar de patrones definidos por el hombre. Los resultados aún pueden estar ligeramente sesgados hacia números más altos o incluso números, pero no son generados por un algoritmo determinista. (Una solución en línea similar está disponible en random.org.) – Jason M. Rubin “

Answer 16

Todos los generadores de números aleatorios basados ​​en software son pseudogeneradores y no son realmente aleatorios en el sentido matemático. Sin embargo, existen generadores mecánicos de números aleatorios que se basan en la detección de partículas de descomposición emitidas por un isótopo de baja energía. Estos detectores en su forma más simple usan la dirección de emisión de una partícula para activar una respuesta binaria, algunos están construidos en una matriz.

Ver
http://en.m.wikipedia.org/wiki/H …

http://en.m.wikipedia.org/wiki/R …

Aunque hay algunos dispositivos electrónicos que utilizan otros enfoques, consulte http://ipcores.com/True_Random_G …

Answer 17

La única forma de generar números aleatorios con una computadora es usar un dispositivo externo. Si desea generar un número aleatorio con su computadora, será un poco más difícil.

Primero debes entender que tu computadora es puramente determinista, así que no esperes que haga cosas al azar. Por lo tanto, no hablaremos de números aleatorios sino de números pseudoaleatorios. Y usaremos la función matemática para generarlos. Ya escribo un artículo al respecto, con el código de Python en un cuaderno y algunas herramientas estadísticas para probar la calidad de su generador, no dude en consultarlo: Melvyn Peignon – Mi blog personal

Answer 18

El más simple usa una recurrencia [math] u_i = f (u_ {i-1}) [/ math], comenzando desde una semilla [math] u_0 [/ math]. La recurrencia más simple es una congruencia lineal [matemática] u_i = (a * u_ {i-1} + b) mod c [/ matemática], con [matemática] c = 2 ^ n [/ matemática] y [matemática] a [ / math] primo con [math] c [/ math]. Si se solicita un número de coma flotante, el número entero [math] u_i [/ ​​math] se divide por [math] c [/ math].

Como otros mencionan, no es una aleatoriedad verdadera, ya que se puede adivinar el siguiente número pseudoaleatorio. Sin embargo, no está lejos siempre que

1. Todos los números en el conjunto [matemática] \ {0, 1,…, c \} [/ matemática] tienen la misma posibilidad de ser seleccionados.
2. la periodicidad (hay una porque el número de resultados posibles es finito, por lo que después de un tiempo el generador tiene que caer en un número previamente elegido y comenzar a alternar), la periodicidad es igual al valor máximo posible [matemáticas] c [ /matemáticas].
3. no hay subperíodos estadísticos que ayuden a adivinar [matemática] u_ {i + k} [/ matemática] conociendo [matemática] u_ {i} [/ matemática], que a menudo se expresa al requerir que la covarianza [matemática ] Cov (u_ {i + k}, u_ {i}) = 0 [/ math] es nulo para todos [math] k [/ math].

Durante mucho tiempo tuve la impresión de que hacer variables [math] b [/ math], como tomarse el tiempo en milisegundos, reduciría la previsibilidad. Sin embargo, leí en algún lugar hace mucho tiempo que, de hecho, no cambia la entropía esperada.

Answer 19

Combinar la lógica difusa con la red neuronal puede ayudar a crear un fuerte generador de números aleatorios. Podemos utilizar la red neuronal como datos para predecir los conjuntos futuros. the classification process is based on SVD concept and energy equation, as we know the SVD give us information about the correlation in matrix and also it has flexibility in rotation vectors. this can give us multiple solution to see similarity in spherical space , i did use this technique to build random number generator with an application on game theory, looking for team to help develop this idea better.

Answer 20

One of the things to keep in mind is that there are no ‘true’ random number generators. They just generate numbers that look random to us mere mortals.
One of the easiest examples of this (to implement, as well) is the Linear congruential generator. Sure, the numbers look unpredictable to you and me, but they’re actually evenly spaced within a finite field.
Of course, some generators, like Blum Blum Shub aren’t predictable for an outsider even if he applies serious mathematical skills and computing power to the task, but at the fundamental level, random number generators aren’t random; they’re regular and predictable.
Source: Page on stackoverflow.com