E 'possibile ottenere un'approssimazione di un seme in base a una sequenza finita di numeri casuali pseudo?

Question

supponiamo di avere alcuni numeri che formano una serie per esempio: 652,328,1,254 e voglio ottenere un seme che, se io, per esempio, fare

srand(my_seed);

mi metterò qualche tipo di approssimazione con l'errore limitato alla mia successione origonal, quando tutti i numeri che compaiono nello stesso ordine.

Answer 1

Dipende l'algoritmo utilizzato per la generazione pseudo-casuale. Se l'algoritmo è un semplice href="http://en.wikipedia.org/wiki/Linear_congruential_generator" lineare congruenziale generatore , quindi ottenere il seme posteriore è solo una questione di risolvendo un'equazione modulare lineare (si noti che la soluzione può essere non univoco, ma come un tale generatore è senza memoria, non importa).

Se l'algoritmo è più complesso, questo può essere impossibile.

Si noti che l'algoritmo utilizzato nella libreria standard C non è limitata dalla norma, in modo da piattaforme diverse possono avere diverse implementazioni.

Answer 2

Non si può avere un errore legato in generale. O il vostro algoritmo funziona o non è così. La ragione di questo è che un errore ragionevole bound è ovviamente molto più piccolo che RAND_MAX. Che a sua volta significa che i bit bassi non sono casuale come i bit superiori. Ma un buon PRNG fa certo che tutti i bit sono ugualmente casuale.

Si consideri l'esempio lento ma matematicamente suono di un algoritmo RNG:

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

Se si riesce a trovare alcuna correlazione significativa tra la sequenza di uscita e la state precedente, l'algoritmo AES dovrebbe essere considerato rotto.

Answer 3

.

Come Justin dice, è possibile fare marcia indietro un generatore congruente lineare (che rand() implementazioni sono spesso) quando si ha una sequenza di numeri generati. Credo che il problema è quello di sapere che uno dei valori precedenti è il seme originale ...

Answer 4

La definizione di un PRNG crytographic è quello in cui questa struttura esatta è computazionalmente impossibile - tuttavia, come è stato detto, ci sono PRNGs per cui ciò è possibile molto più debole (molto più veloce e). Quindi dipende dal vostro algoritmo.