Een congruentiegenerator is een algoritme dat pseudotoevalsgetallen genereert, dat wil zeggen getallenrijen die deterministisch worden gegenereerd en dus niet echt willekeurig zijn, maar veel kenmerken van toevalsgetallen hebben. Congruentiegeneratoren zijn de bekendste en meestgebruikte pseudotoevalsgeneratoren.

Een congruentiegenerator wordt bepaald door de volgende parameters:
 het aantal toestandswaarden  
 de modulus 
 de multipliers 
 de toename 

en het algoritme waarmee een nieuw gegenereerd getal gegenereerd wordt voor  door de recurrente betrekking:

.

Daarin zijn  de startwaarden.

Reële toevalsgetallen in het interval [0, 1] kunnen verkregen worden als , mits  groot genoeg is om een voldoende nauwkeurige onderverdeling te geven.

De toestand van de generator voor de productie van  wordt gegeven door de startwaarden. Deze toestand legt (voor gegeven , , , ) alle volgende toevalsgetallen vast, omdat het volgende toevalsgetal en de volgende toestand door de huidige toestand bepaald worden. Er zijn  mogelijke toestanden, en daarom moet er na maximaal  stappen een eerdere toestand herhaald worden. De congruentiegenerator produceert dus een periodieke rij getallen, waarbij de lengte van de periode veel kleiner dan  kan zijn. In extreme gevallen is de lengte 1, en zal de generator altijd hetzelfde "toevalsgetal" geven. Bij het kiezen van de parameters is het dus onder andere van belang om te zorgen voor een periode die lang genoeg is.

Lineaire congruentie
Als , spreekt men van een lineaire-congruentiegenerator. Het algoritme is:

.

Is ook nog , dus

,

dan is er sprake van een multiplicatieve-congruentiegenerator. De multiplicatieve congruentie heet ook Lehmer-congruentie, naar D. H. Lehmer die dit algoritme in 1949 introduceerde.

Fibonacci-generator 
Een Fibonacci-generator is een congruentiegenerator met ,  en , en bestaat uit de volgende componenten:
 Modulus 
 Startwaarden 
Met de volgende functie worden de pseudowillekeurige getallen gegenereerd: 
.

Een kenmerk is dat de gevallen  respectievelijk  nooit voorkomen. Fibonacci-generatoren zijn dus niet geschikt als pseudotoevalsgenerator. Dit geldt met name voor wiskundige objecten waarvoor de productie van meer dan twee toevalsgetallen nodig is. Als men bijvoorbeeld probeert om een willekeurige wolk van punten in een kubus te genereren, dan zouden alle punten op twee vlakken liggen.

Vertraagde Fibonacci-generator 
Het principe van de Fibonacci-generator kan worden gegeneraliseerd door niet de laatste twee, maar verder terug liggende waarden  te gebruiken om een nieuw toevalsgetal te genereren. Dit resulteert in een vertraagde (Eng. 'lagged') Fibonacci-generator:

met de startwaarden .

Dan is  en  en de andere  zijn nul. Hierbij wordt  in het algemeen even gekozen en  en  worden gekozen, zodat de polynoom in :  een primitieve polynoom modulo 2 is. De periode van de generator is dan minimaal .

 is een primitieve polynoom modulo 2 dan en slechts dan als  dat ook is. Zo kan men in plaats van  ook altijd  berekenen.

De volgende tabel geeft enkele waarden voor  en  die aan deze voorwaarde voldoen:

{| class="wikitable"
! A
| 2|| 31|| 55|| 73|| 98|| 100|| 135|| 258|| 607|| 3217|| 23209
|-
! B
| 1|| 13|| 24|| 25|| 27|| 37|| 22|| 83|| 273|| 576|| 9739
|}

Deze generator wordt ook gebruikt in de praktijk. Het geeft echter niet altijd volledig willekeurige getallen. Het probleem van de gewone Fibonacci-generator is slechts verschoven; nu komen  of  nooit voor. Er zijn zelfs nog meer tekortkomingen.

Als oplossing werd voorgesteld om altijd alleen gebruikmaken van  opeenvolgende nummers, en dan de volgende  tot  getallen te verwerpen. Dit werkt goed, maar zorgt voor een 5 tot 11 keer hogere computatietijd. De door Donald Knuth voorgestelde generator ranarray werkt op deze manier. Hierbij is  en , en van 1009 opeenvolgende getallen wordt slechts een blok van 100 getallen gebruikt.

Om voor een periode van  te zorgen, is alleen de minst significante bit in de toestandswaarde  van belang, dat wil zeggen, dat het van belang is of de bit even of oneven is. Het is mogelijk om de hogere orde bits naar behoefte te veranderen, om de kwaliteit van de resulterende toevalsgetallen te verbeteren. Bijvoorbeeld:

Verdere veralgemening 
Men kan de vertraagde Fibonacci-generator verder veralgemenen door meer dan twee toestandswaarden te verwerken:
.
Hier is  het grootste element in . Om een periode van ten minste  te garanderen, moet ook hier de bijbehorende polynoom  of equivalent, de polynoom  een primitieve polynoom modulo 2 zijn (met een even modulus ). Een generator die zo opgebouwd is met  levert over het algemeen beter toevalsgetallen dan met , maar ook dit gaat ten koste van de rekentijd.

Met een verdere generalisering kan voor een gegeven  de lengte van de periode verhoogd worden en waarschijnlijk ook de kwaliteit van willekeurige getallen verbeterd worden.  is een priemfactor van . Voor de rekenregel

zullen de , met , zodanig worden geselecteerd dat de polynoom in 
 
een primitieve polynoom modulo  is. Dan is de periode ten minste .

De vorige generator vloeit hieruit voort met  en  als een bijzonder geval, en  levert een multiplicatieve congruentiegenerator met periode .

De polynoom  is een primitieve polynoom modulo p als 
 en 
voldoen aan:
  is een primitief element modulo 
 de polynoom  is congruent aan  (modulo )
 voor alle priemfactoren  van  is de graad van de polynoom  positief.

Hiervoor wordt polynoomrekening gebruikt en er wordt modulo  gerekend met de coëfficiënten (het zijn elementen van de quotiëntring ).

Algoritme