Die Auf- und Ab-Laufleistung von Tausworthe Pseudo-Zufallszahlengeneratoren

Jeder Tausworthe-Generator, der auf einem primitiven Trinomial über GF(2) basiert, xp + xq + 1, kann als eine einfache lineare Rekurrenz in GF(2P) dargestellt werden. Für einen Generator, der eine Folge von p-Bit Pseudo-Zufallszahlen erzeugt, wobei (p, 2p -1) = 1, was gemäß der Theorie von Tausworthe garantiert ist, dass es 1-verteilt ist, kann die Rekurrenz kombinatorische Beziehungen offenbaren, die auf eine schlechte Auf- und Ab-Laufleistung hindeuten. Dies tritt auf, wenn q klein ist, zu nahe an p/2 oder nahezu gleich p. Elementare, aber mühsame Kombinatorik ermöglicht es dann, die Häufigkeiten von auf- oder absteigenden Läufen einer bestimmten Länge quantitativ vorherzusagen. Empirische Studien bestätigen diese Vorhersagen eindrucksvoll.