Omgekeerde congruentiegenerator

Een omgekeerde congruentiegenerator is een niet-lineaire toevalsgeneratoren die de modulaire multiplicatieve inverse gebruikt (indien aanwezig) om het volgende getal te genereren. Een omgekeerde congruentiegenerator is een rekenkundige bewerking die de bekende nadelen van lineaire congruentiegeneratoren door de stelling van Marsaglia vermijdt. In het bijzonder ontstaan geen hypervlakken. Als men gebruikmaakt van omgekeerde congruentiegeneratoren voor de Box-Muller-methode, wordt spiraalgedrag vermeden. In ruil daarvoor eist deze methode een hogere rekenkundige complexiteit.

Algemeen

De omgekeerde congruentiegenerator bestaat uit de volgende componenten:

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

De standaardformule voor een omgekeerde congruentiegenerator is

$y_{n+1}\equiv a{y}_n^{-1}+b\equiv a{y}_n^{p-2}+b(\mathrm{mod}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 $\mathrm{\infty }$ het omgekeerde van $0$ worden. Aangezien $\mathrm{\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\dots x_{l+k-2}\ne 0$. Door deze voorwaarde worden er nauwkeurig $k-1$ punten afgescheiden. Daarbij kan $k\ge 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}\equiv (a{y}_n^{p-2}+b)(\mathrm{mod}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\text{ met }e\ge 3$
• $a\equiv 1(\mathrm{mod}4)$
• $b\equiv 2(\mathrm{mod}4)$

Expliciete inverse generatoren

Soms leest men de definitie als:

$y_{n+1}\equiv (an+b{)}^{-1}\equiv (an+b{)}^{p-2}(\mathrm{mod}p)$

of

$y_{n+1}\equiv (a(n+y_0)+b{)}^{-1}\equiv (a(n+y_0)+b{)}^{p-2}(\mathrm{mod}p)$

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

Periodelengte

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 and Applied Mathematics (1992).
• Stallings, W., Cryptography and network security: principles and practice, University of Minnesota (1999).