Zufallszahlengenerator

Ein physikalischer Zufallszahlengenerator dient der Erzeugung von Zufallszahlen und benutzt dafür physikalische Prozesse.

Hierbei werden beispielsweise Impuls­schwankungen elektronischer Schaltungen (z. B. thermisches Rauschen eines Widerstands) oder radioaktive Zerfallsvorgänge ausgenutzt. Generell können alle natürlichen Quellen verwendet werden, die auf physikalischen Effekten basieren und eine recht hohe Güte liefern, aber auch andere asynchrone Quellen, wie z. B.:

• Atmosphärenrauschen (wie analoges Radio, das nicht auf einen Sender abgestimmt ist);
• CCD-Sensorrauschen (mit einer schlechten (z. B. alten Mobiltelefon-) Kamera in einem dunklen Raum fotografieren und daraus Zufallszahlen ableiten);
• radioaktiver Zerfall;
• Schwankung der tatsächlichen Zeitdauer einer mit einem Zeitgeber („Timer“) gemessenen Zeitdauer;[1]
• Spannungsschwankungen an einer Z-Diode;
• Lawinenrauschen an einer pn-Diode.

Allerdings gelten physikalische Zufallszahlengeneratoren nicht als schnell, da eine Unabhängigkeit und Gleichverteilung der erzeugten Zufallszahlen nur durch hinreichend große Abstände bei der Beobachtung der physikalischen Prozesse bzw. Abfangverfahren erreicht werden können. Dies ist aber nur eine Frage der verwendeten Technik, denn Zufallsprozesse wie thermisches Rauschen haben Grenzfrequenzen von vielen Terahertz.

Auch ist eine Reproduzierbarkeit der Ergebnisse prinzipiell nicht möglich, da die produzierten Zufallszahlen unvorhersagbar zufällig sind (so wie die Lotto­zahlen). Dadurch sind die produzierten Zufallszahlen aperiodisch, d. h. die sich nicht wiederholende Folge der Zufallszahlen ist (prinzipiell, d. h. wenn der Generator lange genug läuft) unendlich.

Beispielsweise kann ein Geigerzähler die Zahl der radioaktiven Zerfälle in einer bestimmten Zeitspanne messen. Man nutzt die Tatsache, dass ein radioaktives Nuklid nach einer zufälligen Zeit in sein Tochternuklid zerfällt. Die Zeitspanne hat aber beim gleichen Nuklid immer den gleichen Mittelwert (die sogenannte mittlere Lebensdauer, die mit der Halbwertszeit über den Faktor ${\textstyle {\frac {1}{ln(2)}}}$ zusammenhängt.[2]) Da der radioaktive Zerfall immer unabhängig von Umgebungsbedingungen abläuft, kann dieser Vorgang Zufallszahlen hoher Güte liefern.

Daneben können auch Rauschgeneratoren als Zufallsgeneratoren verwendet werden.[3]

Eine Methode zum Aufbau von Zufallsgeneratoren in digitalen Schaltungen besteht in der Ausnutzung der Metastabilität bei taktflankengesteuerten Flipflops.[4]

Gute physikalische Verfahren zur Generierung von Zufallszahlen sind auch das Würfeln und die Ziehung von Lottozahlen mit den dafür typischen Maschinen. Zufallsziehungen in relativ schneller Abfolge wurden bei elektromechanischen Glücksspielautomaten realisiert, und zwar auf Basis von Nockenscheiben mit Exzenterrrädchen und einem Schaltzeitvariator.[5]

Bei physikalischen Zufallszahlengeneratoren besteht jedoch das Problem der Alterung. Beispielsweise haben Geiger-Müller-Zählrohre eine Lebensdauer von typischerweise einer Billion Pulse und sind zudem abhängig von Temperatur, Magnetfeldern und der Versorgungsspannung. Zudem muss bei Geigerzählern die Pulsrate „deutlich höher“ als die Taktfrequenz sein, mit der die Pulse eingelesen werden. Eine Lösung dieses Problems besteht in der Verwendung vieler (mehr oder weniger guter) Zufallszahlengeneratoren, wobei von den erzeugten Zufallszahlen nur das letzte Bit verwendet wird, um damit die Modulo-Zwei-Summe zu bilden. Nach dem zentralen Grenzwertsatz der Statistik erhält man damit auch mit schlechten Zufallszahlengeneratoren zufällige Zufallsbits (sofern genügend viele Zufallszahlengeneratoren verwendet werden).

Eine der einfachsten Möglichkeiten, zufällige Sequenzen zu erzeugen, verwendet Lawinenrauschen in einem umgekehrt vorgespannten Übergang. Wenn eine Diode in Sperrrichtung vorgespannt ist, fließt tatsächlich nur ein sehr geringer Strom, und in erster Näherung kann die Diode als offener Stromkreis betrachtet werden. Wenn die Sperrspannung jedoch erhöht wird, wird ein Punkt erreicht, an dem der Strom dramatisch ansteigt. Dieser schnelle Anstieg des Stroms unter Sperrspannung kennzeichnet den Durchbruch, und die entsprechende angelegte Spannung wird als Durchbruchspannung bezeichnet. Es gibt zwei Mechanismen, die einen Zusammenbruch verursachen können, nämlich die Lawinenvervielfachung und das quantenmechanische Tunneln von Ladungsträgern durch die Bandlücke.

Die durch den großen Durchbruchstrom und die hohe Durchbruchspannung verursachte Erwärmung führt jedoch dazu, dass die Diode zerstört wird, wenn keine ausreichende Wärmeableitung bereitgestellt wird. Lawinenrauschen ist das Rauschen, das erzeugt wird, wenn eine pn-Diode zu Beginn des Lawinendurchbruchs betrieben wird. Es tritt auf, wenn Ladungsträger unter dem Einfluss des starken elektrischen Feldes genügend kinetische Energie erhalten, um durch Kollision mit den Atomen im Kristallgitter zusätzliche Elektron-Loch-Paare zu erzeugen. Wenn dieser Prozess in einen Lawineneffekt übergeht, können zufällige Rauschspitzen beobachtet werden. Um ein solches Rauschen zu erzeugen, kann man den Basis-Emitter-Übergang eines Kleinsignal-Transistors verwenden, da dieser Übergang für viele gängige Geräte eine relativ niedrige Durchbruchspannung hat. Die Menge an erzeugtem Rauschen hängt von den physikalischen Eigenschaften des Übergangs ab, wie zum Beispiel den verwendeten Materialien und dem Dotierungsniveau.[6]

Letztlich bieten auch noch so sorgfältig aufgebaute physikalische Zufallszahlengenerator keine Gewähr für ideale Zufallsfolgen. Der amerikanische Mathematiker und Informatiker George Marsaglia (1924–2011), der sich mehrere Jahrzehnte lang intensiv mit dieser Thematik befasst hat, und unter anderem eine Testsuite namens Diehard zur Prüfung der „Zufälligkeit“ von Zahlenfolgen entwickelte (siehe Weblinks), gab die explizite Empfehlung, zur Erzeugung von „guten“ Zufallsfolgen am besten mehrere – möglichst unterschiedliche – Verfahren zu benutzen, und zwar sowohl physikalische als auch deterministsche, und deren Ergebnisse anschließend mithilfe eines Mischers miteinander zu kombinieren (siehe auch: Hybride Generatoren).[7]

Es wird beispielsweise die Systemzeit bestimmt, innerhalb der eine Benutzer­aktion eintritt. Auf diese Weise erzeugte Zufallszahlen haben meist eine geringe Güte, lassen sich aber als Startwert für deterministische Verfahren verwenden.

Die erzeugten Zahlen können durch statistische Tests geprüft werden. Dazu gehört die erzeugte Verteilung (z. B. Normalverteilung, Gleichverteilung, Exponentialverteilung etc.) oder die Unabhängigkeit aufeinanderfolgender Zahlen. Wie gut die erzeugten Zahlen den statistischen Vorgaben entsprechen, bestimmt die Güte eines Zufalls­zahlen­generators.

Am Beispiel eines Zufallszahlengenerators, der nur die Zahlen 0 und 1 ausgeben kann (z. B. simulierter Münzwurf), kann man sich klarmachen, dass allein die gleiche Häufigkeit beider Ergebnisse nicht ausreicht, da etwa die Folge 0, 1, 0, 1, 0, 1, 0, 1, … bereits intuitiv als nicht zufällig erscheint. Es sollten im optimalen Fall auch alle möglichen Paare aufeinander folgender Ergebnisse mit den erwarteten Häufigkeiten auftreten, ja möglichst auch Tripel, Quadrupel usw. Diese Überlegungen führen auf den Spektraltest.

Ein sehr einfaches Gütekriterium ist die Periodenlänge, die im Verhältnis zum Wertebereich möglichst lang sein sollte. Dies ist etwa beim Mersenne-Twister in besonders starkem Maße der Fall. Ein simpler linearer Kongruenzgenerator kann dagegen den Wertebereich pro Periode bestenfalls einmal durchlaufen; dies sollte umgekehrt als Mindest­anforderung gesehen werden und kann durch ein einfaches Kriterium geprüft werden (Satz von Knuth).

Weitere Gütetests beruhen auf dem Chi-Quadrat-Test, dem Kolmogorow-Smirnow-Test u. a.

Knuth listet noch zahlreiche andere Tests, so den „serial test“, den Lücken-Test, den Poker-Test, den Couponsammler-Test, den Permutations-Test, den Lauf-Test, den Maximum-aus-${\displaystyle t}$-Test und den Kollisions-Test. Es kommt vor, dass ein Generator bei mehreren Tests sehr gut abschneidet, aber bei einem anderen versagt. Für einige Anwendungen wie Simulationen, die den entsprechenden Testbedingungen nahe sind, ist ein solcher Generator dann ungeeignet.[8]

Besonders strenge Anforderungen werden an kryptographisch sichere Zufalls­zahlen­generatoren gestellt.

Man betrachte die Nachkommastellen der Quadratwurzel einer natürlichen Zahl als Zufallszahlen (hierbei ist darauf zu achten, dass die resultierende Wurzel eine irrationale Zahl ist). Klassischerweise kann man statt ${\displaystyle {\sqrt {n}}}$ auch die Kreiszahl ${\displaystyle \pi }$ verwenden. Zwar ist hierbei garantiert, dass die erzeugte Zahlenfolge nicht periodisch ist; jedoch ist bei diesen Beispielen noch nicht einmal bekannt, ob sie gleichverteilt ist (von weitergehenden statistischen Tests ganz zu schweigen; siehe Normale Zahl).

• Arithmetische Zufallszahlengeneratoren basieren auf der Arithmetik. Irrationale Zahlen wie ${\displaystyle {\sqrt {2}}}$ oder ${\displaystyle e}$ können als Zufalls­zahlen­generatoren verwendet werden, indem man den gebrochenen Teil beliebiger Vielfache als Zufallszahlen nutzt. Nachteil des Verfahrens ist, dass sich irrationale Zahlen nur als Näherungs­werte innerhalb der Rechen­genauigkeit darstellen lassen.
• Rekursiver arithmetischer Zufallszahlengenerator: Diese Verfahren beruhen auf der Berechnung einer neuen Zufallszahl aus einer oder mehreren vorhergehenden Zahlen. Die neu erzeugte Zahl wird gespeichert und geht bei erneutem Aufruf des Zufalls­zahlen­generators in die Berechnung ein. Beim allerersten Aufruf des Zufalls­zahlen­generators muss ein willkürlich gewählter Startwert (oder mehrere), die Saat (meist engl. seed), verwendet werden.
  • Kongruenzgenerator
    • linearer Kongruenzgenerator
      • multiplikativer Kongruenzgenerator
      • gemischter linearer Kongruenzgenerator
    • Fibonacci-Generator
  • Inverser Kongruenzgenerator
  • Mersenne-Twister
  • Multiply-with-carry
  • Well Equidistributed Long-period Linear
  • Xorshift
  • Block- oder Stromchiffren, kryptologische Hashfunktionen

• Schieberegister mit Rückkopplung
  • lineares Schieberegister
  • nichtlineares Schieberegister

In der Programmiersprache C++ können Zufallszahlen mit der Funktion rand() der Standard­bibliothek generiert und auf einfache Weise verwendet werden.[9][10]

Ein einfacher Zufallsgenerator kann auch neu programmiert werden. Das folgende Programm zeigt die Implementierung eines linearen Kongruenzgenerators mit ${\displaystyle m=2147483648}$, ${\displaystyle a=214013}$ und ${\displaystyle b=2531011}$. Es erzeugt 10 Zufallszahlen, die in einem Array gespeichert werden. Bei der Ausführung des Programms wird die Hauptfunktion main verwendet, die die Zufallszahlen auf der Konsole ausgibt.[11][12]

#include <iostream>
using namespace std;

// Funktion, die die Zufallszahlen erzeugt
int* linearCongruentialGenerator(int y0, int m, int a, int b, int count)
{
    int* randomNumbers = new int[count]; // Initialisiert das Array für die Zufallszahlen
    randomNumbers[0] = (a * y0 + b) % m; // Erste Zufallszahl, setzt den nullten Eintrag schon vor dem Loop
    for (int i = 1; i < count; i++)
    {
        randomNumbers[i] = (a * randomNumbers[i - 1] + b) % m;
    }
    return randomNumbers;
}

// Hauptfunktion, die das Programm ausführt
int main()
{
    int y0 = 0;          // Startwert
    int a = 214013;      // linearer Faktor
    int b = 2531011;     // Offset
    int m = 2147483648;  // Modulus
    int count = 10;      // Anzahl der gewünschten Zufallszahlen
    int* randomNumbers = linearCongruentialGenerator(y0, m, a, b, count); // Aufruf der Funktion
    for (int i = 0; i < count; i++)
    {
        cout << randomNumbers[i] << endl; // Ausgabe auf der Konsole
    }
}