Omgekeerde congruentiegenerator

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

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

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

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

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

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

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

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

Zie ook[bewerken]

lineaire congruentiegenerator

Referenties[bewerken]

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