Liste von Zufallszahlengeneratoren

Pseudozufallszahlengeneratoren

Pseudozufallgeneratoren sind Deterministische Zufallszahlengeneratoren, die Pseudozufallszahlen erzeugen (engl. pseudo random number generator). Die von ihnen erzeugten Zahlenfolgen erscheinen zufällig, obwohl sie durch einen deterministischen Algorithmus errechnet werden.

Zuverlässige Generatoren

Diese nachfolgenden Pseudozufallszahlengeneratoren bestehen alle BigCrush-Tests der TestU01^[1]-Software-Suite, d. h. die generierte pseudozufällige Zahlenfolge ist von einer echt zufälligen mit diesen Tests nicht zu unterscheiden.

Der Begriff zuverlässig ist hier im stochastischen Sinn gemeint, es bedeutet nicht automatisch, dass eine generierte Sequenz auch kryptographisch sicher ist. An kryptographisch sichere Zufallszahlengeneratoren werden besondere Anforderungen gestellt.

Name	log2 k
Marsaglias KISS	> 124
Marsaglias LFIB4	287
ran1 (Numerical Recipes 3)	?
CMWC 4096	131086
Xorshift+ 128[2]	128
AES (CTR)	–
AES (OFB)	–
SHA-1 (CTR)	–
SHA-1 (OFB)	–
Whirlpool (CTR)	–
MRG32k3a[3][4]	191
ACORN[5][6][7]	30, 60, 90, 120, … 30t hängt von den Anfangsparametern ab

log₂ ist in den Tabellen der Zweierlogarithmus der Periodenlänge k. Die Angabe „> 124“ bedeutet also, dass die Periode des Generators länger als 2¹²⁴ ist, d. h. erst nach mehr als 2¹²⁴ erzeugten Zahlen beginnt er sich zu wiederholen.

Beschränkt zuverlässige Generatoren

Diese Pseudozufallszahlengeneratoren bestehen alle BigCrush-Tests^[1] außer denen auf lineare Abhängigkeit. Sie sind für praktische und nicht-kryptologische Zwecke einsetzbar. Es bedeutet jedoch, dass unter Umständen lineare Abhängigkeiten auftreten, falls größere Mengen solcher Zufallszahlen verwendet werden.

Name	log2 k	Fehlgeschlagene Tests
Mersenne-Twister	19937	2: LinearComp
WELL 512	512	7
WELL 1024	1024	5: MatrixRank, LinearComp, HammingIndep
WELL 19937	19937	2: LinearComp
WELL 44497	44497	2: LinearComp

Wenig bis nicht zuverlässige Generatoren

Diese Pseudozufallszahlengeneratoren bestehen einen Großteil der Tests nicht. Sie sollten nur verwendet werden, wenn beträchtliche stochastische Mängel der generierten Zahlenfolgen in Kauf genommen werden können.

Name	log2 k	Fehlgeschlagene Tests	Bemerkung
TT800	800	17
Xorshift (32/64/128)	32/64/128	fast alle/7/16
Alle linearen Rekurrenzgeneratoren		fast alle	klassischer Generator in Standardbibliotheken, z. B. rand() (aus stdlib.h oder PHP) bzw. drand48(), Java.util.Random, …

Weitere

• Blum-Blum-Shub-Generator
• Dual EC DRBG
• Inverser Kongruenzgenerator
• Kongruenzgeneratoren
  • Fibonacci-Generator
  • Verzögerter Fibonacci-Generator
• Maximum Length Sequence
• Multiply-with-carry

Echte Zufallszahlengeneratoren

Echte Zufallszahlengeneratoren sind Nichtdeterministische Zufallszahlengeneratoren, die echt zufällige Zahlenfolgen erzeugen (engl. random number generator). Ihre erzeugten Zahlenfolgen sind nicht reproduzierbar, so wie die Ziehung der Lottozahlen, und aperiodisch. Diese echten Zufallszahlengeneratoren erzeugen Zufallszahlen mit Hilfe physikalischer Prozesse. Sie sind meistens erheblich langsamer als Pseudozufallszahlengeneratoren, liefern also echte Zufallszahlen in (relativ) geringer Frequenz.

Zufallszahlen-Server

Zufallszahlen-Server verbinden die Erzeugung echter Zufallszahlenfolgen mit Hilfe nichtdeterministischer Zufallszahlengeneratoren und deren Darstellung über eine Webschnittstelle und Onlinedienste. Es können Angaben zur gewünschten Zahlenfolge gemacht werden, z. B. fünf zufällige Zahlen aus 50 Zahlen, wie beim Eurojackpot.

• random.org – basierend auf atmosphärischem Rauschen als Radioquelle
• qrng.physik.hu-berlin.de – basierend auf Quanten-Zufälligkeit von Photonen-Ankunftszeiten als Entropie-Quelle.

Hardware

Auf diese Weise erzeugte echte Zufallszahlen hoher Güte lassen sich als Startwert für deterministische Pseudozufallszahlengeneratoren verwenden.

• Intels RdRand-Befehl^[8]

Externe Entropie

Auf diese Weise erzeugte echte Zufallszahlen geringer Güte lassen sich als Startwert für deterministische Pseudozufallszahlengeneratoren verwenden.

• CryptGenRandom^[9], Microsoft Windows, Cryptography API
• die virtuelle Gerätdatei /dev/random^[10] unter Linux und anderen unixoiden Betriebssystemen.

Einzelnachweise

1. Pierre L'Ecuyer, Richard Simard: TestU01: A C library for empirical testing of random number generators, ACM Transactions on Mathematical Software, Volume 33 Issue 4, August 2007
2. Sebastiano Vigna: Further scramblings of Marsaglia's xorshift generators. April 2014; abgerufen im 1. Januar 1 (englisch). Describes xorshift+ generators, a generalization of XSadd. Also available directly from the author.
3. Pierre L'Ecuyer: Good Parameters and Implementations for Combined Multiple Recursive Random Number Generators, abgerufen am 11. Mai 2012
4. MRG32k3a Quellcode
5. Roy Wikramaratna (1989). ACORN – A new method for generating sequences of uniformly distributed Pseudo-random Numbers. Journal of Computational Physics. 83. 16–31.
6. Roy Wikramaratna (April 2019): Royal Society poster talk
7. Roy Wikramaratna (Juni 2019): Oxford University Numerical Analysis seminar
8. Intel: Bull Mountain Software Implementation Guide
9. CryptGenRandom function auf MSDN, abgerufen am 11. Mai 2012
10. random(4) – Linux manual page, abgerufen am 15. Mai 2012

• Pierre L'Ecuyer: TestU01 Bibliothek, abgerufen am 11. Mai 2012
• Pierre L'Ecuyer's publications, Universität von Montreal