Generadores de números pseudoaleatorios

Cuando observar el mundo físico nos encontramos con fluctuaciones aleatorias en todas partes. Podemos generar números verdaderamente aleatorios mediante la medición del azar de las fluctuaciones conocidas como ruido. Cuando medimos este ruido, conocido como toma de muestras, podemos obtener números. - Uno, dos, tres, four-- Por ejemplo, si medimos la corriente eléctrica de la estática de la TV en el tiempo, vamos a generar una secuencia verdaderamente aleatoria. Podemos visualizar esta secuencia aleatoria trazando un camino que cambia de dirección de acuerdo con cada número, conocido como un paseo aleatorio. Nótese la falta de patrón en todas las escalas. En cada punto de la secuencia el siguiente paso es siempre impredecible. Se dice que los procesos aleatorios no son deterministas, ya que son imposibles de determinar con antelación. Máquinas, por otra parte, son deterministas. Su funcionamiento es predecible y repetible. En 1946, John von Neumann participó en el funcionamiento de los cálculos para militares; involucrados específicamente en el diseño de la bomba de hidrógeno. Usando un computador llamado el ENIAC, planeó en varias ocasiones calcular aproximaciones de los procesos implicados en la fisión nuclear. Sin embargo, esto requiere un acceso rápido a los números generados de forma aleatoria que podría repetirse, si es necesario. Sin embargo, ENIAC tenía la memoria interna muy limitada; y el almacenamiento a lo largo de las secuencias aleatorias no fue posible. Por lo tanto, Neumann desarrolló un algoritmo para simular mecánicamente el aspecto de codificación de aleatoriedad como sigue: En primer lugar, seleccionar un número realmente, llamado "semilla". Este número podría provenir de la medición del ruido, o la hora actual en milisegundos. A continuación, esta semilla se proporciona como entrada a un simple cálculo. Multiplicar la semilla por sí mismo, y luego la salida media de este resultado. A continuación, se utiliza esta salida como la siguiente semilla, y repetir el proceso tantas veces como sea necesario. Esto se conoce como el método de cuadrados medios y es sólo la primera de una larga lista de generadores de números pseudoaleatorios. La aleatoriedad de la secuencia depende de Sólo la aleatoriedad de la semilla inicial. Misma semilla, misma secuencia. Así que, ¿cuáles son las diferencias entre un generado de forma aleatoria frente pseudoaleatoria generada secuencia? Vamos a representar las secuencias como un paseo aleatorio. Parecen similares hasta que se acelerar las cosas. La secuencia pseudoaleatoria eventualmente se debe repetir. Esto ocurre cuando el algoritmo llega a una semilla que se ha utilizado previamente, y el ciclo se repite. La longitud, antes de que una secuencia pseudoaleatoria se repita, se llama "el período". El período está limitado estrictamente por la longitud de la semilla inicial. Por ejemplo, si usamos una semilla de dos dígitos, entonces un algoritmo puede producir, a lo sumo, 100 números, antes de volver a usar una semilla y repitir el ciclo. Una semilla de tres dígitos no pueden ampliar últimos 1.000 números antes de repetir su ciclo, y una semilla de cuatro dígitos no puede expandirse pasados 10.000 números antes de repetirse. Aunque si utilizamos una semilla suficientemente grande, la secuencia se puede ampliar en billones y billones de dígitos antes de repetirse. Sin embargo, la diferencia clave es importante. Al generar números de forma pseudoaleatoria, hay muchas secuencias de que no puede ocurrir. Por ejemplo, si Alice genera una secuencia verdaderamente aleatoria de 20 cambios, es equivalente a una selección uniforme de la pila de las todas posibles secuencias de cambios. Esta pila contiene 26 a la potencia de 20 páginas, que es astronómico en tamaño. Si nos encontrábamos en la parte inferior y iluminando con una luz hacia arriba, una persona en la parte superior no vería la luz hasta dentro de 200 millones años por lo menos. Compare esto con la generación de Alice una secuencia pseudoaleatoria de 20 dígitos, usando una semilla aleatoria de cuatro dígitos. Ahora, esto es equivalente a una selección uniforme a partir de 10.000 posibles semillas iniciales, lo que significa que sólo puede generar 10.000 secuencias diferentes, que es una fracción extremadamente pequeña de todas las secuencias posibles. Cuando nos movemos del azar a los cambios pseudoaleatorios, reducimos el espacio clave en un mucho, mucho más pequeño espacio de semillas. Así, para una secuencia pseudoaleatoria que pudiera ser indistinguible de una secuencia generada de forma aleatoria, debe ser poco práctico para un equipo para probar todas las semillas y buscar una coincidencia. Esto conduce a una importante distinción en ciencias de la computación, entre lo que es posible, en comparación con lo que es posible en una cantidad razonable de tiempo. Nosotros usamos la misma lógica cuando compramos un candado. Sabemos que cualquiera puede simplemente tratar todas las combinaciones posibles, hasta que encuentren una coincidencia y se abra. Pero les tomaría días para hacerlo. Así, durante ocho horas asumimos que es prácticamente seguro. Con los generadores pseudoaleatorios, los aumentos de seguridad tales como la longitud de los aumentos de semillas. Si el ordenador más potente tardase cientos de años a ejecutar todas las semillas posibles, entonces nosotros podemos asumir con seguridad que es prácticamente seguro, en lugar de perfectamente seguro. A medida que las computadoras se vuelven más rápidas el tamaño de la semilla debe aumentar en consecuencia. Pseudoaleatoriedad libera a Alice y Bob de tener que compartir su toda secuencia de cambios al azar de antemano. En lugar de ello, comparten una semilla aleatoria relativamente corta, y amplia en el mismo sentido el aspecto de la secuencia aleatoria cuando sea necesario. ¿Pero qué sucede si nunca se pueden reunir para compartir esta semilla aleatoria?