Satz von Knuth

Der Satz von Knuth (nach Donald E. Knuth, 1981) besagt, dass ein linearer Kongruenzgenerator $y_{i+1}\equiv (ay_{i}+r)\,mod\,m$ (siehe dort) genau dann die volle Periodenlänge $m$ besitzt, wenn:

1. $ggT(m,r)=1$ (vgl. größter gemeinsamer Teiler)
2. $a\equiv 1\,mod\,p$ für alle Primteiler $p$ von $m$ (zur Erklärung der Symbolik siehe den Artikel Modulo)
3. $a\equiv 1\,mod\,4$, falls $4$ ein Teiler von $m$ ist

Hierbei verwendet man folgende Komponenten:

• Modul $m\in \mathbb {N}$,
• Inkrement $r\in \mathbb {N} _{0}$,
• Faktor $a\in \mathbb {Z}$,
• Startwert (Saat) $y_{0}\in \left\{0,...,m-1\right\}$.

Der Satz eignet sich also für das Testen linearer Kongruenzgeneratoren.