Was macht einen Pseudozufallsgenerator zu einem qualitativ hochwertigen?

8

Lesen Sie diese Antwort auf diese SO-Frage: Warum kombinieren wir keine Zufallszahlengeneratoren? , es spricht über

sehr hochwertiges PRNG (Pseudo Random Number Generator)

Ich frage mich daher, was ein qualitativ hochwertiges PRNG ausmacht. Ich nehme an, Sie können es als "zufälliger" zusammenfassen, aber

  • Frage 1: Welche Eigenschaften eines PRNG werden verwendet, um zu beschreiben, wie "zufällig" oder "gut" es ist?

  • Frage 2: Wenn Sie ein PRNG mit schlechter Qualität haben, gibt es eine Möglichkeit, die Qualität zu verbessern?

randomness pseudo-random-generators random-number-generator Jose
quelle
Relevante stackoverflow.com/questions/2130621/…
adrianN
2
Sie müssen auch weltliche PRNGs von kryptografisch sicheren RNGs unterscheiden.
AdrianN
1
Ein PRNG ist "besser", wenn es schwieriger ist, seine Ausgabe von vollständig zufälligen Bits zu unterscheiden.
Yuval Filmus

Antworten:

9

Es gibt mehrere Kriterien für die Qualität eines PRNG:

  • Wie schnell es geht. Dies beinhaltet, wie schnell es eingerichtet werden kann und wie schnell es ist, ein einzelnes Bit (amortisiert) zu erzeugen.
  • Wie schwierig es ist, das nächste Bit bei allen vorherigen Bits zu erraten.
  • Wie schwierig ist es, zwischen der Ausgabe des PRNG und wirklich zufälligen Bits zu unterscheiden.

Die letzten beiden Kriterien sind eng miteinander verbunden.

Wenn Sie ein PRNG von schlechter Qualität haben, können Sie es häufig durch Härteverstärkung verbessern . Nehmen Sie mehrere Kopien des PRNG (mit verschiedenen Zufallsschlüsseln) und XOR sie zusammen. In vielen (wenn auch nicht allen) Fällen wird dies die Qualität erheblich verbessern.

Yuval Filmus
quelle
Nur eine weitere Frage: Warum ein PRNG verwenden, das dieselbe Sequenz verursacht, wenn derselbe Startwert zweimal verwendet wird, und nicht jedes Mal, wenn eine neue Zufallszahl erforderlich ist, einen neuen Startwert (z. B. CPU-Uhr) erhalten? Wäre dieser Ansatz nicht zufälliger?
Jose
2
@ Jose Dies ist beabsichtigt. In vielen Fällen möchten Sie in der Lage sein, viele Male genau dieselbe Sequenz zu generieren. Zwei Beispiele sind Monte-Carlo-Experimente (die wiederholbar sein sollten) und Kryptographie (bei denen zwei Benutzer dieselbe zufällige Sequenz als Schlüssel verwenden sollen).
Yuval Filmus
Monte-Carlo-Experimente benötigen selten ein kryptografisches PRNG.
Xavier Combelle
2

Es gibt praktische Überlegungen: Wie einfach zu bedienen? Wie schnell? Wie einfach ist es, eine andere Folge von Zufallszahlen zu erzeugen? Wie einfach ist es, die Zufallszahlen wiederzugeben (wenn Sie beispielsweise 10 Milliarden Zufallszahlen generiert haben, können Sie dann genau dieselben 10 Milliarden Zufallszahlen erneut generieren?)

Die große Frage: Verhalten sich die generierten Zahlen wie eine Folge von Zufallszahlen? Das erste PRNG, das ich jemals verwendet habe, hatte die bizarre Eigenschaft von zwei aufeinanderfolgenden Werten, das zweite war mit einer Wahrscheinlichkeit von etwa 0,6 größer. Nicht sehr zufällig. Sie können also alle Arten von statistischen Tests durchführen und prüfen, ob sich Ihr Zufallszahlengenerator zufällig verhält. Je mehr es sich zufällig verhält, desto besser.

Und dann kommt die kryptografische Zufälligkeit. Wenn ich Ihnen die letzten n Zufallszahlen gebe und vollständig weiß, wie sich der Zufallszahlengenerator verhält, können Sie dann die nächste Zufallszahl vorhersagen? Wenn ja, ist dies in Situationen, in denen Sie Gegner haben, ungeeignet.

gnasher729
quelle
0

Ich würde der Liste der gewünschten Qualitäten eine gleichmäßige Verteilung hinzufügen .

Maciek Łoziński
quelle
Es versteht sich allgemein, dass ein PRNG eine gleichmäßige Verteilung (oder fast) erzeugt.
vonbrand