Ist es möglich, auf einer endlichen Folge von Pseudozufallszahlen eine Annäherung an einen Samen Basis zu bekommen?

Question

nehme habe ich einige Zahlen, die eine Reihe bilden zum Beispiel: 652,328,1,254 und ich möchte einen Samen bekommen, wenn ich zum Beispiel tun

srand(my_seed);

Ich werde eine Art von Annäherung erhält mit begrenzten Fehlern meiner origonal Sequenz, wenn alle Zahlen in der gleichen Reihenfolge erscheinen.

Answer 1

Abhängig vom Algorithmus für die Pseudo-Zufallsgenerierung verwendet. Wenn der Algorithmus ist eine einfache Kongruenzgenerator , dann die Hinter Samen bekommen ist nur eine Frage der eine lineare modulare Lösung der Gleichung (man beachte, dass die Lösung kann nicht eindeutig sein, aber als Generator so ist, speicherlosen, es spielt keine Rolle).

Wenn der Algorithmus komplexer ist, dies nicht möglich sein kann.

Beachten Sie, dass der Algorithmus in der C-Standardbibliothek verwendet wird, nicht durch den Standard beschränkt, so verschiedene Plattformen können unterschiedliche Implementierungen haben.

Answer 2

Sie können keinen Fehler im Allgemeinen gebunden haben. Entweder Ihr Algorithmus funktioniert oder es funktioniert nicht. Der Grund dafür ist, dass ein vernünftiger Fehler gebunden ist natürlich viel kleiner als RAND_MAX. Das wiederum bedeutet, dass die die niedrigen Bits nicht so zufällig wie die höheren Bits. Aber ein guter PRNG stellt sicher, dass alle Bits gleich zufällig.

Betrachten Sie diese langsam, aber mathematisch Klangbeispiel eines RNG-Algorithmus:

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

Wenn Sie eine signifikante Korrelation zwischen der Ausgangssequenz und dem vorherigen state finden können, sollte der AES-Algorithmus gebrochen berücksichtigt werden.

Answer 3

Überprüfen Sie diese Frage out .

Wie Justin sagt, dann ist es möglich, einen linearen kongruenten Generator (die rand() Implementierungen oft sind) zurückzuzuverfolgen, wenn Sie eine Folge von erzeugten Zahlen haben. Ich denke, das Problem ist zu wissen, welche der vorherigen Wert die ursprüngliche Samen ist ...

Answer 4

Die Definition eines Cryptographic PRNG ist eine, in der genau diese Eigenschaft rechnerisch nicht machbar ist - aber, wie bereits erwähnt wurde, gibt es viel schwächer (und viel schneller) PRNGs, für die dies möglich ist. So ist es auf dem Algorithmus abhängt.