Als Zufallszahlengenerator, kurz Zufallsgenerator, bezeichnet man ein Verfahren, das eine Folge von Zufallszahlen erzeugt. Der Bereich, aus dem die Zufallszahlen erzeugt werden, hängt dabei vom speziellen Zufallszahlengenerator ab.
Man unterscheidet grundsätzlich zwischen nicht-deterministischen und deterministischen Zufallszahlengeneratoren. Nicht-deterministisch ist ein Zufallszahlengenerator, wenn er auch bei gleichen Ausgangsbedingungen unterschiedliche Werte liefert. Da die Implementierung einer Software-Prozedur in der Regel deterministisch arbeitet, muss zur Realisierung eines nicht-deterministischen Zufallszahlengenerators ein externer (beispielsweise physikalischer) Vorgang einbezogen werden. Ein deterministischer Zufallszahlengenerator liefert bei gleichen Ausgangsbedingungen dagegen immer die gleiche Folge von Zahlen. Oft werden beide Formen zu einem hybriden Generator kombiniert.
Zufallszahlen werden unter anderem bei verschiedenen Methoden der Statistik benötigt, z. B. bei der Auswahl einer Stichprobe aus einer Grundgesamtheit, bei der Verteilung von Versuchstieren auf verschiedene Versuchsgruppen (Randomisierung) oder bei der Monte-Carlo-Simulation. Typische weitere Anwendungsgebiete sind (Computer-, Glücks-)spiele und diverse Kryptographieverfahren.
Nichtdeterministische Zufallszahlengeneratoren Ein nichtdeterministischer Zufallszahlengenerator erzeugt Zufallszahlen aus einer als unvorhersagbar geltenden und somit nichtdeterministischen Entropiequelle. Zur Abgrenzung von deterministischen Zufallszahlengeneratoren wird dies auch als echter Zufallszahlengenerator bezeichnet (, TRNG).
Als Entropiequellen dienen entweder nichtdeterministische physikalische Prozesse oder die zeitliche Abfolge von nichtdeterministischen Systemereignissen. Die Messung physikalischer Prozesse erfordert eine Hardware-Komponente mit einem Sensor, weswegen diese als physikalischer Zufallszahlengenerator oder Hardware-Zufallszahlengenerator bezeichnet werden (, HRNG).
Physikalischer Zufallszahlengenerator Ein physikalischer Zufallszahlengenerator oder Hardware-Zufallszahlengenerator dient der Erzeugung von Zufallszahlen und nutzt dafür physikalische Prozesse wie etwa Rauschen.
Hierbei werden beispielsweise Impulsschwankungen 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;timer entropy daemon 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 Lottozahlen). 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 zusammenhängt.D. Meschede (Hrsg.): Gerthsen Physik. 23., überarbeitete Auflage, Springer 2006, S. 986) 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.W. Baier (Hrsg.): Elektronik Lexikon. 2. Auflage. Franckh’sche Verlagshandlung, Stuttgart 1982, S. 485.
Eine Methode zum Aufbau von Zufallsgeneratoren in digitalen Schaltungen besteht in der Ausnutzung der Metastabilität bei taktflankengesteuerten Flipflops.D. J. Kinniment et al.: Design of an on–chip random number generator using metastability. In: Proceedings of the 28th European Solid-State Circuits Conference, 24.–26. September 2002, S. 595–598.
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.Wolfgang Scheibe, Zufallsgeber in Geldspielgeräten, Automaten-Markt, Heft 5, 1966, S. 523–534, .
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.Giorgio Vazzana: Random Sequence Generator based on Avalanche Noise
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 deterministische, und deren Ergebnisse anschließend mithilfe eines Mischers miteinander zu kombinieren (siehe auch: Hybride Generatoren).George Marsaglia: Instructions for using DIEHARD – a battery of tests of randomness. Diehard.doc, 7. Januar 1997, S. 3 (englisch).
Nichtdeterministische Systemereignisse Betriebssysteme können als Entropiequelle Ereignisse nutzen, die beobachtet, aber nicht zuverlässig vorhergesagt werden können. Dazu zählen zum Beispiel: Benutzereingaben über Peripheriegeräte wie Maus, Tastatur und Touchscreen Ankunftszeit von Netzwerkpaketen Zeitliche Abfolge von Interrupts
Deterministische Zufallszahlengeneratoren Deterministische Zufallszahlengeneratoren erzeugen Pseudozufallszahlen und werden daher auch Pseudozufallszahlengeneratoren genannt (engl. , PRNG). Sie erzeugen eine Zahlenfolge, die zwar zufällig aussieht, es aber nicht ist, da sie durch einen deterministischen Algorithmus berechnet wird. Solche Pseudozufallszahlen sind von Computern wesentlich einfacher zu erzeugen, und entsprechende Generatoren sind in der Laufzeitbibliothek von praktisch allen höheren Programmiersprachen verfügbar.
Bei jedem Start der Berechnung mit gleichem Startwert (; Saat oder Saatkorn) wird die gleiche Folge erzeugt, weshalb diese später reproduziert werden kann, wenn Startwert und Algorithmus dokumentiert sind. Diese Eigenschaft der Reproduzierbarkeit ist bedeutsam für die Anerkennung wissenschaftlicher Experimente.
Güte eines Zufallszahlengenerators 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 Zufallszahlengenerators.
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 erkennbar ist. Es sollten im optimalen Fall auch alle möglichen Paare aufeinander folgender Ergebnisse mit den erwarteten Häufigkeiten auftreten, und ebenso auch Tripel, Quadrupel usw. Diese Überlegungen führen auf den Spektraltest.
Ein sehr einfaches Gütekriterium ist die Periodenlänge, die ausreichend lang sein sollte, damit sie bei der Anwendung des PRNG nicht vollständig durchlaufen wird, sich die erzeugten Zahlen also nicht wiederholen. Der Mersenne-Twister hat z. B. eine besonders große Periodenlänge. Ein PRNG wiederholt sich zwangsläufig, sobald ein bestimmter interner Zustand wiederholt auftritt. Die Periodenlänge kann also höchstens so groß sein wie die Zahl der möglichen Zustände. Wenn etwa der Zustand in einem Datenwort von 64 Bit gespeichert wird, beträgt sie höchstens . Dies betrifft insbesondere den linearen Kongruenzgenerator. Für diesen werden daher in der Regel die Parameter so gewählt, dass diese maximale Periodenlänge auch realisiert wird, was durch ein einfaches Kriterium geprüft werden kann (Satz von Knuth).