2. Lineare Kongruenzgeneratoren

Lineare Kongruenzgeneratoren sind Generatoren für Pseudozufallsfolgen der Form:

X_n ist hierbei die n-te Zahl der Folge und X_n-1 ihr Vorgänger.

Die folgenden Werte sind konstant: a ist der Multiplikator, b das Inkrement und m der Modul. Der Startwert ist X₀ (seed). Dieser Wert kann beliebig gewählt werden. Die einzige Auswirkung bei der Wahl unterschiedlicher Startwerte ist, daß verschiedene unterschiedliche zufällige Folgen entstehen.

Um eine neue Zufallszahl zu erhalten, nimmt man die vorhergehende Zufallszahl, multipliziere sie mit einer Konstanten b, addiere das Inkrement und nehme das Ergebnis modulo einer Konstanten. Diese Operationen sind für den Computer einfach auszuführen.

Damit diese Methode sauber funktioniert sind bestimmte Regeln bei der Wahl von a, b und m einzuhalten. Diese Regeln geben einen gewissen Anhaltspunkt, wie die Konstanten zu wählen sind. Die Regeln wurden von D. E. Knuth entwickelt:

• m sollte groß sein,
• m sollte als eine Zweier- oder Zehnerpotenz gewählt werden,
• a sollte weder zu groß noch zu klein sein, eine günstige Wahl ist eine Zahl, die eine Ziffer weniger hat als m,
• a sollte auf x21 enden, x eine gerade Zahl sein

Die letzte Bedingung scheint eigenartig, doch sie verhindert das Auftreten bestimmter, möglicherweise problematischer Fälle die durch mathematische Analyse gefunden wurden.

Die Periode des Generators beträgt höchstens m. Bei guter Wahl von a, b und m erreicht der Generator die maximale Periode von m.

Das größte Problem des Generators besteht darin, daß er in einen Zyklus gelangen kann und viel früher, als erwartet, Zahlen erzeugt, die er bereits erzeugt hat. Dies ist zum Beispiel bei der Wahl von a=19, b=1, m=380 und dem Startwert 0 der Fall. Hierbei entsteht die Folge 0,1,20,0,1,20,... .

Lineare Kongruenzgeneratoren können in der Kryptographie nicht benutzt werden, da sie vorhersagbar sind. Sie wurden zum erstem Mal von Jim Reeds geknackt.

2.1 Softwareimplementierung eines linearen Kongruenzgenerators in C++

Folgendes Programm schreibt eine Zufallszahlenfolge in eine Datei namens "test.dat":

// *****************************************************************
// Linearer Kongruenzgenerater
// Programm erzeugt eine Folge von Zufallszahlen mittels Linearer 
// Kongruenz. Die Folge wird in einer Datei abgelegt.
// Autor: Martin Essig
// *****************************************************************
#include "iostream.h"
#include "fstream.h"

#define a 1291      // Multiplikator
#define b 4621      // Inkrement
#define m 21870     // Modul

#define m1 10000

#define start 1235  // Startwert (seed)

// Modulo-Multiplikation zur Verhinderung von Ueberlauf
// Eingabe : Die zu multiplizierenden Zahlen p,q
// Ergebnis : p * q
long mult(long p,long q)
{
 long p1,p0,q1,q0;

 p1 = p/m1; p0 = p%m1;
 q1 = q/m1; q0 = q%m1;

 return(((p0*q1+p1*q0) % m1)*m1+p0*q0) % m;
}

// Berechnet nächste Zufallszahl der Folge
// Eingabe : letzte Zufallszahl
// Ausgabe : nächste Zufallszahl
long random(long last)
{
 long result;

 result = (mult(last,a) + b) % m;  // Generator
 return result;
}

void main()
{
 ofstream output;
 long n,i;
 long result,ausgabe;

 result = start;

 cout << "Anzahl: "; // Anzahl der Zufallszahlen, die berechnet werden 
                     // sollen
 cin >> n;

 output.open("test.dat");

 i = 0;
 while (i < n)
 {
  result = random(result);
  ausgabe = result & 255;     // Ausgabe auf 8 bit gekuerzt
  output << "\n" << ausgabe;
  i++;
 }

 output.close();
}