Omgekeerde congruentiegenerator

Omgekeerde congruentiegeneratoren zijn een soort niet-lineaire congruentietoevalsgeneratoren, die de modulaire multiplicatieve inverse gebruiken (indien aanwezig) om naar het volgende nummer in een reeks te genereren. Een omgekeerd congruente toevalsgenerator is een rekenkundige bewerking die door de set van Marsaglia bekende nadelen van lineaire congruentiegeneratoren vermijdt. In het bijzonder ontwikkelt hij geen hypervlakken. Als men gebruik maakt van omgekeerde congruentietoevalsgeneratoren voor de Box-Muller-methode, dan wordt spiraalgedrag vermeden. In ruil daarvoor eist deze methode een hogere computationele complexiteit.

Algemeen

Het bestaat uit de volgende componenten:

• Modulo $p \in \mathbb{P}$ ($\mathbb{P}$ staat zoals gewoonlijk voor de verzameling van priemgetallen)
• Factor $a \in \{0, ... , p-1\}$
• Toename $b \in \{0, ... , p-1\}$
• Startwaarde $y_0 \in \{0, ... , p-1\}$

De standaard formule voor een omgekeerde congruentiegenerator is

$y_{n+1} = (a y_n^{-1} + b) \, \bmod \, p = ( a y_n^{p-2} + b ) \, \bmod \, p$. Voor uitleg van de symboliek, zie modulair rekenen. Wegens $p\in\mathbb{P}$ is er voor elke $y_n \ne 0$ een unieke multiplicatieve inverse van elk element, $y_n^{-1}$, zodat $y_n \, y_n^{-1} \equiv 1$. Alleen om $y_n = 0$ moet je je nog zorgen maken. Formeel zou het element $\infty$ het omgekeerde van $0$ worden. Aangezien $\infty$ niet vertegenwoordigd is, kan deze het best overgeslagen worden door het te schrijven als $0^{-1} = 0$.

Periodelengte

De maximale periodelengte kan niet groter zijn dan $p$. Dit wordt bereikt als en slechts als de polynoom $x^2 - bx -a$ een primitieve veelterm in $\mathbb{Z}_p$ is.

Hypervlak gedrag

In tegenstelling tot lineaire congruentiegeneratoren waarvan de waarden zo weinig van hypervlakken verschillen, kan men hier aantonen dat elk hypervlak in $\mathbb{Z}_p^k$ ten hoogste $k$ punten van de vorm

$(x_1,\dots,x_k), (x_2,\dots,x_{k+1}),\dots$

bevat, zo lang $x_l\cdots x_{l+k-2} \ne 0$. Door deze voorwaarde worden er nauwkeurig $k-1$ punten afgescheiden. Daarbij kan $k\geq 2$ gekozen worden.

Inverse generatoren met samengesteld modulo

Ter vervanging van de modulo deling door het afsnijden van de meest significante bits zou het handig zijn om modulo $m$ voor de berekening

$y_{n+1} = ( a y_n^{p-2} + b ) \, \bmod \, m$

toe te staan die geen priemgetal, maar een macht van 2 is. Daarvoor moet $y_0$ niet gegeven zijn, en $a,b$ moeten zo vastgesteld worden dat alle $y_n$ oneven zijn, omdat dan het inverse element van $y_n$ eenduidig berekend kan worden. De periodelengte is hoogstens $m/2$. Indien aan de volgende voorwaarden is voldaan, is het precies $m/2$:

• $m=2^e \; \; \mbox{met} \; \; e\geq 3$
• $a \equiv 1 \; (\bmod 4)$
• $b \equiv 2 \; (\bmod 4)$

Expliciete inverse generatoren

Soms leest men de definitie als:

$y_{n+1} = (a n + b)^{-1} \mod p = ( a n + b )^{p-2}\, \bmod\, p$

of

$y_{n+1} = (a (n+y_0) + b)^{-1} \mod p = ( a (n+y_0) + b )^{p-2}\, \bmod\, p$

De laatste is geen generalisatie van bovenstaande formule; deze wordt onmiddellijk verkregen door vermenigvuldiging van bovenstaande formule.

Periode lengte

De maximale periode lengte is weer gelijk aan $p$, en zal worden bereikt, als $a\ne 0$.

Zie ook

lineaire congruentiegenerator

Referenties

• Niederreiter, H., Random Number Generation and Quasi-Monte Carlo Methods, Society for Industrial & Applied Mathematics (1992).
• Stallings, W., Cryptography and network security: principles and practice, University of Minnesota (1999).