Das Kefk Network Wiki befindet sich im Testbetrieb.

Kongruenzgenerator

Aus Kefk.

(Weitergeleitet von Fibonacci-Generator)
Wechseln zu: Navigation, Suche

Der Kongruenzgenerator ist ein Algorithmus, der Zahlenfolgen erzeugt, die wie Zufallszahlen aussehen. Die so erzeugten Zahlen nennt man Pseudozufallszahlen, da sie deterministisch erzeugt werden und somit nicht wirklich zufällig sind. Kongruenzgeneratoren sind rekursive arithmetische Zufallszahlengeneratoren und wohl die bekanntesten und meistverwendeten Vertreter dieser Klasse.

Inhaltsverzeichnis

Allgemeiner Kongruenzgenerator

Ein Kongruenzgenerator wird durch folgende Parameter definiert:

  • Anzahl n \in \mathbb{N}^+ der Zustandswerte
  • Modul m \in \{2, 3, 4, ...\}
  • Faktoren a_1, ..., a_n \in \left\{ 0, ..., m-1 \right\}
  • Inkrement b \in \left\{ 0, ..., m-1 \right\}
  • Startwerte (Saat, engl. „Seed“) y_1, ..., y_n \in \left\{ 0, ..., m-1 \right\}

Für i > n setzt man nun

y_i = ( (\sum_{k=1}^{n} a_k y_{i-k} ) + b ) \, \bmod \, m.

Die so berechneten yi werden als Zufallszahlen verwendet. Braucht man reelle Zufallszahlen im Intervall [0;1[, so kann man dafür z. B.

u_i := \frac{y_i}{m}

als Näherung verwenden, falls der Modul m genügend groß ist, um eine ausreichend feine Unterteilung zu ergeben.

Der Zustand des Generators vor der Erzeugung von yi wird durch die Werte yi − n,...,yi − 1 gegeben. Dieser Zustand legt (bei gegebenen n,m,ak,b) alle folgenden Zufallszahlen fest, da die nächste Zufallszahl und der nächste Zustand durch den aktuellen Zustand determiniert werden. Es gibt mn mögliche Zustände, und deshalb muss spätestens nach mn Schritten ein früherer Zustand wiederholt werden. Der Kongruenzgenerator erzeugt somit eine periodische Folge von Zahlen. Bei der Festlegung der Parameter kommt es somit unter anderem darauf an, eine ausreichende Periodenlänge sicherzustellen.

Linearer Kongruenzgenerator

Mit n = 1 erhält man den Sonderfall eines linearen Kongruenzgenerators. Bei b = 0 wird er als multiplikativer Kongruenzgenerator bezeichnet, und für andere b als gemischter linearer Kongruenzgenerator.

Letzterer wird häufiger verwendet und hat vier natürliche Zahlen als Parameter:

  • Modul m \in \{2, 3, 4, ...\}
  • Faktor a \in \{1, ... , m-1\}
  • Inkrement b \in \{1, ... , m-1\}
  • Startwert y_1 \in \{0, ... , m-1\}

Aus dem Startwert werden dann die weiteren Werte nach folgender Formel (mit i \ge 2 ) berechnet:

y_i = (a y_{i-1} + b) \ \bmod \ m

Der lineare Kongruenzgenerator wurde 1949 von D. H. Lehmer eingeführt.[1] Er wird in den Laufzeitbibliotheken verschiedener Programmiersprachen zur Erzeugung von Pseudozufallszahlen verwendet. In der Kryptografie dagegen kommt er nicht zum Einsatz, da man schon aus wenigen Werten der erzeugten Zahlenfolge die Parameter a und b und damit die vollständige Zahlenfolge berechnen kann.

Periodenlänge

Lineare Kongruenzgeneratoren erreichen nach dem Satz von Knuth genau dann ihre maximal mögliche Periodenlänge m, wenn die folgenden Voraussetzungen erfüllt sind:

  • Das Inkrement b ist zum Modul m teilerfremd.
  • Jeder Primfaktor von m teilt a − 1.
  • Wenn m durch 4 teilbar ist, dann auch a − 1.

In diesem Fall erzeugt der Generator jede Zahl von 0 bis m − 1 genau einmal und beginnt dann wieder von vorn. Er liefert also eine pseudozufällige Permutation dieser Zahlen. Der Startwert y1 kann dann jede Zahl aus dieser Menge sein.

Der multiplikative Kongruenzgenerator (mit b = 0) weist, bei gegebenem m, nach dem Satz von Carmichael die maximal mögliche Periodenlänge auf (die kleiner als m ist) genau dann wenn:

  • y1 ist zu m teilerfremd
  • a ist ein primitives Element modulo m

Für einige Sonderfälle von m können die primitiven Elemente modulo m leicht bestimmt werden:

  • Ist m eine Zweierpotenz \ge 16, dann muss a mod 8 den Rest 3 oder 5 liefern. Die Periodenlänge ist dann m / 4, und der Startwert y1 muss ungerade sein. Es gibt zwei Perioden, die jeweils die Hälfte der ungeraden Zahlen von 1 bis m − 1 umfassen.
  • Wenn m eine Primzahl \ge 3 ist, dann muss für alle Primfaktoren q von m − 1 gelten:
a^{(m-1)/q} \ \bmod \ m \ne 1

Dann beträgt die Periodenlänge m − 1. Der Startwert y1 darf nicht Null sein.

Mängel der erzeugten Zahlen

Der lineare Kongruenzgenerator liefert keine vollkommen zufällig erscheinenden Zahlen. Man kann nachweisen, dass eine Abhängigkeit von aufeinanderfolgenden Zahlen besteht.

Teilperiode

Oft wählt man m = 2e, wobei e die Wortlänge des Rechners in Bit ist, denn dann muss man die Modulo-Division nicht explizit berechnen. Sie ergibt sich von selbst durch das Abschneiden der Überlauf-Bits. In diesem Fall verhalten sich die x niederwertigsten Bits der Zustandszahl yi wie ein Generator mit dem Modul 2x. Diese Bits wiederholen sich also spätestens nach 2x Schritten. Dies bedeutet insbesondere, dass das niederwertigste Bit bestenfalls die Periode 2 besitzt, also regelmäßig zwischen 0 und 1 wechselt. Beim multiplikativen Kongruenzgenerator ist es sogar konstant.

Allgemein gilt für alle linearen Kongruenzgeneratoren: wenn d ein Teiler des Moduls m ist, dann ergibt y_i \ \bmod \ d eine Zahlenfolge mit der Periode o \le d:

für ein o \in \{1, ..., d\} gilt: \forall i: y_{i+o} \equiv y_i \ ( \bmod \ d) .

Wenn der Generator nach dem Satz von Knuth die Periode m hat, dann beträgt die Länge o der Teilperiode genau d für alle Teiler d von m.

Wegen dieses Teilperioden-Verhaltens ist es ungünstig, Zufallszahlen r_i \in \{0, ..., k-1\} durch r_i := y_i \ mod \ k zu gewinnen, wenn k und m nicht teilerfremd sind. Dann würde der Divisionsrest r_i \ \bmod \ d für eine Zahl d, die k und m teilt, eine Periode der Länge höchstens d durchlaufen. Wenn man z. B. einen sechsseitigen Würfel simulieren will und m gerade ist, dann liefert r_i := y_i \ mod \ 6 Zahlen, die abwechselnd gerade und ungerade sind.

Mögliche Abhilfe:

  • Man verwendet einen multiplikativen Kongruenzgenerator mit einer großen Primzahl als Modul m und setzt r_i := y_i \ \bmod \ k. Dann sind aber die ri nicht gleichverteilt. Wenn k \ll m ist, kann man dieses Problem oft vernachlässigen.
  • Wenn m = 2e ist: die yi um e − f Bit nach rechts schieben, um die höchstwertigen Bits zu verwenden: r_i := \lfloor y_i / 2^{e-f} \rfloor (wobei 2f die kleinste Zweierpotenz \ge k ist). Wenn das Ergebnis r_i \ge k ist, wird es verworfen und neu erzeugt. Diese Methode liefert gleichverteilte Ergebnisse.

Hyperebenen-Verhalten

[[Hilfe:Cache|Fehler beim Thumbnail-Erstellen]]: convert: unable to open image `/var/www/kefk/w/images/a/a3/Lcg_3d.gif': No such file or directory.
„Hyperebenen­verhalten“ eines linearen Kongruenzgenerators in drei Dimensionen

Der lineare Kongruenzgenerator weist ein Hyperebenen-Verhalten auf, siehe Satz von Marsaglia. Durch geeignete Wahl der Parameter m, a und b kann man das Verhalten des Generators optimieren und eine große Zahl von Hyperebenen erreichen. Bei gegebenem m kann man a nach folgenden Faustregeln bilden:

  • a sollte weder zu groß noch zu klein sein, etwa: 0{,}01 \cdot m < a < 0{,}99 \cdot m
  • a sollte möglichst zufällig gewählt werden, also nicht in binärer oder dezimaler Darstellung eine „runde“ Zahl sein.
  • Beim gemischten linearen Kongruenzgenerator sollte die Potency möglichst groß sein. Sie ist der minimale Wert s, für den (a − 1)s ein Vielfaches von m ist. Donald E. Knuth empfielt, dass die Potency mindestens 5 sein sollte. Wenn m = 2e, dann sollte a \ \bmod \ 8 = 5 sein, um die maximal mögliche Potency \lceil e/2 \rceil zu erhalten.

Wenn man sichergehen will, dass der Generator gute Zufallszahlen erzeugt, sollte man sich nicht allein auf diese Faustregeln verlassen, sondern den Generator mit dem Spektraltest prüfen.

Wegen des Hyperebenen-Verhaltens greift man statt auf den linearen Kongruenzgenerator gelegentlich auf den inversen Kongruenzgenerator zurück, der dieses Problem nicht aufweist. Allerdings erfordert er einen höheren Rechenaufwand. Er ist kein Spezialfall des allgemeinen Kongruenzgenerators.

Fibonacci-Generator

Ein Fibonacci-Generator ist ebenfalls ein Kongruenzgenerator (mit n = 2, b = 0 und a1 = a2 = 1) und besteht aus folgenden Komponenten:

  • Modul m \in \{2, 3, 4, ...\}
  • Startwerte y_1, y_2 \in \left\{ 0, ..., m-1 \right\}

Mit folgender Bildungsregel werden die Pseudozufallszahlen erzeugt:

y_i = ( y_{i-1} + y_{i-2} ) \ \bmod \ m \quad (\mbox{mit} \ i \ge 3)

Eine Eigenschaft ist es, dass die Fälle yi − 1 < yi + 1 < yi bzw. yi < yi + 1 < yi − 1 nie auftreten. Fibonacci-Generatoren sind daher als Pseudozufallszahlengeneratoren wenig geeignet. Das gilt insbesondere für mathematische Objekte, zu deren Erzeugung mehr als zwei Zufallszahlen erforderlich sind. Würde man beispielsweise damit versuchen, eine zufällige Punktewolke in einem Würfel zu generieren, so kämen alle Punkte auf zwei Ebenen zu liegen.

Verzögerter Fibonacci-Generator

Das Prinzip des Fibonacci-Generators kann aber verallgemeinert werden, indem man nicht die beiden letzten, sondern weiter zurückliegende Zustandswerte yi zur Erzeugung der neuen Zufallszahl verwendet. Dies ergibt einen verzögerten (engl. 'lagged') Fibonacci-Generator:

y_i = ( y_{i-B} + y_{i-A} ) \ \bmod \ m \quad \mbox{mit} \; A,B \in \mathbb{N}^+, \ A > B; \quad i > A
mit den Startwerten y_1, ...,y_A \in \left\{ 0, ..., m-1 \right\}

Dann ist also n = A und aA = aB = 1, die übrigen ak sind Null. Dabei wählt man in der Regel m gerade und A und B so, dass das Polynom in x

xA + xB + 1

ein primitives Polynom modulo 2 ist. Dann beträgt die Periodenlänge des Generators mindestens 2A − 1.

Die folgende Tabelle gibt einige Wertepaare für A und B an, die diese Bedingung erfüllen:

A 2 31 55 73 98 135 258 607 3217 23209
B 1 13 24 25 27 22 83 273 576 9739

xA + xB + 1 ist genau dann ein primitives Polynom modulo 2, wenn dies für xA + xA − B + 1 gilt. Somit kann man statt B immer auch A − B verwenden.

Dieser Generator wird auch praktisch eingesetzt. Er liefert aber ebenfalls keine vollkommen zufällig erscheinenden Zahlen. Das Problem des einfachen Fibonacci-Generators wird nur verlagert: man hat niemals yi − A < yi < yi − B oder yi − B < yi < yi − A. Außerdem gibt es noch weitere Mängel.

Als Abhilfe wurde vorgeschlagen, immer nur n (die Zahl der Zustandswerte) aufeinanderfolgende Zahlen zu verwenden, und dann die nächsten 4n oder 5n Zahlen zu verwerfen. Dies funktioniert gut, aber um den Preis eines 5 bis 6 mal höheren Rechenaufwands.

Um die Periode 2A − 1 sicherzustellen, kommt es nur auf das jeweils niederwertigste Bit in den Zustandswerten yi an, also darauf, ob sie gerade oder ungerade sind. Man kann die höherwertigen Bits beliebig modifizieren, um die Qualität der erhaltenen Zufallszahlen zu verbessern. Beispielsweise:

y_i = (y_{i-A} + y_{i-B} + f(y_{i-C})) \ \bmod \ m; \quad f: \{0, ..., m-1\} \rightarrow \{0, 2, 4, 6, ...\}, \; C \in \{ 1, ..., n \}

Andere

Man kann den verzögerten Fibonacci-Generator weiter verallgemeinern, indem man mehr als zwei Zustandswerte verarbeitet:

y_i = ( \sum_{k \in M} y_{i-k} ) \ \bmod \ m \quad \mbox{mit} \quad M \subset \mathbb{N}^+ .

n ist hier das größte Element in M. Um eine Periode von mindestens 2n − 1 zu garantieren, muss auch hier das entsprechende Polynom

\sum_{k \in M} x^k + 1 oder gleichbedeutend das Polynom x^n + \sum_{k \in M} x^{n-k}

ein primitives Polynom modulo 2 sein (mit geradem Modul m). Ein so konstruierter Generator mit | M | > 2 liefert im allgemeinen bessere Zufallszahlen als mit | M | = 2, aber wiederum um den Preis eines höheren Rechenaufwands.


Mit einer weiteren Verallgemeinerung kann man bei gegebenem n die Periodenlänge vergrößern und wohl auch die Qualität der Zufallszahlen weiter verbessern. p sei ein Primfaktor von m. für die Berechnungsvorschrift

y_i = ( \sum_{k = 1}^{n} a_k y_{i-k} ) \ \bmod \ m

werden die a_k \in \{ 0, ..., m-1 \} derart gewählt, mit a_n \not\equiv 0 (\bmod \ p) , dass das Polynom in x

x^n - \sum_{k=1}^{n} (a_k \ \bmod \ p) x^{n-k}

ein primitives Polynom modulo p ist. Dann beträgt die Periodenlänge mindestens pn − 1.
Der vorige Generator ergibt sich daraus mit p = 2 und a_k \in \{ 0, 1 \} als Sonderfall.


Siehe auch

Zur Erklärung der Symbolik siehe den Artikel Modulo.

Quellen


Arithmetische Zufallszahlengeneratoren

Kongruenzgenerator (linearer, multiplikativer, gemischt linearer, Fibonacci-Generator) | Inverser Kongruenzgenerator | Mersenne-Twister

 
Wikipedia
 Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Kongruenzgenerator, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.
Von „http://www.kefk.org/wiki/Kongruenzgenerator“
Persönliche Werkzeuge