Kongruenzgeneratoren

Kongruenzgeneratoren sind eine Klasse von Pseudozufallszahlengeneratoren, die auf der Modulararithmetik beruhen. Sie erzeugen Sequenzen von Ganzzahlen nach einer Rekursion der Form X_{n+1} = (a X_n + c) mod m oder X_{n+1} = (a X_n) mod m. Aus diesen Zahlen lässt sich durch Division durch das Modul m oder durch Skalierung eine Folge von Zufallszahlen im Intervall [0,1) ableiten.

Die Parameter eines Kongruenzgenerators sind der Modulus m, der Multiplikator a, das Inkrement c und der Startwert (Seed) X_0. Ist c ≠ 0, handelt es sich um einen gemischten Kongruenzgenerator; ist c = 0, spricht man von einem multiplikativen Kongruenzgenerator. Die Qualität und die Länge der Periode hängen entscheidend von diesen Parametern ab.

Unter bestimmten Bedingungen liefert der Generator eine vollständige Periode von Größe m (Hull-Dobell-Theorem). Dazu müssen gcd(c, m) = 1, jeder Primfaktor von m teilt a − 1, und falls m durch 4 teilbar ist, auch a − 1 durch 4. In der Praxis entstehen jedoch oft Lücken in der Verteilung, besonders bei niedrigeren Bits oder wenn m eine Potenz von zwei ist. Tests wie der Spektraltest helfen bei der Beurteilung der Qualität.

Anwendungen liegen in der Monte-Carlo-Simulation, Computerspielen und einfachen Rechenaufgaben, bei denen Geschwindigkeit wichtiger ist als höchste statistische Güte. Kongruenzgeneratoren sind nicht kryptografisch sicher und können Muster erzeugen, weshalb moderne Anwendungen oft robuste Generatoren wie PCG oder Mersenne Twister bevorzugen. Dennoch bleiben sie historisch wichtig und in älteren Systemen verbreitet.