Liste von Zufallszahlengeneratoren

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Pseudozufallszahlengeneratoren[Bearbeiten]

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[Bearbeiten]

Diese 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
AES (CTR)
AES (OFB)
SHA-1 (CTR)
SHA-1 (OFB)
Whirlpool (CTR)
MRG32k3a[2][3] 191

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

Beschränkt zuverlässige Generatoren[Bearbeiten]

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[Bearbeiten]

Diese Pseudozufallszahlengeneratoren fallen bei einem Großteil der Tests durch. 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[Bearbeiten]

Echte Zufallszahlengeneratoren[Bearbeiten]

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[Bearbeiten]

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

Hardware[Bearbeiten]

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

  • Intels RdRand Befehl[4]

Externe Entropie[Bearbeiten]

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

Einzelnachweise[Bearbeiten]

  1. a b 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. Pierre L'Ecuyer: Good Parameters and Implementations for Combined Multiple Recursive Random Number Generators, abgerufen am 11. Mai 2012
  3. MRG32k3a Quellcode
  4. Intel: Bull Mountain Software Implementation Guide
  5. CryptGenRandom function auf MSDN, abgerufen am 11. Mai 2012
  6. random(4) - Linux manual page, abgerufen am 15. Mai 2012