Dado un algoritmo RNG y una serie de números ¿es posible determinar qué semilla produciría la serie?

Question

El código está en el Objetivo C pero debería ser comprensible si lo revisas incluso si no conoces el Objetivo C. Básicamente es un objeto RNG, instancias una nueva instancia, estableces la semilla si quieres y comienzas a agarrar al azar números.

Entonces, ¿es posible retroceder una serie dada de números para determinar la semilla utilizada para generar los números? Supongo que cualquier algoritmo dado no puede generar ningún conjunto aleatorio de números, ¿o sí?

decir que lo hago lo siguiente:

rng.seed = 1024; 
for (int i=1; i<11; i++) 
    DLog(@"%lu", [rng randomBetween:0 and:10]); 

Lo que me da la secuencia 10, 10, 8, 10, 2, 10, 9, 9, 7, 4. ¿Hay algún método o algoritmo que podría usar, dada la secuencia, para obtener el número 1024? Sé que esa es la secuencia válida para el 1024 visto, pero ¿qué es lo que acabo de inventar una secuencia ... 10, 1, 9, 6, 3, 9, 10, 3, 5, 2. ¿Hay alguna manera de saber si esa es una secuencia válida para este algoritmo y, de ser así, cuál es la semilla?

RNG.h:

@interface RNG : NSObject 
@property (assign) unsigned long seed; 
- (unsigned long)random; 
- (long)randomBetween: (long)min and: (long)max; 
@end 

RNG.m:

#define A 16807   /* a relatively prime number -- also M div Q */ 
#define M 2147483647L /* 0xFFFFFFFF/2 */ 
#define Q 127773L  /* M div A */ 
#define R 2836   /* M mod A */ 

@implementation RNG 
@synthesize seed = _seed; 

- (id)init { 
    self = [super init]; 
    if (self) { 
     self.seed = 0; 
    } 
    return self; 
} 


- (unsigned long)random { 
    self.seed = A * (self.seed % Q) - R * (self.seed/Q); 
    if (self.seed > M) 
     return (self.seed -= M); 
    else if (self.seed) 
     return (self.seed); 
    else 
     return (self.seed = 1L); 
} 


- (long)randomBetween: (long)min and: (long)max { 
    return ([self random] % (max - min + 1) + min); 
} 


- (void)seed: (unsigned long)new_seed { 
    if (new_seed == 0) 
     new_seed = 1; 
    while (new_seed > M) 
     new_seed -= M; 

    self.seed = new_seed; 
} 
@end 

Answer 1

Esto se parece a un "generador de congruencia lineal", véase http://en.wikipedia.org/wiki/Linear_congruential_generator "

Estos no ofrecen una buena seguridad criptográfica? , entonces sí, debería ser posible calcular una semilla que produzca la secuencia.

Answer 2

el código que publica es básicamente el mismo que el openbsd srandom - es un generador congruencia lineal que se implementa para evitar el redondeo (por eso contiene Q).

here is a paper on how to crack such a generator, pero espera que esté disponible la salida completa (no el valor "entre").

supongo que debe ser capaz de ampliar el enfoque en el papel para trabajar con "entre" usando el módulo aritmético del rango (presumiblemente necesitaría más muestras).

Answer 3

Su mejor opción es probablemente crear una matriz (o archivo de disco) que tenga el primer valor devuelto por su algoritmo elegido para cada semilla. Luego solo usa los que coinciden con el primer valor buscando una coincidencia más larga. De hecho, una tabla de base de datos sería genial, vienen a la mente gdbm o bsddb o sqlite.

Esto me suena a uno de esos problemas "Es computable, pero ...". IOW, se puede hacer, pero no es especialmente bonito.