Die Kongruenzgeneratoren bilden eine Klasse von Algorithmen, die zufällig aussehende Zahlenfolgen erzeugen. Die dadurch erzeugten Zahlen nennt man Pseudozufallszahlen, da sie deterministisch erzeugt werden und somit nicht wirklich zufällig sind. Kongruenzgeneratoren sind die bekanntesten und meistverwendeten rekursiven arithmetischen Zufallszahlengeneratoren.

Allgemeiner Kongruenzgenerator

Ein Kongruenzgenerator wird durch folgende Parameter definiert:

• Anzahl ${\displaystyle n\in \mathbb {N} ^{+}}$ der Zustandswerte
• Modul ${\displaystyle m\in \{2,3,4,\ldots \}}$
• Faktoren ${\displaystyle a_{1},\ldots ,a_{n}\in \left\{0,\ldots ,m-1\right\}}$ mit ${\displaystyle a_{n}>0}$
• Inkrement ${\displaystyle b\in \left\{0,\ldots ,m-1\right\}}$
• Startwerte ${\displaystyle y_{1},\ldots ,y_{n}\in \left\{0,\ldots ,m-1\right\}}$ (nicht alle 0, wenn ${\displaystyle b=0}$)

Für ${\displaystyle i>n}$ setzt man nun

${\displaystyle y_{i}=\left(\left(\sum _{k=1}^{n}a_{k}y_{i-k}\right)+b\right)\,{\bmod {\,}}m}$. Dabei bezeichnet ${\displaystyle \mod {}}$ den Divisionsrest; siehe Modulo.

Die so berechneten ${\displaystyle y_{i}}$ werden als Zufallszahlen verwendet.

Der Zustand des Generators vor der Erzeugung von ${\displaystyle y_{i}}$ wird durch die Werte ${\displaystyle y_{i-n},\ldots ,y_{i-1}}$ gegeben. Dieser Zustand legt (bei gegebenen ${\displaystyle n,m,a_{k},b}$) alle folgenden Zufallszahlen fest, da die nächste Zufallszahl und der nächste Zustand durch den aktuellen Zustand determiniert werden. Es gibt ${\displaystyle m^{n}}$ mögliche Zustände, und deshalb muss spätestens nach ${\displaystyle m^{n}}$ Schritten ein früherer Zustand wiederholt werden. Der Kongruenzgenerator erzeugt somit eine periodische Folge von Zahlen, wobei die Periodenlänge auch wesentlich kleiner als ${\displaystyle m^{n}}$ sein kann. Im Extremfall ist sie 1, und der Generator erzeugt immer die gleiche „Zufallszahl“. Bei der Festlegung der Parameter kommt es somit unter anderem darauf an, eine ausreichende Periodenlänge sicherzustellen.

Braucht man reelle Zufallszahlen im Intervall ${\displaystyle [0,1)}$, so kann man dafür die Näherung

${\displaystyle u_{i}:={\frac {y_{i}}{m}}}$

verwenden, falls der Modulo ${\displaystyle m}$ groß genug ist, um eine ausreichend feine Unterteilung zu ergeben.

Linearer Kongruenzgenerator

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

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

• Modul ${\displaystyle m\in \{2,3,4,\ldots \}}$
• Faktor ${\displaystyle a\in \{1,\ldots ,m-1\}}$
• Inkrement ${\displaystyle b\in \{1,\ldots ,m-1\}}$
• Startwert ${\displaystyle y_{1}\in \{0,\ldots ,m-1\}}$

Aus dem Startwert werden dann die weiteren Werte nach folgender Formel (mit ${\displaystyle i\geq 2}$) berechnet:

${\displaystyle y_{i}=(ay_{i-1}+b)\ {\bmod {\ }}m}$

Der lineare Kongruenzgenerator wurde 1949 von Derrick Henry Lehmer eingeführt. Er wird in den Laufzeitbibliotheken verschiedener Programmiersprachen zur Erzeugung von Pseudozufallszahlen verwendet, z. B. in C/C++ in der Funktion rand() in der Headerdatei stdlib.h.

In der Kryptographie dagegen kommt der lineare Kongruenzgenerator nicht zum Einsatz, da man schon aus wenigen Werten der erzeugten Zahlenfolge die Parameter ${\displaystyle a}$ und ${\displaystyle b}$ und damit die vollständige Zahlenfolge berechnen kann.

#include <iostream>
#include <stdint.h>
using std::cout;
using std::endl;

// Funktion, die die Zufallszahlen erzeugt
void linearCongruentialGenerator(uint64_t &y, uint32_t *randNumbers, int count)
{
    const uint64_t a = 6364136223846793005;
    const uint64_t b = 2531011;
    uint64_t r = y;  // lokale Variable für die Berechnung
    for (int i = 0; i < count; i++) {
        r = a * r + b;
        randNumbers[i] = r >> 32;
    }
    y = r; // Zustand zurückschreiben
}

int main()
{
    const int count = 10;        // Anzahl der Zufallszahlen
    uint32_t randNumbers[count]; // Array für die Zufallszahlen
    const uint64_t seed = 12345; // Startwert für den Generator

    uint64_t y = seed;           // Zustand des Generators
    linearCongruentialGenerator(y, randNumbers, count); // Erzeugung der Zufallszahlen

    for (int i = 0; i < count; i++) {
        cout << randNumbers[i] << endl; // Ausgabe auf der Konsole
    }
}

Fibonacci-Generator

Ein Fibonacci-Generator ist ebenfalls ein Kongruenzgenerator (mit ${\displaystyle n=2}$, ${\displaystyle b=0}$ und ${\displaystyle a_{1}=a_{2}=1}$) und besteht aus folgenden Komponenten:

• Modul ${\displaystyle m\in \{2,3,4,\dotsc \}}$
• Startwerte ${\displaystyle y_{1},y_{2}\in \{0,\dotsc ,m-1\}}$

Es sollte ${\displaystyle \operatorname {ggT} (m,y_{1},y_{2})=1}$ sein.

Mit folgender Bildungsregel werden die Pseudozufallszahlen erzeugt:

${\displaystyle y_{i}=(y_{i-1}+y_{i-2}){\bmod {m}}\quad ({\text{mit }}i\geq 3)}$

Eine Eigenschaft ist, dass die Fälle ${\displaystyle y_{i-1}<y_{i+1}<y_{i}}$ bzw. ${\displaystyle y_{i}<y_{i+1}<y_{i-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 ${\displaystyle y_{i}}$ zur Erzeugung der neuen Zufallszahl verwendet. Dies ergibt einen verzögerten (engl. 'lagged') Fibonacci-Generator:

${\displaystyle y_{i}=(y_{i-B}+y_{i-A}){\bmod {m}}\quad {\text{mit }}A,B\in \mathbb {N} ^{+},\ A>B;\quad i>A}$

mit den Startwerten ${\displaystyle y_{1},\dotsc ,y_{A}\in \{0,\dotsc ,m-1\}}$

Dann ist also ${\displaystyle n=A}$ und ${\displaystyle a_{A}=a_{B}=1}$, die übrigen ${\displaystyle a_{k}}$ sind Null. Dabei wählt man in der Regel ${\displaystyle m}$ gerade und ${\displaystyle A}$ und ${\displaystyle B}$ so, dass das Polynom in ${\displaystyle x}$

${\displaystyle x^{A}+x^{B}+1}$

ein primitives Polynom modulo 2 ist. Dann beträgt die Periodenlänge des Generators mindestens ${\displaystyle 2^{A}-1}$.

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

${\displaystyle x^{A}+x^{B}+1}$ ist genau dann ein primitives Polynom modulo 2, wenn dies für ${\displaystyle x^{A}+x^{A-B}+1}$ gilt. Somit kann man statt ${\displaystyle B}$ immer auch ${\displaystyle 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 ${\displaystyle y_{i-A}<y_{i}<y_{i-B}}$ oder ${\displaystyle y_{i-B}<y_{i}<y_{i-A}}$. Außerdem gibt es noch weitere Mängel.

Als Abhilfe wurde vorgeschlagen, immer nur ${\displaystyle A}$ aufeinanderfolgende Zahlen zu verwenden, und dann die nächsten ${\displaystyle 4A}$ bis ${\displaystyle 10A}$ Zahlen zu verwerfen. Dies funktioniert gut, aber um den Preis eines 5- bis 11-mal höheren Rechenaufwands. Der von Donald Knuth vorgeschlagene Generator ranarray arbeitet auf diese Weise. Bei ihm ist ${\displaystyle A=100}$ und ${\displaystyle B=37}$, und von 1009 aufeinanderfolgenden Zahlen wird immer nur ein Block von 100 Zahlen verwendet.

Um die Periode ${\displaystyle 2^{A}-1}$ sicherzustellen, kommt es nur auf das jeweils niederwertigste Bit in den Zustandswerten ${\displaystyle y_{i}}$ 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:

${\displaystyle y_{i}=(y_{i-A}+y_{i-B}+f(y_{i-C})){\bmod {m}};\quad f\colon \{0,\dotsc ,m-1\}\to \{0,2,4,6,\dotsc \},\;C\in \{1,\dotsc ,n\}}$

Andere

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

${\displaystyle y_{i}=\left(\sum _{k\in M}y_{i-k}\right){\bmod {m}}\quad {\text{mit}}\quad M\subset \mathbb {N} ^{+}}$.

${\displaystyle n}$ ist hier das größte Element in ${\displaystyle M}$. Um eine Periode von mindestens ${\displaystyle 2^{n}-1}$ zu garantieren, muss auch hier das entsprechende Polynom

${\displaystyle \sum _{k\in M}x^{k}+1}$ oder gleichbedeutend das Polynom ${\displaystyle x^{n}+\sum _{k\in M}x^{n-k}}$

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

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

${\displaystyle y_{i}=\left(\sum _{k=1}^{n}a_{k}y_{i-k}\right){\bmod {m}}}$

werden die ${\displaystyle a_{k}\in \{0,\dotsc ,m-1\}}$ derart gewählt, mit ${\displaystyle a_{n}\not \equiv 0{\pmod {p}}}$, dass das Polynom in ${\displaystyle x}$

${\displaystyle x^{n}-\sum _{k=1}^{n}(a_{k}{\bmod {p}})x^{n-k}}$

ein primitives Polynom modulo ${\displaystyle p}$ ist. Dann beträgt die Periodenlänge mindestens ${\displaystyle p^{n}-1}$.
Der vorige Generator ergibt sich daraus mit ${\displaystyle p=2}$ und ${\displaystyle a_{k}\in \{0,1\}}$ als Sonderfall, und ${\displaystyle n=1;\ p=m}$ liefert einen multiplikativen Kongruenzgenerator mit der Periodenlänge ${\displaystyle p-1}$.

Das Polynom ${\displaystyle f(x)=x^{n}-\sum _{k=1}^{n}a_{k}x^{n-k}}$ ist ein primitives Polynom modulo ${\displaystyle p}$, wenn die folgenden Bedingungen erfüllt sind:

(${\displaystyle {\text{sei }}r={\frac {p^{n}-1}{p-1}}{\text{ und }}a=(-1)^{n-1}a_{n}}$)

• ${\displaystyle a}$ ist ein primitives Element modulo ${\displaystyle p}$
• das Polynom ${\displaystyle x^{r}}$ ist kongruent zu ${\displaystyle a}$ (modulo ${\displaystyle f(x)}$)
• für alle Primfaktoren ${\displaystyle q}$ von ${\displaystyle r}$ ist der Grad des Polynoms ${\displaystyle x^{r/q}{\bmod {f}}(x)}$ positiv

Dabei wird Polynomarithmetik angewandt (siehe Polynome sowie Polynomdivision), und mit den Koeffizienten wird modulo ${\displaystyle p}$ gerechnet (sie sind Elemente des Restklassenrings ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$).

Siehe auch

• Liste von Zufallszahlengeneratoren

Einzelnachweise

1. ↑ Donald E. Knuth: The Art of Computer Programming. Volume 2: Seminumerical Algorithms. 3. Auflage. Addison-Wesley, 1997, ISBN 0-201-89684-2, S. 10–26
2. ↑ Stackoverflow-Forum:Understanding the algorithm of Visual C++'s rand() function
3. ↑ Rosetta Code: Linear congruential generator
4. ↑ GeeksforGeeks: Linear Congruence method for generating Pseudo Random Numbers

Weblinks

Abhandlung über Bitstrom-Verschlüsselungen