Erzeugung gleichverteilter Zufallszahlen

Zur Durchführung von stochastischen Simulationen werden Zufallszahlen, die gemäß bestimmter Wahrscheinlichkeitsverteilungen verteilt sind, benötigt. Diese Zufallszahlen gewinnt man durch verschiedene, verteilungsabhängige Methoden aus Zufallszahlen, die auf dem Intervall [0,1] gleichverteilt sind.

Generell können in einem deterministisch arbeitenden Computer keine echten Zufallszahlen erzeugt werden, sondern stets nur Pseudo-Zufallszahlen. Diese Peudo-Zufallszahlen sind zwar sind zwar ebenfalls näherungsweise auf dem Intervall [0,1] gleichverteilt und erfüllen eine Reihe von Kriterien echter Zufallszahlen, besitzen aber dennoch gewisse Regelmäßigkeiten, die echte Zufallszahlen nicht aufweisen. Für Anwendungen in der Kryptographie ist es wichtig, dass diese Regelmäßigkeiten möglichst gering ausfallen und insbesondere nicht aus einer Reihe von Pseudo-Zufallszahlen auf die jeweils nächste Pseudo-Zufallszahl geschlossen werden kann. Für die Anwendung in der stochastischen Simulation sind jedoch keine so starken Voraussetzungen notwendig, so dass hier häufig lineare Kongruenzgeneratoren zur Erzeugung von Zufallszahlen zur Anwendung kommen.

Bei einem linearen Kongruenzgenerator wird die jeweils nächste Zufallszahl (a_n+1) aus der vorherigen gewonnen, in dem der letzte Wert mit einer fest gewählten Zahl multipliziert (b) wird und anschließend ebenfalls ein fest gewählter Wert addiert (c) wird. Abschließend wird das Ergebnis modulo eines ebenfalls fest gewählten Wertes (m) betrachtet. Damit sich eine Verteilung zwischen 0 und 1 ergibt, werden die so ermittelten Zahlen durch den gewählten Modul geteilt:

a₀:=Startwert
a_n+1:=b⋅a_n+c mod m
Zufallszahlen: u_n:=a_n/m

Die Qualität der Zufallszahlen, d.h. wie gut die sich ergebenden Werte u_n eine Gleichverteilung auf [0,1] annähern, hängt von der Wahl von b, c und m ab.