Omgekeerde congruentiegenerator

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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[bewerken]

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[bewerken]

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

Hypervlak gedrag[bewerken]

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[bewerken]

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[bewerken]

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[bewerken]

De maximale periode lengte is weer gelijk aan , en zal worden bereikt, als .

Zie ook[bewerken]

lineaire congruentiegenerator

Referenties[bewerken]

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