¿Es posible obtener una aproximación a una semilla en base a una secuencia finita de números pseudo-aleatorios?

Question

Supongamos que tengo algunos números que forman una serie por ejemplo: 652,328,1,254 y quiero obtener una semilla que si, por ejemplo, hago

srand(my_seed);

Me va a obtener algún tipo de aproximación con el error acotado a mi secuencia origonal, cuando todos los números que aparecen en el mismo orden.

Answer 1

depende del algoritmo utilizado para la generación pseudo-aleatorio. Si el algoritmo es un simple lineal congruente generador , a continuación, obtener la parte posterior semilla es sólo una cuestión de la solución de un lineal modular la ecuación (nota que la solución puede ser no único, sino como un generador de este tipo es sin memoria, no importa).

Si el algoritmo es más compleja, esto puede ser imposible.

Tenga en cuenta que el algoritmo utilizado en la biblioteca estándar C no está restringida por la norma, por lo que diferentes plataformas pueden tener diferentes implementaciones.

Answer 2

No se puede tener un límite de error en general. Puede ser que su algoritmo funciona o no lo hace. La razón de esto es que un error razonable unido es, obviamente, mucho más pequeño que RAND_MAX. Que en medios de giro que los los bits bajas no son tan al azar como los bits más altos. Pero un buen PRNG se asegura de que todos los bits son igualmente aleatoria.

Considere este ejemplo lento pero matemáticamente sonido de un algoritmo generador de números aleatorios:

int rand() {
  state = AES_encrypt(state);
  return state % RAND_MAX;
}
void srand(int seed) {
  state = AES_encrypt(seed);
}

Si usted puede encontrar ninguna correlación significativa entre la secuencia de salida y el state anterior, el algoritmo AES se debe considerar roto.

Answer 3

Salida esta pregunta .

Al igual que Justin dice, es posible dar marcha atrás un generador de congruencia lineal (que a menudo son implementaciones rand()) cuando se tiene una secuencia de números generados. Supongo que el problema es saber cuál de los valores anteriores es la semilla original ...

Answer 4

La definición de un PRNG criptográficos es aquella en la que esta propiedad exacta es computacionalmente imposible - sin embargo, como ya se ha mencionado, hay PRNG para los que esto sea posible mucho más débil (y) mucho más rápido. Por lo tanto, depende de su algoritmo.