Zufallszahlen | MathePrisma

Spektraltest

Dieser Test benutzt Hilfsmittel aus der Geometrie der Zahlen und wird auf Generatoren angewendet, denen eine Gitterstruktur zugrundeliegt. Es hat sich nämlich beim linearen Kongruenzgenerator sowie einigen anderen Generatoren herausgestellt, daß er in jeder Dimension eine intrinsische Regelmäßigkeit aufweist ([24], Chapter 7).

Voraussetzung

Sei der Einfachheit halber

$m=p$ eine Primzahl,
$\lambda$ eine Primitivwurzel modulo $p$ ,
$y_0\not\equiv 0 \,\bmod p$ und $r=0$ .

Dabei bedeutet die zweite Bedingung, daß die Potenzen $\lambda^n$ für $n\ge 0$ alle primen Restklassen modulo $p$ durchlaufen. Es gilt dann

$\begin{equation*} y_n\equiv \lambda^n y_0\,(p),\quad x_n=\frac{y_n}{p},\quad n\ge 0 , \end{equation*}$

und die Folge $(x_n)_{n\ge 0}$ hat die minimale Periode $p-1$ .

Gitterstruktur

Für jedes $s\ge 2$ existiert nun ein Gitter $\Lambda_s$ in $\mathbb{R}^s$ , sodaß

$\begin{equation*} \big\lbrace (x_n,x_{n+1},...,x_{n+s-1})\,|\, n\ge 0 \big\rbrace = (0,1)^s\cap\Lambda_s . \end{equation*}$

Die aus $s$ aufeinanderfolgenden Pseudozufallszahlen gebildeten $s$ -tupel bilden also ein Gitter im Einheitswürfel.