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  ( staat zoals gewoonlijk voor de verzameling van priemgetallen) 
 Factor 
 Toename 
 Startwaarde 
De standaardformule voor een omgekeerde congruentiegenerator is 

.

Voor uitleg van de symboliek, zie modulair rekenen. 
Wegens  is er voor elke   een unieke multiplicatieve inverse van elk element, ,  zodat . Alleen om  moet je je nog zorgen maken. Formeel zou het element  het omgekeerde van  worden. Aangezien  niet vertegenwoordigd is, kan deze het best overgeslagen worden door het te schrijven als .

Periodelengte
De maximale periodelengte kan niet groter zijn dan . Dit wordt bereikt als en slechts als de polynoom  een primitieve veelterm in  is.

Hypervlak gedrag
In tegenstelling tot lineaire congruentiegeneratoren waarvan de waarden zo weinig van hypervlakken verschillen, kan men hier aantonen dat elk hypervlak in  ten hoogste  punten van de vorm

bevat, zo lang . Door deze voorwaarde worden er nauwkeurig  punten afgescheiden. Daarbij kan   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  voor de berekening
 

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

Expliciete inverse generatoren
Soms leest men de definitie als: 

of

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 , en zal worden bereikt, als .

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

Algoritme