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.

De omgekeerde congruentiegenerator bestaat uit de volgende componenten:

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

De standaardformule voor een omgekeerde congruentiegenerator is

${\displaystyle y_{n+1}\equiv ay_{n}^{-1}+b\equiv ay_{n}^{p-2}+b{\pmod {p}}}$.

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

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

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

${\displaystyle (x_{1},\ldots ,x_{k}),(x_{2},\ldots ,x_{k+1}),\ldots }$

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

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

${\displaystyle y_{n+1}\equiv (ay_{n}^{p-2}+b){\pmod {m}}}$

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

• ${\displaystyle m=2^{e}{\mbox{ met }}e\geq 3}$
• ${\displaystyle a\equiv 1{\pmod {4}}}$
• ${\displaystyle b\equiv 2{\pmod {4}}}$

Soms leest men de definitie als:

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

of

${\displaystyle y_{n+1}\equiv (a(n+y_{0})+b)^{-1}\equiv (a(n+y_{0})+b)^{p-2}{\pmod {p}}}$

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

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

lineaire congruentiegenerator

• 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).