Lineaire-congruentiegenerator

Een lineaire-congruentiegenerator is een speciale vorm van een congruentiegenerator. Het algoritme is een recurrente betrekking van de vorm:

$y_{i}\equiv ay_{i-1}+b{\pmod {m}}$,

met daarin de volgende parameters:

• de modulus $m\in \{2,3,4,\ldots \}$
• de vemenigvuldigingsfactor $a\in \{1,\ldots ,m-1\}$
• de toename (increment) $b\in \{1,\ldots ,m-1\}$

Door de keuze van de startwaarde $y_{0}\in \{0,\ldots ,m-1\}$ kunnen verschillende rijen gegenereerd worden. Het is echter mogelijk dat sommige startwaarden een resultaat geven dat meer op een rij toevalsgetallen lijkt, dan bij andere startwaarden.

Lineaire-congruentiegeneratoren (LCGs) behoren tot de oudste en bekendste pseudotoevalsgeneratoren. De LCG werd in 1949 geïntroduceerd door D.H. Lehmer. Het wordt in de run-time bibliotheken in de verschillende programmeertalen gebruikt voor het genereren van pseudotoevalsgetallen. In de cryptografie worden lineaire-congruentiegeneratoren echter niet gebruikt, omdat je met een paar waarden van de gegenereerde getallenreeks de parameters $a$ en $b$, en dus de totale getallenreeks, kan berekenen.

Periode

Door de modulus zullen de waarden van de geproduceerde reeks tussen 0 en $m-1$ liggen. Indien een getal voor de tweede keer verschijnt, wordt de gehele reeks herhaald vanaf dit getal, aangezien elke term geheel afhankelijk is van de vorige. Het aantal waarden dat de termen aan kunnen nemen is eindig (gelijk aan $m$), de reeks zal zich na een tijdje steeds herhalen. Dit wordt periodiek genoemd. De periode van een algemene LCG is hoogstens $m$, en voor sommige keuzes van $a$ zelfs veel minder dan $m$. Als gegeven is dat $b$ geen nul is, zal de LCG volgens een stelling van Donald Knuth een maximale periode hebben voor alle startwaarden dan en slechts dan als:

• 1. $b$ en $m$ relatief priem zijn
• 2. $a-1$ deelbaar is door alle priemfactoren van $m$
• 3. $a-1$ een veelvoud is van 4 als $m$ een veelvoud van 4 is.

In dit geval produceert de generator elk getal tussen 0 en $m-1$ precies één keer en begint dan weer opnieuw. Het geeft dus een pseudowillekeurige permutatie van deze getallen. De startwaarde $y_{1}$ kan elk getal uit deze verzameling zijn. De multiplicatieve congruentiegenerator (met $b=0$) moeten dus een periode hebben met een lengte die kleiner is dan $m$. De stelling van Carmichael stelt dat voor een gegeven $m$ de lengte van de periode maximaal is dan en slechts dan als:

• $y_{1}$ en $m$ relatief priem zijn,
• $a$ een primitief element modulo $m$ is.

De juiste keuze van de parameters

Voor dit type algoritme zal de kwaliteit van de generator volledig afhangen van de keuze van $a$, $b$ en $m$, omdat een generator die reeksen van pseudotoevalsgetallen produceert niet alleen volgens keuze van de $y_{0}$ kan werken.

Een slecht voorbeeld

Het willekeurig kiezen van $a$, $b$ en $m$ is geen goed idee, zie het volgende voorbeeld. Uit de lineaire congruentie generator met $a=25$, $b=16$ en $m=256$ krijgen we:

• met $y_{0}=10$, de reeks: 10, 10, 10, 10, 10, ...
• met $y_{0}=11$, de reeks: 11, 35, 123, 19, 235, 3, 91, 243, 203, 227, 59, 211, 171, 195, 27, 179, 139, 163, 251, 147, 107, 131, ...
• met $y_{0}=12$, de reeks: 12, 60, 236, 28, 204, 252, 172, 220, 140, 188, 108, 156, 76, 124, 44, 92, 12, 60, 236, 28, 204, 252, 172, ...

Het is duidelijk dat deze reeksen niet kunnen worden beschouwd als willekeurig. De parameters van de generator moeten dus zorgvuldig gekozen worden om getallen te krijgen die willekeurig lijken te zijn.

Keuze van de modulus

Congruentiegeneratoren bevatten een berekening modulo $m$, en dus een Euclidische deling, die belangrijke computatietijd kost bij veelvuldig gebruik van de generator. De eenvoudigste oplossing is om een module te gebruiken van het type $M=2^{e}$. Computers berekenen immers altijd binair en een dergelijke keuze is dus volledig transparant voor hen, waardoor een Euclidische deling onnodig is.

Deze keuze zorgt echter voor een belangrijke beperking: de zogenaamde minst significante bits (de meest rechtse bits) zijn veel minder willekeurig dan de meest significante bits (de meest linkse bits). Sterker nog, als $d$ een deler is van $m$, dan voldoet de rij $x_{n}\equiv y_{n}\mod d$ aan de lineaire congruentie:

$x_{n+1}\equiv (a\cdot x_{n}+b)\mod d$

in het bijzonder, met $d=2^{k}$, voor een vaste $k$, tussen 1 en $e$, zien we dat de $k$ minst significante bits een periode van maximaal $2^{k}$ hebben, dit is duidelijk lager dan $m$.

Om dit probleem te verhelpen kunnen we alleen de meest significante bits behouden, dat wil zeggen houd het meest linkse bit van het aantal verkregen. Als we de laatste $k$ bits afkappen, hebben we een pseudotoevalsgetal tussen 0 en $2^{e-k}-1$.

Keuze van de multiplier en de toename

Om een vrije startwaarde $x_{0}$ te kunnen kiezen tussen 0 en $m-1$ moet geprobeerd worden om de periode van de generator te maximaliseren. Als de waarden van $a$ en $c$ gegeven zijn, kan een maximale periode verkregen worden (gelijk aan $m$). Zie hierboven bij de paragraaf over Periode.

De potentie

De potentie is een concept dat bepaalde generatoren van onvoldoende willekeurige getallen zou uitsluiten. De potentie is altijd gedefinieerd als een reeks een maximale periode heeft. We kunnen de potentie niet altijd bepalen voor andere generatoren, en er zijn goede generatoren waarvoor de potentie niet is gedefinieerd.

De potentie $s$ van een reeks met een maximale periode wordt gedefinieerd als het kleinste getal zodanig dat:

$(a-1)^{s}\equiv 0\mod m$

Voor een reeks met maximale periode kan $x_{0}=0$ worden genomen, en dus:

$X_{n}\equiv {\frac {a^{n}-1}{a-1}}\cdot c\mod m$

En met $a^{n}=((a-1)+1)^{n}$:

$X_{n}\equiv c\cdot \left(n+{n \choose 2}\cdot (a-1)+\ldots +{n \choose s}\cdot (a-1)^{s-1}\right)\mod m$

Een potentie kleiner dan of gelijk aan drie is laag, omdat het resultaat niet willekeurig genoeg is. Een potentie van 5 of meer wordt aanbevolen. Merk echter op dat het concept van potentie alleen bestaat om enkele te slechte generatoren uit te sluiten. Een generator met een potentie groter dan 5 is niet meteen een goede generator, deze moet eerst een aantal tests ondergaan.

Hypervlakken

De lineaire congruentiegenerator heeft een hypervlak volgens de Stelling van Marsaglia. Door geschikte keuze van de parameters $m$, $a$ en $b$ kan het gedrag van de generator geoptimaliseerd worden en een groot aantal hypervlakken verkregen worden. Voor een gegeven $m$ kan $a$ met de volgende vuistregels geproduceerd worden:

• $a$ mag niet te groot of te klein zijn, bijvoorbeeld $0{,}01\cdot m<a<0{,}99\cdot m$
• $a$ moet willekeurig worden gekozen, het is dus geen dubbel of decimale representatie van een “rond” getal.
• Bij gemengde lineaire congruentiegeneratoren moet de “potentie” zo groot mogelijk zijn.

Referenties

• Gentle, J.E., Random Number Generation and Monte Carlo Methods. Springer, 2e editie (2003).
• Knuth, D.E., The Art of Computer Programming. Seminumerical Algorithms, deel 2, 3e editie (1998).