imported>Rigormath: /* Programmierung */ Erweiterter euklidischer Algorithmus: Linkziel ersetzt durch eines mit Beispiel zur Inversenberechnung.

2026-02-22T10:55:44Z

Programmierung: Erweiterter euklidischer Algorithmus: Linkziel ersetzt durch eines mit Beispiel zur Inversenberechnung.

Neue Seite

Ein '''inverser Kongruenzgenerator''' ist ein [[arithmetischer Zufallszahlengenerator]], der durch den [[Satz von Marsaglia]] bekannte Nachteile [[linearer Kongruenzgenerator]]en vermeidet. Insbesondere lässt er keine [[Hyperebene]]n entstehen. Verwendet man Zufallszahlen inverser Kongruenzgeneratoren für die [[Box-Muller-Methode]], so wird ein Spiralverhalten vermieden. Im Gegenzug verlangt er einen höheren Rechenaufwand.

== Allgemeines ==
Er besteht aus folgenden Komponenten:

*Modul <math>p \in \mathbb{P}</math> (<math>\mathbb{P}</math> steht hierbei wie üblich für die Menge der [[Primzahl]]en)
*Faktor <math>a \in \{0, ... , p-1\}</math>
*Inkrement <math>b \in \{0, ... , p-1\}</math>
*Startwert <math>y_0 \in \{0, ... , p-1\}</math>

Der Generator arbeitet nach folgendem Bildungsgesetz:
:<math>y_{n+1} = (a y_n^{-1} + b) \, \bmod \, p = ( a y_n^{p-2} + b ) \, \bmod \, p</math>

Zur Erklärung der Symbolik siehe den Artikel [[Modulo]].

Wegen <math>p\in\mathbb{P}</math> gibt es zu jedem <math>y_n \ne 0</math> ein eindeutiges multiplikativ inverses Element <math>y_n^{-1}</math>, so dass <math>y_n \, y_n^{-1} \equiv 1</math>. Nur für <math>y_n = 0</math> muss man sich noch Gedanken machen. Rein formal wäre <math>\infty</math> das inverse Element von <math>0</math>. Da <math>\infty</math> nicht darstellbar ist, wird es am besten übersprungen, indem man <math>0^{-1} = 0</math> setzt, wie es auch der zweiten Darstellung (mit <math>y_n^{p-2}</math>) entspricht.

=== Periodenlänge ===
Die maximale Periodenlänge kann offenbar <math>p</math> nicht überschreiten. Erreicht wird diese genau dann, wenn das Polynom
:<math>x^2 - bx -a</math>
ein primitives Polynom in <math>\mathbb{Z}_p</math> ist.

=== Hyperebenenverhalten ===
Im Gegensatz zu [[Kongruenzgenerator|linearen Kongruenzgeneratoren]], deren Werte ja auf wenigen Hyperebenen liegen, kann man hier zeigen, dass gilt:

:Jede Hyperebene in <math>\mathbb{Z}_p^k</math> enthält maximal <math>k</math> Punkte der Form
::<math>(x_1,\dots,x_k), (x_2,\dots,x_{k+1}),\dots</math>
: solange <math>x_l\cdots x_{l+k-2} \ne 0</math> gilt. Durch diese Bedingung scheiden genau <math>k-1</math> Punkte aus. Dabei ist <math>k\geq 2</math> beliebig wählbar.

=== Inverse Generatoren mit zusammengesetztem Modul ===
Um die Modulodivision durch das Abschneiden der höchstwertigen Bits ersetzen zu können, wäre es angenehm, Moduln <math>m</math> für die Berechnungsvorschrift

:<math>y_{n+1} = ( a y_n^{p-2} + b ) \, \bmod \, m</math>

zuzulassen, die keine Primzahl, sondern eine Potenz von 2 sind. Dazu muss <math>y_0</math> ungerade sein, und <math>a,b</math> müssen so festgelegt werden, dass alle <math>y_n</math> ungerade sind, denn dann kann das inverse Element zu <math>y_n</math> eindeutig berechnet werden. Die Periodenlänge beträgt höchstens <math>m/2</math>. Falls folgende Bedingungen erfüllt sind, beträgt sie genau <math>m/2</math>:
* <math>m=2^e \; \; \mbox{mit} \; \; e\geq 3</math>
* <math>a \equiv 1 \; (\bmod 4)</math>
* <math>b \equiv 2 \; (\bmod 4)</math>

=== Programmierung ===
Das folgende [[Programmiersprache|Programm]] in der [[Programmiersprache]] [[C++]] zeigt die Implementierung eines inversen Kongruenzgenerators mit <math>p=21269</math>, <math>a=8</math> und <math>b=3</math>. Es erzeugt 10 [[Zufallszahl]]en, die in einem [[Feld (Datentyp)|Array]] gespeichert werden. Das [[Multiplikation|multiplikativ]] [[Inverses Element|inverse Element]] von <math>y_n</math> [[modulo]] <math>p</math> wird mit dem [[Restklassenring#Invertierbarkeit und Inversenberechnung|erweiterten euklidischen Algorithmus]] bestimmt. Bei der Ausführung des Programms wird die Hauptfunktion ''main'' verwendet, die die Zufallszahlen auf der Konsole ausgibt.<syntaxhighlight lang="c++">
#include <iostream>
using namespace std;

// Diese Funktion bestimmt das multiplikative Inverse von a modulo b mithilfe des erweiterten euklidischen Algorithmus
int getModularMultiplicativeInverse(int a, int b)
{
if (a == 0)
{
return 0; // Spezialfall: Inverses von 0
}
int d = 1; // Deklaration der lokalen Variablen
int t = 0;
int u = 0;
int v = 1;
while (b != 0)
{
int q = a / b;
int b1 = b; // Variable zum Zwischenspeichern
b = a - q * b;
a = b1;
int u1 = u; // Variable zum Zwischenspeichern
u = d - q * u;
d = u1;
}
return d;
}

// Funktion, die die Zufallszahlen erzeugt
int* inversiveCongruentialGenerator(int y0, int p, int a, int b, int count)
{
int* randomNumbers = new int[count]; // Initialisiert das Array für die Zufallszahlen
randomNumbers[0] = y0; // Startwert für den Zufallszahlengenerator
for (int i = 0; i < count; i++)
{
randomNumbers[i] = (a * getModularMultiplicativeInverse(randomNumbers[i - 1], p) + b) % p;
}
return randomNumbers;
}

// Hauptfunktion die das Programm ausführt
int main()
{
int y0 = 0; // Deklaration der lokalen Variablen
int p = 21269;
int a = 8;
int b = 3;
int count = 10;
int* randomNumbers = inversiveCongruentialGenerator(y0, p, a, b, count); // Aufruf der Funktion
for (int i = 0; i < count; i++)
{
cout << randomNumbers[i] << endl; // Ausgabe auf der Konsole
}
}
</syntaxhighlight>

== Explizite inverse Generatoren ==
Manchmal liest man auch die Definition
:<math>y_{n+1} = (a n + b)^{-1} \mod p = ( a n + b )^{p-2}\, \bmod\, p</math>
oder auch
:<math>y_{n+1} = (a (n+y_0) + b)^{-1} \mod p = ( a (n+y_0) + b )^{p-2}\, \bmod\, p</math>
Letzteres stellt keine Verallgemeinerung dar; man erhält durch Ausmultiplizieren sofort die obige Gestalt.

=== Periodenlänge ===
Die maximale Periodenlänge beträgt wieder <math>p</math> und wird erreicht, falls <math>a\ne 0</math> gilt.

== Siehe auch ==

* [[Kongruenzgenerator]]
* [[Erweiterter euklidischer Algorithmus]]

== Literatur ==
* [[Harald Niederreiter]]: ''Random Number Generation and Quasi-Monte Carlo Methods.'' Society for Industrial & Applied Mathematics, Philadelphia PA 1992, ISBN 0-89871-295-5 (''Regional Conference Series in Applied Mathematics'' 63).

[[Kategorie:Zahlentheorie]]
[[Kategorie:Pseudozufallszahlengenerator]]

Inverser Kongruenzgenerator - Versionsgeschichte

imported>Rigormath: /* Programmierung */ Erweiterter euklidischer Algorithmus: Linkziel ersetzt durch eines mit Beispiel zur Inversenberechnung.