¿Cómo puedo determinar los valores iniciales del generador de números pseudoaleatorios si se da la secuencia?

Supongamos que supiera que un generador congruencial lineal genera una secuencia de números aleatorios. Es decir,

$x_{n+1}=(aX_n+c) \bmod m$

Si me dan todo el período (o al menos una gran subsecuencia contigua de la misma), ¿cómo puedo reconstruir los parámetros y que produjo esta secuencia? Estoy buscando un método general que pueda determinar los parámetros iniciales si se conoce el generador de números pseudoaleatorios. $a,c,m$ $x_0$

random-number-generation inverse-problem Paul
fuente

¿Qué se sabe exactamente? Desde una subsecuencia contigua no se puede saber dónde comenzó la secuencia , a menos que los elementos estén indexados en secuencia. Si es conocido, a continuación, y se descubren fácilmente.

x_{0}

$x_0$

m

$m$

a

$a$

c

$c$

hardmath

Respuestas:

Vea el artículo Cómo romper un generador congruente lineal , Haldir ("Equipo de ingeniería inversa", diciembre de 2004):

En este artículo presentaré un método que resolverá todos los valores de la LCG, incluido el módulo con seis o más números consecutivos de salida de PRNG.

El documento incluye el código fuente de "prueba de concepto" escrito en C, usando NTL de Victor Shoup para aritmética de precisión extendida.

hardmath
fuente

¡Ese fue un gran trabajo! :) ¿Conoces un método más general que pueda aplicarse a otros generadores de números aleatorios, no solo congruenciales lineales?

Paul

@Paul: Por supuesto, uno puede encontrar RNG que se "resuelven" fácilmente para sus parámetros a partir de datos de salida suficientes (problema inverso), pero parece que cuanto mejor sea el RNG (más aleatoria la apariencia de la salida), más difícil será la inversa El problema sería. La solución del caso LCG está relacionada con ciertos efectos de agrupamiento dimensional que son bien conocidos, lo que hace que los pares de valores generados se distribuyan de manera no uniforme. Para obtener más información, consulte Diseño de generador criptográficamente fuerte mediante la transformación de secuencias generadas linealmente

hardmath