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

,

met daarin de volgende parameters:
 de modulus 
 de vemenigvuldigingsfactor 
 de toename (increment) 

Door de keuze van de startwaarde  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  en , en dus de totale getallenreeks, kan berekenen.

Periode 
Door de modulus zullen de waarden van de geproduceerde reeks tussen 0 en  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 ), de reeks zal zich na een tijdje steeds herhalen. Dit wordt periodiek genoemd.
De periode van een algemene LCG is hoogstens , en voor sommige keuzes van  zelfs veel minder dan . Als gegeven is dat  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.  en  relatief priem zijn
2.  deelbaar is door alle priemfactoren van 
3.  een veelvoud is van 4 als  een veelvoud van 4 is.
In dit geval produceert de generator elk getal tussen 0 en  precies één keer en begint dan weer opnieuw. Het geeft dus een pseudowillekeurige permutatie van deze getallen. De startwaarde  kan elk getal uit deze verzameling zijn.
De multiplicatieve congruentiegenerator (met ) moeten dus een periode hebben met een lengte die kleiner is dan . De stelling van Carmichael stelt dat voor een gegeven  de lengte van de periode maximaal is dan en slechts dan als:
  en  relatief priem zijn,
  een primitief element modulo  is.

De juiste keuze van de parameters 
Voor dit type algoritme zal de kwaliteit van de generator volledig afhangen van de keuze van ,  en , omdat een generator die reeksen van pseudotoevalsgetallen produceert niet alleen volgens keuze van de  kan werken.

Een slecht voorbeeld 
Het willekeurig kiezen van ,  en  is geen goed idee, zie het volgende voorbeeld. Uit de lineaire congruentie generator met ,  en  krijgen we:
 met , de reeks: 10, 10, 10, 10, 10, ...
 met , 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 , 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 , 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 . 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  een deler is van , dan voldoet de rij  aan de lineaire congruentie:

in het bijzonder, met , voor een vaste , tussen 1 en , zien we dat de  minst significante bits een periode van maximaal  hebben, dit is duidelijk lager dan .

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  bits afkappen, hebben we een pseudotoevalsgetal tussen 0 en .

Keuze van de multiplier en de toename 
Om een vrije startwaarde  te kunnen kiezen tussen 0 en  moet geprobeerd worden om de periode van de generator te maximaliseren. Als de waarden van  en  gegeven zijn, kan een maximale periode verkregen worden (gelijk aan ). 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  van een reeks met een maximale periode wordt gedefinieerd als het kleinste getal zodanig dat:

Voor een reeks met maximale periode kan  worden genomen, en dus:

En met :

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 ,  en  kan het gedrag van de generator geoptimaliseerd worden en een groot aantal hypervlakken verkregen worden. Voor een gegeven  kan  met de volgende vuistregels geproduceerd worden:
  mag niet te groot of te klein zijn, bijvoorbeeld 
  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).

Algoritme