Consideraciones del generador aleatorio en el diseño de algoritmos aleatorios

Question

Es bien sabido que la eficiencia de los algoritmos aleatorios (al menos los de BPP y RP) depende de la calidad del generador aleatorio utilizado. Las fuentes aleatorias perfectas no están disponibles en la práctica. Aunque se demuestra que por todos los $ 0 < delta leq frac {1} {2} $ las identidades bpp = $ delta $ -bpp y rp = $ delta $ -rp Hold, no es cierto que el original El algoritmo utilizado para una fuente aleatoria prefecta se puede utilizar directamente también para una fuente de nube $ delta $. En cambio, se debe hacer algo de simulación. Esta simulación es polinomio, pero el algoritmo resultante no es tan eficiente como el original.

Además, en cuanto a mi conocimiento, los generadores aleatorios utilizados en la práctica generalmente ni siquiera son $ delta $-fuente, sino fuentes pseudo-aleatorias que pueden comportarse extremadamente mal en el peor de los casos.

De acuerdo a Wikipedia:

En la práctica común, los algoritmos aleatorios se aproximan utilizando un generador de números pseudorandom en lugar de una verdadera fuente de bits aleatorios; Tal implementación puede desviarse del comportamiento teórico esperado.

De hecho, las implementaciones de algoritmos aleatorios que he visto hasta ahora fueron meras implementaciones de los algoritmos para fuentes aleatorias perfectas que se ejecutan con el uso de fuentes pseudorandom.

Mi pregunta es, si hay alguna justificación de esta práctica común. ¿Hay alguna razón para esperar que en la mayoría de los casos el algoritmo devuelva un resultado correcto (con las probabilidades como en BPP resp. RP)? ¿Cómo se puede formalizar la "aproximación" mencionada en la cita de Wikipedia? ¿Se puede estimar de alguna manera la desviación mencionada, al menos en el caso esperado? ¿Es posible argumentar que un algoritmo aleatorizado de Monte-Carlo ejecutado en una fuente aleatoria perfecta se convertirá en un algoritmo estocástico bien comportado cuando se ejecute en una fuente pseudorandom? ¿O hay otras consideraciones similares?

Answer 1

Aquí hay una buena justificación. Suponga que utiliza un generador de números pseudorandom de fuerza criptográfica para generar los bits aleatorios que necesitan algún algoritmo aleatorizado. Luego, el algoritmo resultante continuará funcionando, siempre y cuando el algoritmo criptográfico sea seguro.

A generador de números pseudorandom de fuerza criptográfica es una herramienta estándar de la criptografía que acepta una semilla corta (por ejemplo, 128 bits de aleatoriedad verdadera) y genera un número ilimitado de bits pseudorandom. Viene con una garantía de seguridad muy fuerte: siempre que el primitivo criptográfico subyacente no esté roto, entonces los bits de pseudorandom serán completamente indistinguibles de los bits de los mandios verdaderos por ningún proceso factible (y, en particular, ningún algoritmo eficiente puede distinguir su producción de una secuencia de verdaderos bits aleatorios). Por ejemplo, podríamos obtener una garantía que diga: si el factoring es difícil (o, si RSA es seguro; o, si AES es seguro), entonces este es un buen generador pseudorandom.

Esta es una garantía muy fuerte, ya que se cree ampliamente que es muy difícil romper estas primitivas criptográficas. Por ejemplo, si puede encontrar una forma eficiente de tener en cuenta números muy grandes, entonces eso sería un resultado innovador. Para todos los efectos prácticos, puede actuar como si las primitivas criptográficas fueran inquebrantables. Esto significa que, a todos los efectos prácticos, puede actuar como si la salida de un generador de números pseudorandom de fuerza criptográfica sea básicamente la misma siempre que una secuencia de bits de aleación verdadera. En particular, esta es una buena fuente de aleatoriedad que necesita un algoritmo aleatorizado.

(He pasado por alto el hecho de que, para usar un PRNG criptográfico, todavía necesita encontrar 128 bits de verdadera aleatoriedad por su cuenta para formar la semilla. Pero generalmente esto no es difícil y, de hecho, hay herramientas criptográficas para ayudar con esa tarea también).

En la práctica, obtener bits pseudorandom extremadamente buenos es tan simple como

$ cat /dev/urandom

Answer 2

Es bien sabido que la eficiencia de los algoritmos aleatorios (al menos los de BPP y RP) depende de la calidad del generador aleatorio utilizado. Tengo que estar en desacuerdo. Lo que le brinda un buen conjunto de secuencia pseudurandom es una garantía sobre el rendimiento del algoritmo ejecutando una secuencia aleatoria del conjunto, en comparación con una secuencia aleatoria. Si no tiene tal garantía, no puede concluir que el algoritmo funcionará mal, simplemente no lo sabe.

¿Hay alguna justificación de esta práctica común? Funciona.

¿Es posible argumentar que un algoritmo aleatorizado de Monte-Carlo ejecutado en una fuente aleatoria perfecta se convertirá en un algoritmo estocástico bien comportado cuando se ejecute en una fuente pseudorandom? La teoría de la complejidad sufre de dos deficiencias. El primero es que es muy difícil probar algo (por ejemplo, P vs. NP está abierto). El segundo es que se preocupa principalmente por el análisis del peor de los casos. En conjunto, estas dos limitaciones descartan la teoría de la complejidad como un buen modelo para el comportamiento de los algoritmos en la práctica.