Algún tipo dijo lo siguiente:

Cualquiera que intente generar números aleatorios por medios deterministas está, por supuesto, viviendo en un estado de pecado.

Eso siempre se entiende que no puede generar números aleatorios verdaderos con solo una computadora. Y dijo que cuando las computadoras tenían el tamaño equivalente de un único microprocesador Intel 8080 (~ 6000 válvulas). Las computadoras se han vuelto más complejas, y creo que la declaración de von Von Neumann puede que ya no sea cierta. Considere que un algoritmo implementado solo de software es imposible. Se ejecutan en hardware físico. Los verdaderos generadores de números aleatorios y sus fuentes de entropía también están hechos de hardware.

Este fragmento de Java se coloca en un bucle:

      file.writeByte((byte) (System.nanoTime() & 0xff));

puede crear un archivo de datos que he representado como una imagen:

Puedes ver la estructura, pero también con mucha aleatoriedad. Lo interesante es que este archivo PNG tiene un tamaño de 232 KB, pero contiene 250,000 píxeles de escala de grises. El nivel de compresión PNG era máximo. Eso es solo una relación de compresión del 7%, es decir. bastante no compresible Lo que también es interesante es que el archivo es único. Cada generación de este archivo es un patrón ligeramente diferente y tiene una compresibilidad ~ 7% similar. Destaco esto, ya que es fundamental para mi argumento. Eso es ~ 7 bits / byte entropía. Eso reducirá, por supuesto, con el uso de un algoritmo de compresión más fuerte. Pero no reduzca a nada cerca de 0 bits / byte. Se puede tener una mejor impresión tomando la imagen de arriba y sustituyendo su mapa de color por uno aleatorio:

La mayor parte de la estructura (en la mitad superior) desaparece, ya que eran solo secuencias de valores similares pero marginalmente diferentes. ¿Es esta una verdadera fuente de entropía creada simplemente ejecutando un programa Java en un sistema operativo multi-toma? ¿No es un generador de números aleatorios distribuido uniformemente, sino la fuente de entropía para uno? Una fuente de entropía creada con software que se ejecuta en hardware físico que resulta ser una PC.

Hecho suplementario

Para confirmar que cada imagen genera una entropía nueva sin un patrón fijo común a todos, se generaron 10 imágenes consecutivas. Estos fueron concatenados y comprimidos con el archivador más fuerte que puedo compilar (paq8px). Este proceso eliminará todos los datos comunes, incluida la correlación automática, dejando solo los cambios / entropía.

El archivo concatenado se comprimió a ~ 66%, lo que conduce a una tasa de entropía de ~ 5.3 bits / byte o 10.5Mbits / imagen. Una sorprendente cantidad de entropía$\smile$

Suplementario 2

Ha habido comentarios negativos de que mi entropía por metodología de prueba de compresión es defectuosa, solo da una estimación de límite superior suelto. Así que ahora he ejecutado el archivo concatenado a través de la prueba de evaluación de entropía criptográfica oficial de NIST, SP800-90B_EntropyAssessment . Esto es tan bueno como se obtiene para la medición de entropía sin IID. Este es el informe (lo siento, esta pregunta se está haciendo larga, pero el problema es complejo): -

Running non-IID tests...

Entropic statistic estimates:
Most Common Value Estimate = 7.88411
Collision Test Estimate = 6.44961
Markov Test Estimate = 5.61735
Compression Test Estimate = 6.65691
t-Tuple Test Estimate = 7.40114
Longest Reapeated Substring Test Estimate = 8.00305

Predictor estimates:
Multi Most Common in Window (MultiMCW) Test: 100% complete
    Correct: 3816
    P_avg (global): 0.00397508
    P_run (local): 0.00216675
Multi Most Common in Window (Multi MCW) Test = 7.9748
Lag 

Test: 100% complete
    Correct: 3974
    P_avg (global): 0.00413607
    P_run (local): 0.00216675
Lag Prediction Test = 7.91752
MultiMMC Test: 100% complete
    Correct: 3913
    P_avg (global): 0.00407383
    P_run (local): 0.00216675
Multi Markov Model with Counting (MultiMMC) Prediction Test = 7.9394
LZ78Y Test: 99% complete
    Correct: 3866
    P_avg (global): 0.00402593
    P_run (local): 0.00216675
LZ78Y Prediction Test = 7.95646
Min Entropy: 5.61735

El resultado es que NIST cree que he generado 5.6 bits / byte de entropía. Mi estimación de compresión de bricolaje pone esto en 5,3 bits / byte, marginalmente más conservador.

-> La evidencia parece apoyar la idea de que una computadora que solo ejecuta software puede generar entropía real. Y que von Neumann estaba equivocado (pero tal vez correcto para su tiempo).

Ofrezco las siguientes referencias que pueden respaldar mi reclamo:

¿Existen modelos estocásticos de no determinismo en la tasa de ejecución del programa?

Análisis WCET de sistemas probabilísticos de tiempo real duro

¿Existe un algoritmo de software que pueda generar un patrón de caos no determinista? y la relevancia de los efectos caóticos.

Paralelos con el principio de incertidumbre entrópica cuántica

Entrada de blog de Aleksey Shipilёv sobre el comportamiento caótico de nanoTime (). Su diagrama de dispersión no es diferente al mío.

El hecho de que no pueda ver un patrón no significa que no exista un patrón. El hecho de que un algoritmo de compresión no pueda encontrar un patrón no significa que no exista un patrón. Los algoritmos de compresión no son balas de plata que pueden medir mágicamente la verdadera entropía de una fuente; todo lo que te dan es un límite superior en la cantidad de entropía. (Del mismo modo, la prueba NIST también le da solo un límite superior). El caos no es aleatoriedad.

Se necesita un análisis y un examen más detallados para comenzar a obtener cierta confianza en la calidad de la aleatoriedad obtenida de esta manera.

No hay razones para pensar que, probablemente, podemos obtener una cierta cantidad de aleatoriedad mediante la explotación de las fluctuaciones de reloj y la deriva entre dos relojes de hardware , pero es delicado y complicado, por lo que tiene que tener cuidado. No recomendaría intentar implementar el tuyo. En cambio, sugeriría que use una fuente de entropía de alta calidad (generalmente implementada en la mayoría de los sistemas operativos modernos). Para obtener más detalles, consulte también Wikipedia , hasged y /crypto//q/48302/351 (que parece que ya conoce).

Por último, un comentario sobre su primer partido:

"Cualquiera que intente generar números aleatorios por medios deterministas está, por supuesto, viviendo en un estado de pecado".

Eso siempre se entiende que no puede generar números aleatorios verdaderos con solo una computadora.

No, no es así como se suele tomar, y no es lo que dice. Está diciendo que no puedes generar números aleatorios verdaderos por medios deterministas . Si puede hacerlo en una computadora depende de si la computadora es determinista o no. Si la computadora es determinista, o su programa usa solo operaciones deterministas, no puede hacerlo. Sin embargo, muchas computadoras contienen elementos no deterministas, y si su programa los usa, se necesita un análisis más detallado antes de que pueda decidir si se pueden usar para generar números aleatorios. En su caso nanoTime()es no determinista.

Si está utilizando alguna fuente de hardware de entropía / aleatoriedad, no está "intentando generar aleatoriedad por medios deterministas " (mi énfasis). Si no está utilizando ninguna fuente de hardware de entropía / aleatoriedad, entonces una computadora más poderosa solo significa que puede cometer más pecados por segundo.

Siempre he entendido que la cita significa que un algoritmo determinista tiene una cantidad fija de entropía, y aunque la salida puede parecer "aleatoria", no puede contener más entropía de la que proporcionan las entradas. Desde esta perspectiva, vemos que su algoritmo pasa de contrabando en entropía a través de System.nanoTime(): la mayoría de las definiciones de un algoritmo "determinista" no permitiría llamar a esta función.

La cita, aunque concisa, es esencialmente una tautología. No hay nada para refutar y no hay una evolución posible del hardware que pueda hacer que ya no sea cierto. No se trata de hardware, se trata de la definición de un algoritmo determinista. Simplemente está observando que el determinismo y la aleatoriedad son incompatibles. Para cualquier algoritmo determinista, todo su comportamiento se predice por sus condiciones iniciales. Si crees que has encontrado una excepción, estás malentendido lo que significa ser determinista.

Es cierto que un proceso que se ejecuta en una computadora compartida con una serie compleja de cachés y que recibe varias entradas de red y hardware tiene acceso a mucha más entropía que uno que se ejecuta en hardware simple, aislado y dedicado. Pero si ese proceso accede a esa entropía, ya no es determinista y, por lo tanto, la cita no se aplica.

Cualquiera que intente generar números aleatorios por medios deterministas está, por supuesto, viviendo en un estado de pecado.

Cuando interpretas "vivir en un estado de pecado" como "hacer un sinsentido", es perfectamente correcto.

Lo que hiciste fue usar un método bastante lento System.nanoTime()para generar una aleatoriedad bastante débil. Mediste algo

... tasa de entropía de ~ 5.3 bits / byte ...

pero esto es solo el límite superior. Todo lo que puedes obtener es un límite superior. La entropía real puede ser un orden de magnitud menor.

En su lugar, intente llenar la matriz con un hash criptográfico como MD5. Calcule una secuencia como md5(0), md5(1), ...(de cada valor tomado uno o más bytes, esto no importa). No obtendrá compresión alguna (sí, MD5 está roto, pero sigue siendo lo suficientemente bueno como para producir datos incompresibles).

Podemos decir que no hay entropía, sin embargo, medirías 8 bits / byte.

Cuando realmente necesita algo al azar, no solo tiene que usar una fuente HW, sino que también debe conocer un límite inferior seguro de cuánta entropía realmente produce. Si bien es probable que haya algo de aleatoriedad nanoTime(), no conozco ningún límite inferior no trivial.

Cuando necesita aleatoriedad para la criptografía, entonces realmente tiene que recurrir a algo proporcionado por su sistema operativo, su idioma o una buena biblioteca. Dichos proveedores recolectan entropía de múltiples fuentes y / o HW dedicados y se ha realizado bastante trabajo en tales estimaciones de entropía.

Tenga en cuenta que generalmente no necesita casi ninguna entropía. Un buen PRNG (determinista) inicializado con unos pocos bytes aleatorios es utilizable para la criptografía y, por lo tanto, también para todo lo demás.

Pensé que hablaría sobre el significado de "aleatorio". La mayoría de las respuestas aquí están hablando de la salida de procesos aleatorios , en comparación con la salida de procesos deterministas. Ese es un significado perfectamente bueno de "aleatorio", pero no es el único.

Un problema con la salida de procesos aleatorios es que son difíciles de distinguir de las salidas de procesos deterministas: no contienen un "registro" de cuán aleatoria fue su fuente. Un ejemplo extremo de esto es un famoso cómic de XKCD donde un generador de números aleatorios siempre regresa 4, con un comentario de código que dice que es aleatorio porque proviene de una tirada de dado.

Un enfoque alternativo para definir la "aleatoriedad", llamado complejidad de Kolmogorov , se basa en los datos en sí, independientemente de cómo se generaron. La complejidad de Kolmogorov de algunos datos (por ejemplo, una secuencia de números) es la longitud del programa de computadora más corto que genera esos datos: los datos son "más aleatorios" si tienen una mayor complejidad de Kolmogorov.

El uso de algoritmos de compresión como PNG, y la comparación de la longitud antes y después de la compresión, es similar a la idea de la complejidad de Kolmogorov. Sin embargo, la complejidad de Kolmogorov permite que los datos se codifiquen como un programa en cualquier lenguaje de programación completo de Turing, en lugar de un formato limitado como PNG; "descomprimir" tales codificaciones (programas) se realiza ejecutándolas, lo que puede tomar una cantidad arbitraria de tiempo y memoria (por ejemplo, más de lo que está disponible en nuestro pequeño universo).

El teorema de Rice nos dice que, en general, no podemos distinguir entre programas que se repiten para siempre y programas que generan nuestros datos. Por lo tanto, es muy difícil encontrar la complejidad de Kolmogorov de algunos datos: si escribimos un programa que genera esos datos, en realidad puede haber un programa más corto (es decir, una complejidad menor), pero no lo detectamos porque no pudimos distinguirlo de un bucle infinito. La complejidad de Kolmogorov es, por lo tanto, incuestionable, aunque si supiéramos los números de Busy-Beaver podríamos calcularlos utilizando esos para limitar la cantidad de tiempo que verificamos cada programa.

En el caso de sus datos de ejemplo, para encontrar su complejidad de Kolmogorov (es decir, "aleatoriedad intrínseca") necesitaríamos encontrar el programa determinista más corto que genere la misma secuencia de bytes y tomar su longitud.

Ahora podemos responder a su pregunta desde el punto de vista de la complejidad de Kolmogorov, y encontramos que la cita es correcta: no podemos generar números aleatorios (alta complejidad de Kolmogorov) por medios deterministas.

Por qué no? Imaginemos que escribimos un pequeño programa de computadora y lo usamos para generar una secuencia de números aleatorios. Se debe aplicar una de las siguientes situaciones:

• Generamos una gran cantidad de salida. Sin embargo, como sabemos que esta salida es generada por un pequeño programa, la salida (por definición) tiene una baja complejidad de Kolmogorov y, por lo tanto, no es "aleatoria" en este sentido.
• Generamos tan pocos números que escribirlos todos tomaría casi lo mismo, o incluso menos, bits que escribir nuestro programa de generación corto. En este caso, los números son relativamente incompresibles, lo que indica que son bastante aleatorios en el sentido de Kolmogorov. Sin embargo, dado que la cantidad de salida es comparable a la que pusimos (el código fuente del programa), es justo decir que el programa no "generó" la aleatoriedad, lo hicimos al elegir ese programa. Después de todo, en este caso, nuestro programa generador también podría haber sido una lista de estos números exactos (por ejemplo print([...])).

En cualquier caso, no estamos "generando" más aleatoriedad de la que ponemos (la "aleatoriedad" del código fuente de nuestro programa generador). Podríamos intentar solucionar esto utilizando un programa de generación más largo, para evitar que la salida tenga un generador corto, pero solo hay dos formas de hacerlo:

• Sistemáticamente "hinchar" el código de alguna manera. Sin embargo, la complejidad de Kolmogorov no se preocupa por el programa particular que hemos utilizado para generar los datos: sólo se preocupa por lo que el programa de generación es la más pequeña. La hinchazón sistemática no agrega la complejidad de Kolmogorov, porque tales patrones en el código pueden generarse con una cantidad muy pequeña de código. Por ejemplo, si tomamos run(shortGenerator)y agregamos una carga completa de hinchazón sistemática para obtener run(bloatedGenerator), todavía existe un generador corto de la forma run(addBloat(shortGenerator)).
• Agregue bloat de forma no sistemática , es decir, sin ningún patrón, de modo que una addBloatfunción tenga que terminar siendo tan hinchada como el código mismo. Sin embargo, estar tan desprovisto de patrones es exactamente lo que hace que algo sea aleatorio (alta complejidad de Kolmogorov). Por lo tanto la hinchazón del programa de generación de esta manera no aumentar la aleatoriedad (complejidad de Kolmogorov) de la salida, pero también aumenta la cantidad de aleatoriedad (complejidad de Kolmogorov) que tenemos para ofrecer en forma de código fuente. Por lo tanto, todavía somos nosotros los que estamos proporcionando la "aleatoriedad" y no el programa. En el ejemplo anterior de solo escribir print([...]), agregar una hinchazón no sistemática es equivalente a simplemente escribir más números "aleatorios" en esa lista codificada.

La compresión no es una prueba precisa de aleatoriedad, y tampoco es mirar una imagen y decir "eso parece aleatorio".

La aleatoriedad se prueba por métodos empíricos . De hecho, hay suites de software / algoritmos especialmente diseñados para probar la aleatoriedad, por ejemplo TestU01 y las pruebas Diehard .

Además, su imagen es, de hecho, una cadena de números 1D asignada a un espacio y, por lo tanto, no es una buena representación de ciertos patrones que pueden aparecer.

Si examinara su imagen píxel por píxel, lo más probable es que encuentre muchos patrones cortos de valor creciente antes de una caída repentina. Si creara un gráfico con el valor x como el número de muestra y el valor y siendo el valor obtenido de la función 'aleatoria', lo más probable es que sus datos se vean como una onda de diente de sierra:

Este es el patrón hecho por los valores que aumentan bajo la aritmética modular (cuyo cálculo es un ejemplo de: el tiempo aumenta a una tasa casi constante, y el & 0xFFactuar como mod 256).

Está confundiendo el concepto de números aleatorios de "números que parecen ser aleatorios".

Para entender la cita de von Neumann, tenemos que entender lo que significa "generar números aleatorios". La respuesta de Warbo vincula un excelente XKCD a este fin:

Cuando hablamos de números aleatorios, no estamos hablando de los valores en sí. Obviamente, un 4 no es más aleatorio que un 3. Estamos hablando de la capacidad de un tercero para predecir este valor mejor que la posibilidad aleatoria. Un número aleatorio es uno que no es predecible. A veces agregaremos condiciones a esto. Un generador de números pseudoaleatorio criptográficamente seguro (CSPRNG) genera números que no se pueden predecir mejor que una probabilidad aleatoria si un atacante no conoce la semilla / clave, pero si estamos hablando de números verdaderamente aleatorios (no pseudoaleatorios), generalmente se define como un número que no es predecible, incluso con un conocimiento completo del sistema, incluidas las teclas.

Ahora, su ejemplo, como muchos han señalado, no es determinista. El programa no especifica de qué valor sale System.nanoTime(). Por lo tanto, no está en la misma clase que usar un CSPRNG para generar números pseudoaleatorios. El primero puede ser no determinista, mientras que el segundo es determinista si el valor de la clave es determinista. El primero contiene operaciones que no están definidas para tener valores deterministas.

Sin embargo, notará que dije que puede ser no determinista. Tenga en cuenta que System.nanoTime()no está diseñado para proporcionar valores para este propósito. Puede o no ser suficientemente no determinista. Una aplicación puede ajustar el reloj del sistema de manera que todas las llamadas se System.nanoTime()produzcan en múltiplos de 256 nanosegundos (o cierre). O puede estar trabajando en Javascript, donde los recientes exploits de Spectre han llevado a los principales navegadores a disminuir intencionalmente la resolución de sus temporizadores. En estos casos, sus "números aleatorios" pueden volverse altamente predecibles en entornos que no planificó.

• Entonces generando números aleatorios con procesos deterministas ... pecado.
• Generando números aleatorios con hardware aleatorio dedicado ... no pecado.
• Generar números aleatorios con aspectos no deterministas de las computadoras ... tal vez pecado.

Todo depende de lo que pretendes. Si está encriptando sus cartas de amor a Bob Esponja para que su hermana no pueda leerlas, las demandas de sus llamados números aleatorios son bastante bajas. System.nanoTime()usado como lo hiciste probablemente sea lo suficientemente bueno. Si está protegiendo secretos nucleares contra un Estado extranjero avanzado que los está buscando activamente, puede considerar el uso de hardware diseñado para estar a la altura del desafío.

No creo que hayas entendido el reclamo. El punto es que si hay un procedimiento determinista para generar una serie de números 'aleatorios' (o cualquier cosa, en realidad), ¡encontrar el patrón es simplemente la tarea de encontrar este procedimiento!

Por lo tanto, siempre existe un método determinista para predecir el siguiente entero. ¡Esto es precisamente lo que no esperamos que suceda si suponemos aleatoriedad!

Cualquier determinismo suficientemente complejo es indistinguible de la estocasticidad.

--Desde la página de usuario de Wrzlprmft

Por lo tanto, incluso si algo parece aleatorio, ¿por qué demonios lo modelaríamos como 'aleatorio' si tenemos un procedimiento determinista para generarlo?

Este, creo, es el problema clave. Solo ha mostrado alguna forma de indistinguibilidad del PRNG y 'aleatoriedad verdadera'.

Sin embargo, que estos conceptos son por lo tanto iguales no se sigue. En particular, la aleatoriedad es un concepto matemático y teórico . Ya hemos demostrado anteriormente que, en teoría, considerar PRNG como "verdadera aleatoriedad" conduce a una contradicción. Por lo tanto, no pueden ser iguales.

Creo que otros ya lo señalaron, pero no fue eso lo que enfatiza, así que permítanme añadir también al debate.

Como otros ya señalaron, está el problema de medir la entropía. Los algoritmos de compresión pueden decirle algo, pero son independientes de la fuente. Como sabe más sobre cómo se generaron los datos, probablemente podría interpretar un algoritmo mucho mejor para comprimirlos, y eso significa que la entropía verdadera es mucho menor.

Además, estás confundiendo los significados de las frases "en computadora" y "determinista". Ciertamente puede realizar operaciones no deterministas en la computadora.

Además, de hecho, lo acabas de hacer , pero no es tan evidente a primera vista.

Un algoritmo determinista típico para una generación de números aleatorios es ie. PRNG como generador lineal congruencial. Son con estado. El estado interno significa menos entropía ya que el siguiente estado está determinado por el anterior. No profundizaré en eso, probablemente sea obvio para ti. El punto importante es que el algoritmo completamente determinista depende solo del estado anterior, sea lo que sea.

Ahora mira tu algoritmo. ¿En qué se basa? ¿Cuánto estado tienes? ¿Es determinista?

  file.writeByte((byte) (System.nanoTime() & 0xff));

Ignoremos file.writecualquier problema relacionado con la descarga de buffers, esperando E / S (¿trataste de agregar un ruido fuerte en los cables del disco duro por un momento? ¿No? ¡Oye, podrías hacerlo! centrémonos en la fuente, es más importante.

El tiempo es una especie de estado. Varía, pero la mayor parte es igual. Es por eso que trataste de eludirlo y tomaste & 0xFF para abandonar la mayor parte del estado. Pero no lo ha descartado todo, es posible que algún estado de la lectura anterior se filtre a la siguiente, por lo que ciertamente no es completamente no determinista *)

Pero no estamos interesados ​​en eso. Para "probar" que la cita es incorrecta:

Cualquiera que intente generar números aleatorios por medios deterministas está, por supuesto, viviendo en un estado de pecado.

Necesitas demostrarlo por medios deterministas.
Lo que nos interesa es: ¿ es su algo ciertamente totalmente determinista ?

... y es obvio que no lo es.

  System.nanoTime() & 0xff

Esa es una medida de tiempo. Tiempo y medida . La parte de medición puede hacerlo determinista, si el valor se almacena en caché. Supongo que no, de lo contrario esta función no tendría sentido. Entonces, si se lee sobre la marcha desde la fuente, tenemos un valor basado en el tiempo. Dado que ( supongo nuevamente ) que no lo ha ejecutado en un hardware dedicado de una sola tarea, a veces puede tener cambios de contexto. Incluso si tuviera un hardware dedicado de una sola tarea, la medición del tiempo aún puede no ser determinista, debido a las variaciones de temperatura / humedad en la fuente de tiempo, los tiempos de reloj del autobús, etc.

Estoy totalmente de acuerdo en que estoy exagerando aquí. Las derivas no serán tan grandes para causar un gran impacto (aunque en realidad nanotimepodrían ser). Más importante aún, nanotimeestá destinado a ser rápido. No lee de la fuente en tiempo real. Se basa en la instrucción interna del procesador / recuento de ciclos. Eso es realmente determinista, si se asegura de que no haya cambios de contexto.

Mi punto es que puede ser realmente muy difícil ejecutar un algoritmo verdaderamente 100% determinista si lo basa en el tiempo, y no tiene derecho a refutar esa cita a menos que tenga medios completamente deterministas.

*) Curiosamente, probablemente podría aumentar la aleatoriedad real si va por el camino duro. Haga & 0x01, bit a bit, y espere un hilo un tiempo notable, antes de leer cada bit. Generar datos de esa manera sería ridículamente largo, pero en realidad argumentaría que podría considerarse casi verdaderamente aleatorio, si IIF se ejecuta en no RTOS y también IFF en cada 'tiempo notable' es lo suficientemente alto como para garantizar que El sistema operativo se fue a dormir o cambió de contexto a otra tarea.

Creo que la respuesta que necesita comienza con este comentario que usted mismo hizo al responder otra respuesta:

El patrón es el resultado de la interacción de Java, la JVM, el sistema operativo, los cachés de CPU +, el disco duro, la música Trance que estaba transmitiendo que consume ciclos de CPU / RAM y todo lo demás. El patrón simplemente surge de una línea de código Java dentro de un bucle for / next. Una parte importante de la entropía proviene de los circuitos de hardware subyacentes.

Creo que ya te das cuenta de esto: no usaste medios deterministas para crear el patrón.

Usó una computadora, una parte no despreciable de la cual es determinista, pero la entropía provino de fuentes externas no deterministas (o al menos no deterministas para todos los propósitos y propósitos prácticos en este momento): usted o el mundo externo interactuando con la computadora (y en menor medida, cualquier imperfección física en el hardware de la computadora que pueda afectar los tiempos de las cosas).

Esto, por cierto, es una gran parte de cómo los sistemas operativos modernos siembran sus generadores de números aleatorios que están disponibles para los programas: al aprovechar la entropía en las interacciones con su hardware y el usuario que esperamos no sean predecibles para un atacante.

Por cierto, la entropía del mundo externo es en realidad un problema que debe abordarse hasta el día de hoy en criptografía bien codificada: computadoras que tienen un comportamiento predecibledurante el arranque y durante su tiempo de ejecución, como aquellos con almacenamiento de solo lectura o que arrancan desde la red, y que tienen un entorno de red predecible (ya sea no conectado a una red o la carga de trabajo en la red es lo suficientemente baja como para que todo se entregue dentro de una cantidad de tiempo confiable), y que ejecutan el mismo conjunto limitado de software con un comportamiento más o menos consistente, podrían sobreestimar en gran medida la entropía que obtienen de estos componentes supuestamente impredecibles, y terminar generando números mucho más predecibles de lo que obtendrías en una estación de trabajo típica que está haciendo todo tipo de otras cosas para ti (transmisión de música, sincronización con Dropbox, lo que sea) en segundo plano.

Creo que la mayoría de las respuestas se centran en si verificar los últimos ocho bits de mediciones de tiempo en nanosegundos tomados en un bucle es una buena manera de cosechar esa entropía. Esta es una pregunta muy importante para responder adecuadamente antes de usar el método en su ejemplo como un esquema de generación de números aleatorios en la práctica , pero es una pregunta separada de lo que creo que está preguntando.

Para agregar a respuestas anteriores, aquí hay una manera fácil de pensar sobre esta pregunta.

Se trata de la diferencia entre aleatorio y determinista . Luego iremos a Von Neumann y lo que estaba diciendo.

Números al azar

Un verdadero generador de números aleatorios no tendría un patrón, ni siquiera oculto en el fondo, que podríamos usar para predecir el próximo número dada la secuencia hasta el momento. En un mundo ideal, podrías saber todo lo que hay que saber en el universo físico y sobre el sistema, nanosegundo por nanosegundo, y aún sería inútil tratar de predecir el próximo número producido.

Ese es un caso ideal: en términos prácticos, llegamos allí al mezclar muchas fuentes que "no son malas aproximaciones" al azar, o que son realmente al azar, o que matemáticamente mezclan las cosas lo suficiente como para demostrar matemáticamente que se acercan mucho a lo impredecible y falta sesgo a cualquier número o patrón específico.

• Las fuentes "buenas" son cosas similares a esperar un proceso de desintegración radiactiva u otro proceso cuántico inherentemente impredecible. Salida de un semiconductor sensible al calor. Ruido aleatorio en un diodo u otro material eléctrico. Contando fotones del sol.

• Mezclados en esto, también podemos agregar algunos que consideramos "no malos" que ayudan, ya que no tienen ninguna conexión con estos: Esperando el próximo clic del mouse o paquete de red. Último bit de microtiempo en el siguiente archivo escrito. Salida de una función generadora de números pseudoaleatoria "aleatoria pero matemáticamente bastante aleatoria". Entropía previa de usos anteriores de números aleatorios.

El objetivo aquí es obtener un número que aún no se puede predecir , sea ​​lo que sea en el universo que conozca , y que estadísticamente sea tan probable como esto, sin un patrón matemáticamente detectable, sesgo o previsibilidad, y sin correlación con un evento que podría ser monitoreado y utilizado para la predicción. (O si se correlaciona con un evento, entonces se hace de una manera que hace que la conexión sea increíblemente tenue, como "dígito en nanosegundos solo la hora del último clic del mouse")

Números deterministas

Los matemáticos pueden probar cosas sobre fórmulas y funciones. Por lo tanto, es posible demostrar que una función, cuando se llama repetidamente, no da ningún sesgo o preferencia a ningún patrón, que no sea el patrón simple "estas son las salidas de esa función si se llama repetidamente".

Entonces, por ejemplo, si elige un número que dice entre 1 y 10 millones, escríbalo en binario y lo "pica" repetidamente, obtendrá una secuencia de dígitos de aspecto bastante aleatorio. Es casi aleatorio, pero en realidad no lo es en absoluto. Puede predecir dado el algoritmo y cualquier estado, cuál será el próximo número.

Lo llamamos "pseudoaleatorio" porque parece y parece ser principalmente aleatorio, incluso si no lo es.

Aquí hay un buen ejemplo. Piensa en esta secuencia de "números aleatorios" de 3 dígitos: 983, 367, 336, 244, 065, 664, 308, 602, 139, 494, 639, 522, 473, 719, 070, 217. Digamos que te digo Puedo generar un millón de números de la misma manera. Luego puede pasar a un estadístico que confirmará (dirá) que se distribuyen por igual o lo que sea. No hay un patrón predecible obviob. Se ven bastante al azar, ¿verdad? Pero ahora te digo que en realidad son

500 + dígitos de Pi, agrupados en 3s.

De repente, por aleatorio que sea

dígitos de Pi

puede ser, puede predecir de inmediato que los siguientes 2 números serán 986 y 094.

Para ser claros, no sé exactamente qué tan aleatorio

dígitos de Pi

son. Habrá sido estudiado y la respuesta bien conocida. Pero el punto es este: en principio, la misma conclusión es cierta para cualquier fuente que se produce siguiendo un proceso determinista .

Entre

Entre los dos, hay una amplia gama de "cosas que parecen aleatorias y que a menudo son aleatorias hasta cierto punto". Cuanto más aleatoriedad y casi aleatoriedad se pueda mezclar, menos propenso es la salida a poder detectar cualquier patrón o predecir matemáticamente cualquier salida.

De vuelta a von Neumann y su pregunta

Como puede ver, las salidas deterministas pueden parecer aleatorias, pero incluso estadísticamente pueden distribuirse aleatoriamente. Incluso podrían usar datos "secretos" o de cambio rápido que no tenemos una esperanza realista de conocer. Pero mientras sea determinista, los números nunca pueden ser verdaderamente aleatorios . Solo pueden estar "lo suficientemente cerca del azar como para que estemos felices de olvidar la diferencia".

Ese es el significado de la cita que diste. Un proceso determinista simplemente no puede dar números aleatorios. Solo puede dar números que parecen ser y se comportan como números aleatorios.

Ahora podemos reformular su pregunta de esta manera: "La salida de mi computadora (o cualquier otra moderna) puede verse y comportarse de manera totalmente aleatoria, ¿eso significa que la cita de von Neumann está desactualizada e incorrecta?"

El problema sigue siendo este: incluso si la salida de su computadora puede verse y comportarse aleatoriamente, aún puede no ser realmente aleatoria . Si solo se calcula de manera determinista, eso significa que no hay nada que no sea una causa-efecto predecible para obtener el siguiente número (eso es lo que significa "determinista" en este sentido). Comenzamos con algunos datos existentes (conocidos), aplicamos un proceso conocido (complejo o desordenado o lo que sea), y obtenemos lo que parece un nuevo "número aleatorio". Pero no es aleatorio, porque el proceso fue determinista.

Si dice que su método incluirá un verdadero generador aleatorio de hardware, para solucionarlo (como un número aleatorio generado por la desintegración radiactiva o el ruido en un semiconductor), su respuesta ahora podría ser aleatoria, pero su método por definición ya no es determinista , precisamente porque ya no puede predecir las salidas (o efectos) dadas las entradas / datos iniciales (causas) .

¡Von Neumann gana en ambos sentidos, casi por definición!