2 Erzeugung gleichverteilter Zufallszahlen

Die Erzeugung von gleichverteilter Zufallszahlen kann man sich als iterative Folge von Transformationen $f(x)$ , mit Ausnahme der Identität, aus den Zufallszahlen $x$ vorstellen, wobei die aus der Transformation der (gleichverteilten) Zufallszahlen – und folglich auch die nach $n$ -facher Anwendung derselben Transformation $f^{n}(x)$ – erzeugten Zufallszahlen die ursprüngliche (Gleichverteilung-) Verteilung besitzen. Des weiteren muss die Transformation $f(x)$ umkehrbar sein. Zumeist werden die Transformationen auf einer Teilmenge der ganzen Zahlen entsprechend der Länge der Computerregister unter Anwendung der hierauf möglichen arithmetischen Operationen durchgeführt. Aufgrund der beschränkten Registerlänge $L$ wird nach einer bestimmten Anzahl an Transformationen, spätestens nach $N=2^{L}$ Schritten, der Anfangswert wieder erreicht. Um möglichst viele Zufallszahlen zu erzeugen, sollte diese Periodenlänge $N$ möglichst groß sein. Auch ist es wichtig, dass im Verlaufe der Iterationen möglichst alle Zahlen mit gleicher Häufigkeit angenommen werden und Lücken vermieden werden, so dass eine Gleichverteilung erreicht wird.

Vor der ersten Anwendung müssen die Startwerte der Zufallsgeneratoren initialisiert werden, wobei manche Generatoren Zugriffe auf mehrere zuvor bestimmte Werte verwenden. Die Wahl geeigneter Startwerte aus einer Startmenge $\mathcal{Z}$ kann ausschlaggebend für die Güte der erzeugten Zufallszahlen sein. Für ideale Generatoren sollte die Zahl der zulässigen Startwerte so groß sein wie die Periodenlänge.

Für die praktische Anwendung ist wichtig, dass die künstlich erzeugten, gleichverteilten Zufallszahlen den statistischen Kriterien „echter“ Zufallszahlen weitestgehend. So etwa Im Vergleich untereinander sollten sie, auch wenn man verschiedene Generatoren verwendet, für die Erwartungswerte dieselben Ergebnisse liefern. Statistische Prüfverfahren wie der $\chi^{2}$ -Test, Spektraltests und die strengen Tests von Marsaglia [8] in der Sammlung „Diehard Battery of Tests of Randomness“ („Diehard“-Tests) geben detaillierten Aufschluss über die Güte der Zufallszahlen. Für die Wahl des Generators ist nicht nur die statistische Güte ausschlaggebend, sondern auch seine Geschwindigkeit, so dass der Anwendungsfall entscheidet, welcher unter welchen Kompromissen eingesetzt wird. In den letzten Jahren ist das Thema Erzeugung von Zufallszahlen insbesondere durch die Entwicklung von Verschlüsselungsalgorithmen für kryptographischer Verfahren rasch vorangekommen und ist zunehmend hardwareorientiert. Die meisten Programmiersprachen besitzen Standardfunktion zur Erzeugung von Zufallszahlen Jedoch sind diese nicht standardisiert, kaum dokumentiert und genügen oft nicht den Erfordernissen, weshalb man diese auch nicht verwenden sollte. Viele der älteren Generatoren bestehen nicht mehr den heutigen Ansprüchen und modernen Testverfahren.

Hierzu gehört auch der früher häufig eingesetzte Zufallsgeneratoren nach der lineare Kongruenz- bzw. die Modulo- oder Reste-Methode (engl. linear congruential generator, Abk. LCG) zur Erzeugung gleichverteilter Zufallszahlen mit Ganzzahlarithmetik, welcher nach der iterativen Vorschrift (Iterationsschritte $n$ ) $$\begin{equation} x_{n}=a\cdot x_{n-1}+b\,\left(\mathrm{mod}\,m\right)\label{eq:URE:Zufallszahlen:LCG} \end{equation}$$ arbeitet. Ein Spezialfall hiervon ist der multiplikative Linear-Kongruenz-Generator (MLCG) mit $b=0$ , d. h. $$\begin{equation} x_{n}=a\cdot x_{n-1}\,\left(\mathrm{mod}\,m\right),\label{eq:URE:Zufallszahlen:MLCG} \end{equation}$$ und eine Verallgemeinerung von diesem mit der Rekursionstiefe $r$ ist $$x_{n}=\sum_{i=1}^{r}a_{i}x_{r-i}\,\left(\mathrm{mod}\,m\right).$$ Hierbei liefert die Modulo-Operation $\mathrm{mod}$ den Rest nach der Division durch $m$ . Die Zahlen wiederholen sich beginnend mit einem Startwert $x_{0}$ spätestens nach $m$ Iterationen. Benötigt man viele Zufallszahlen muss die Periodenlänge für das Wiederholen der Zahlenwerte und damit $m$ hinreichend groß. Zusätzlich werden an die Konstanten $a$ und $b$ weitere Forderungen gestellt (z. B. müssen $a$ und $b$ teilerfremd sein), um zum einen möglichst großen Wiederholungszyklus zu erhalten und, um die geforderte Güte der Zufallszahlen zu erfüllen. So sollten nach [7] $b$ und $m$ keinen gemeinsamen Teiler besitzen, $a\equiv1\,\mathrm{mod}\,p$ für jeden Primfaktor $p$ von $m$ und $a\equiv1\,\mathrm{mod}\,4$ , falls $m$ ein Vielfaches von 4 ist. Den Startwert $x_{0}$ kann man bei der Initialisierung vorgeben oder man verwendet den vom System initialisierten Standardwert. Da alle Werte in (\ref{eq:URE:Zufallszahlen:LCG}↓) im Idealfall irgendwann im Verlaufe der Iteration angenommen werden, sind alle Startwerte gleich berechtigt.

Besonders einfach lassen sich Zufallsgeneratoren in Binärarithmetik realisieren, wenn $m$ eine Zweierpotenz $m=2^{k}$ ist. In diesem Falle kann man die Modulo-Operation durch eine binäre AND-Operation mit der Bitmaske $2^{k}-1$ ersetzen. Ein solcher ist der Generator mit den Konstanten $(a,b,m)=(513,297410973,2^{47})$ [3], bei dem vorteilhafterweise die Multiplikation von $x_{n}$ mit 513 durch eine Linksverschiebung von $x_{n}$ um 9 Binärstellen und anschließender Addition von $x_{n}$ realisiert werden kann. Jedoch haben Zufallsgeneratoren mit Zweierpotenzen für $m$ eine Schwachstelle; ihre niederwertigen Bits sind weniger zufällig. Dennoch werden in [13] für 64-Bit-Ganzzahlen mit $m=2^{64}$ aufgrund ihrer guten spektralen Eigenschaften und trotz nicht so guter statistischer Eigenschaften die in der Tabelle 1↓ angegebenen Werte empfohlen. Hiervon sind aber nur die 32 höherwertigen Bits für die Verwendung als Zufallszahl zugelassen. Bessere Ergebnisse erhält man, wenn $m$ als Primzahl gewählt wird. Dann benötigt man zur schnellen Ausführung der Multiplikation Register mit doppelten Breite. Derartige Parameter erfüllen auch die „Diehard“-Tests. In [13] werden die in der Tabelle 2↓ von P. L´ Ecuyer berechneten Parameter eines MLCG angegeben. Als Startwert kann jede 64-Bit-Ganzzahl $1\leq x_{0}\leq m-1$ genommen werden. Für die Nutzung als Zufallszahlen dienen die 32 niederwertigen Bits. In manchen Fällen sind auch noch mehr Bits brauchbar.

Generator-Bezeichnung	$m$	$a$
E1	$2^{39}-7=549755813881$	10014146
E2		30508823
E3		25708129
E4	$2^{41}-21=2199023255531$	5183781
E5		1070739
E6		6639568
E7	$2^{42}-11=4398046511093$	1781978
E8		2114307
E9		1542852
E10	$2^{43}-57=8796093022151$	2096259
E11		2052163
E12		2006881

Tabelle2 Parameter für den LCG mit Primzahlen $m$ nach [13], S. 349

Lineare rückgekoppelte Schieberegister (engl. linear feedback shift register, Abk. LFSR) [4] können ebenfalls zur Erzeugung von Zufallszahlen genutzt werden. Sie finden außerdem eine breite Anwendung in elektronischen Schaltungen, z. B. als Rauschgeneratoren, lassen sich aber auch leicht durch übliche Bitoperationen auf herkömmlichen Rechnern realisieren. Ein Schieberegister der Länge $N$ ist ein Bitspeicher $\mathrm{B}=(b_{1},\ldots,b_{N})$ bestehend aus $N$ Einzelbitspeichern (Flip-Flops), an dessen Ausgang die Bitzustände $b_{i}$ mit $i=1,\ldots,N$ sequentiell ausgelesen und an dessen Eingang die Werte bitweise eingelesen werden können, wobei die Bitzustände (taktweise mit $n$ ) vom Eingang $b_{1}$ zum Ausgang $b_{N}$ durchgeschoben werden. Über eine Rückkopplung werden der Ausgang und einzelne Elemente des Schieberegisters linear Modulo 2 verknüpft (über eine Exklusiv-Oder-Operation) dem Eingang zugeführt, wobei die Auswahl der Elemente über die Koeffizienten $c_{j}\in[0,1]$ erfolgt. Die iterative Vorschrift lässt sich zusammenfassend durch $$\begin{eqnarray} b_{1}^{(n+1)} & = & b_{N}^{(n)}+\sum_{i=1}^{N-1}c_{i}b_{i}^{(n)}\label{eq:URE:Zufallszahlen:LFSR}\\ b_{j}^{(n+1)} & = & b_{j-1}^{(n)},\;j=2,\ldots,N\nonumber \end{eqnarray}$$ bzw. mittels der Matrix $$\mathbf{C}=\left(\begin{array}{ccccc} c_{1} & c_{2} & \cdots & c_{N-1} & 1\\ 1 & 0 & \cdots & 0 & 0\\ \vdots & \vdots & \ddots & \vdots & \vdots\\ 0 & 0 & \cdots & 0 & 0\\ 0 & 0 & \cdots & 1 & 0 \end{array}\right)$$ als lineare Transformation $$\mathbf{B}^{(n+1)}=\mathbf{C}\,\mathbf{B}^{(n)}\,(\mathrm{mod}\,2)$$ darstellen. Die maximalen Periodenlänge beträgt $2^{N}-1$ und es ist leicht einzusehen, dass als Initialisierung nicht alle Bitzustände $b_{i}$ den Wert 0 besitzen dürfen. Bei ungeeigneter Wahl der Koeffizienten können jedoch kürzere Teilzyklen entstehen, die den Einsatz als Zufallsgenerator unbrauchbar machen. Der Abbildungsvorschrift (\ref{eq:URE:Zufallszahlen:LFSR}↓) lässt sich das charakterisierende Polynom $$P(x)=x^{N}+c_{N-1}x^{N-1}+\cdots+c_{1}x+1$$ zuordnen, wobei die Indizes der von Null verschiedenen Koeffizienten dieses Polynom eindeutig beschreiben. Kann ein solches Polynom wieder in Polynome faktorisieren werden, d. h. ist es reduzibel, dann treten Teilzyklen auf. Die Forderung besteht demnach darin, irreduzible Darstellungen zu finden. Dies ist aber sehr aufwendig und für bestimmte Längen $N$ gibt es oft mehrere Lösungen. Die Irreduzibilität ist jedoch keine Garantie für einen guten Zufallsgenerator, sondern nur eine Notwendigkeit.

Andere Zufallsgeneratoren arbeiten wie der zeitlich-verzögerte Fibonacci [B]  [B] genannt nach Leonardo da Pisa, Sohn des Guglielmo Bonacci („figlio di Bonaccio“)-Generator (engl.: lagged Fibonacci generator, Abk. LFG), kurz Fibonacci-Generator, mit Tabellen auf die mit einem gewissen Indexversatz zugegriffen wird, wobei die enthaltenen Werte mit binären Operationen $\bullet$ (Addition, Subtraktion, Multiplikation, bitweises Exklusiv-Oder) nach der Vorschrift $$\begin{equation} x_{n}=x_{n-r}\bullet x_{n-s}\,(\mathrm{mod\,}m),\;0<r<s\label{eq:URE:Zufallszahlen:Fibonacci} \end{equation}$$ verknüpft werden. Diese erfolgt in Analogie zur Erzeugung der Fibonacci-Zahlenfolge ($r=1$ , $s=2$ , Operation; „$+$ “ ohne Modulo-Operator) nach der Rekursionsvorschrift $x_{n}=x_{n-1}+x_{n-2}$ für $n\geq2$ und den Startwerten $x_{0}=0$ und $x_{1}=1$ als Modell für die Populationsentwicklung. Aufgrund der einfachen Vorschrift für die Verknüpfung der Operanden sind Fibonacci-Generatoren sehr schnell. Mindestens einer der Verzögerungen $r$ oder $s$ sollte ungerade sein. Eine mögliche Wahl ist $r=24$ und $s=55$ , womit die Tabelle entsprechend des größten Verzögerung eine Länge von 55 besitzen muss. Die Wertetabelle muss vor der ersten Anwendung des Generators mit geeigneten Werten initialisiert werden. Beispielsweise kann man hierzu den Generator Ranq1 (s. u.) verwenden. Nachteilig ist, dass die Qualität der Zufallsfolgen stark von dieser Initialisierung abhängen kann. Von Vorteil ist, dass man mit dem Fibonacci-Generator sehr schnell gleichverteilte Zufallszahlen direkt im doppelt genauen Gleitkommaformat mit 52-Bit-Mantisse unter Nutzung des IEEE 754-Standards erzeugen kann, d. h. ohne den üblichen Weg der Umwandlung einer Ganzzahl in das Gleitkommaformat, wenn als binäre Operation $$\begin{equation} a\bullet b=\begin{cases} a-b, & a\geq b\\ a-b+1, & a<b \end{cases}\label{eq:URE:Zufallszahlen:Fibonacci:Double} \end{equation}$$ verwendet wird. Fibonacci-Generatoren lassen sich auch in parallelen Rechnersystemen anwenden [15].

Wenn man zudem einem Übertrag $c$ in der Addition berücksichtigt, so spricht man von Addition-mit-Übertrag-Generatoren (engl. add-with-carry generator, Abk. AWC). Man kann die entsprechende Iteration $x_{n}=x_{n-r}+x_{n-s}+c\,(\mathrm{mod\,}m)$ als Abbildung der Funktion $f(x_{1},x_{2},\ldots,x_{r},c)$ durch $$\begin{eqnarray} f(x_{1},x_{2},\ldots,x_{r},c) & = & \begin{cases} (x_{2},x_{3},\ldots,x_{r},x_{r+1-s}+x_{1}+c,0), & x_{r+1-s}+x_{1}+c<m\\ (x_{2},x_{3},\ldots,x_{r},x_{r+1-s}+x_{1}+c-m,1), & x_{r+1-s}+x_{1}+c\geq m \end{cases}\label{eq:URE:Zufallszahlen:AWC1} \end{eqnarray}$$ oder für die komplementären Form $x_{n}=1-b-(x_{n-r}+x_{n-s}+c)\,(\mathrm{mod\,}m)$ als Abbildung $$\begin{equation} f(x_{1},x_{2},\ldots,x_{r},c)=\begin{cases} (x_{2},x_{3},\ldots,x_{r},m-1-(x_{r+1-s}+x_{1}+c),0), & x_{r+1-s}+x_{1}+c<m\\ (x_{2},x_{3},\ldots,x_{r},2m-1-(x_{r+1-s}+x_{1}+c),1), & x_{r+1-s}+x_{1}+c\geq m \end{cases}\label{eq:URE:Zufallszahlen:AWC2} \end{equation}$$ darstellen. Die erste Variante besitzt mit der Primzahl $p=m^{r}+m^{s}-1$ und die zweite mit der Primzahl $p=m^{r}+m^{s}+1$ die Periodenlänge $p-1$ . Beide Periodenlängen sind wesentlich größer als beim klassischen Fibonacci-Generator. (Für z. B. $m=2^{32}$ wäre die Periodenlänge hierfür nur ungefähr $2^{32+s}$ , im Gegensatz zum Addition-mit-Übertrag-Generator mit einer Periodenlänge von mindestens $2^{32\cdot s}$ ). Entsprechend kann man auch Subtraktion-mit-Borgen-Generatoren (engl. subtract-with-borrow generator, Abk. SWB) für Iterationen der Form $x_{n}=x_{n-s}-x_{n-r}-c$ durch die Abbildung $$\begin{equation} f(x_{1},x_{2},\ldots,x_{r},c)=\begin{cases} (x_{2},x_{3},\ldots,x_{r},x_{r+1-s}-x_{1}-c,0), & x_{r+1-s}-x_{1}-c\geq0\\ (x_{2},x_{3},\ldots,x_{r},x_{r+1-s}-x_{1}-c+m,1), & x_{r+1-s}+x_{1}+c<0 \end{cases}\label{eq:URE:Zufallszahlen:SWB1} \end{equation}$$ bzw. für Iteration der Form $x_{n}=x_{n-r}-x_{n-s}-c$ durch die Abbildung $$\begin{equation} f(x_{1},x_{2},\ldots,x_{r},c)=\begin{cases} (x_{2},x_{3},\ldots,x_{r},x_{1}-x_{r+1-s}-c,0), & x_{1}-x_{r+1-s}-c\geq0\\ (x_{2},x_{3},\ldots,x_{r},x_{1}-x_{r+1-s}-c+m,1), & x_{1}-x_{r+1-s}-c<0 \end{cases}\label{eq:URE:Zufallszahlen:SWB2} \end{equation}$$ einführen. Die erste Variante besitzt mit der Primzahl $p=m^{r}-m^{s}+1$ und die zweite mit der Primzahl $p=m^{r}-m^{s}-1$ die Periodenlänge $p-1$ . Die Verzögerungen $r$ und $s$ sollten so gewählt werden, dass je nach Variante $p=m^{r}\pm m^{s}\pm1$ eine Primzahl mit der Primitivwurzel $m$ ist. Die Suche nach geeigneten Parametern ($m$ , $r$ , $s$ ) ist sehr zeitaufwendig [7].

Ein weiterer Generator mit großer Periodenlänge und guten statistischen Eigenschaften stammt von Marsaglia [9] und benutzt die Multiplikation mit Übertrag (engl.: Multiply with Carry, Abk. MWC) modulo einer Zahl $b$ , welche als Zweierpotenz $b=2^{w}$ entsprechend der Registerbreite $w$ der Prozessoren gewählt wird.

Die Iteration der Zufallszahlen $x_{n}$ mit um $r$ , $n\ge r$ , verzögerten Werten $x_{n-r}$ erfolgt durch Multiplikation mit $a$ und der Addition des Übertrages $c_{n-1}$ – beim Zufallsgenerator nach dem Kongruenzverfahren war dieser Term eine Konstante – nach der Vorschrift $$\begin{equation} x_{n}=ax_{n-r}+c_{n-1}\,\left(\mathrm{mod\,}b\right),\ \label{eq:URE:Zufallszahlen:MWC1} \end{equation}$$ wobei der neue Übertrag $y_{n}$ durch den ganzzahligen Anteil nach der Division durch $b$ gemäß $$\begin{equation} c_{n}=\left\lfloor \frac{ax_{n-r}+c_{n-1}}{b}\right\rfloor \ \label{eq:URE:Zufallszahlen:MWC2} \end{equation}$$ bestimmt wird. Die Wahl von $a$ , $b$ und $r$ erfolgt nach dem Kriterium, dass $p=ab^{r}-1$ eine Primzahl ist. Im allgemeinen Fall werden sowohl Startwerte für den Übertrag $0\leq c_{0}<a$ und für die Reste $0\leq x_{i}<b,\,0\leq i<r$ aus einer Startmenge $\mathcal{Z}=\left\{ \left[c_{0};x_{0},x_{1},\ldots,x_{r-1}\right]\right\}$ von $(r+1)$ -Tupeln benötigt, wobei $\left[0;0,0,\ldots,0\right]$ und $\left[a-1;b-1,b-1,\ldots,b-1\right]$ verboten sind. Die Transformation ist somit durch $$\begin{equation} f\left[y_{0};x_{0},x_{1},\ldots,x_{r-1}\right]=\left[\left\lfloor \frac{ax_{0}+c_{0}}{b}\right\rfloor ;x_{1},x_{2},\ldots,x_{r-1},ax_{0}+c_{0}\,\left(\mathrm{mod}\,b\right)\right]\label{eq:URE:Zufallszahlen:MWC} \end{equation}$$ gegeben.

Falls $b$ sich als Zweierpotenz darstellt, dann kann die Division durch eine Rechtsverschiebeoperation oder bei Verwendung von Doppelregistern durch Kopieren des höherwertigen Wortes in das niederwertige Wort ersetzt werden. Insbesondere für 64-Bit-Ganzzahlen $x_{n}$ kann dies nach $$\begin{equation} x_{n+1}=a\cdot(x_{n}\,\&\,(2^{32}-1))+(x_{n}\mathtt{>>}32)\label{eq:URE:Zufallszahlen:MWC:64Bit} \end{equation}$$ erfolgen, wobei die bitweisen Operationen UND (Symbol: „$\&$ “) zur Maskierung der niederwertigen Bits und die Rechtsverschiebung (Symbol „$\mathtt{\mathtt{>>}}$ “) um 32 Stellen zur Erzeugung des Übertrages Anwendung finden. Es sind jedoch nur die niederwertigen 32 Bit zur Erzeugung der Zufallszahlen nutzbar. Die erlaubten Startwerte $x_{0}$ liegen im Bereich $1\leq x_{0}\leq2^{32}-1$ . In [13] werden die in Tabelle 3↓ enthaltenen Werte empfohlen, die auch die „Diehard“-Tests bestehen. Das Beispiel von [9] unter Verwendung von Tabellenzugriffen, besteht in der Wahl $a=611373678$ , $b=2^{32}$ , $r=1038$ . Zufallszahlenfolgen, welche mit $b=2^{32}$ gebildet werden, besitzen aber nicht die Periode $p-1$ sondern, falls für $p=2q+1$ und $q$ auch ein Primzahl ist, die Periode $\frac{p-1}{2}.$

Dieser Makel lässt sich mit dem komplementären Multiplikation-mit-Übertrag-Verfahren (engl. Complimentary Multiply With Carry, Abk. CMWC) speziell für $b=2^{32}-1$ vermeiden, wonach die Zufallszahlen nach der Vorschrift $$\begin{equation} x_{n}=\left(b-1\right)-\left[ax_{n-r}+c_{n-1}\,\left(\mathrm{mod}\,b\right)\right]\label{eq:URE:Zufallszahlen:CMWC1} \end{equation}$$ und der Übertrag gemäß $$\begin{equation} c_{n}=\left(ax_{n-r}+c_{n-1}\right)\mathtt{>>}32\label{eq:URE:Zufallszahlen:CMWC2} \end{equation}$$ gebildet werden. Hierfür verwendet man als Kriterium, dass $p=ab^{r}+1$ eine Primzahl ist. Die Periode der Zufallszahlensequenz beträgt $p-1=ab^{r}$ .

Weitere sehr schnelle und leicht zu implementierende Methoden zur Erzeugung von Zufallszahlen beinhalten Kombinationen aus den Standard-Computerarithmetik-Operationen XOR (Exklusiv-Oder: Symbol „$\wedge$ “ bzw. die Modulo-2-Addition) und bitweiser Verschiebung (SHIFT) nach links bzw. rechts (Linksverschiebung: Symbol „$\mathtt{<<}$ “, Rechtsverschiebung: Symbol „$\mathtt{>>}$ “) um eine gewisse Anzahl von Positionen, so die XOR-SHIFT-Zufallsgeneratoren von Marsaglia [9] (engl. „xorshift RNG“, Abk. XSRNG) in 32-Bit-Abstufung mit einer Periode $p=2^{N}-1$ für $N=32,\,64,\,96,\,128,\,160,\,192$ usw., welche die XOR-Operation auf eine entsprechende Ganzzahl und deren bitverschobene Kopie anwenden. Hierzu gehört insbesondere die 64-Bit-Xorshift-Methode mit den Befehlssequenzen $$\begin{eqnarray} x_{n+1} & = & x_{n}\wedge(x_{n}\mathtt{<<}a)\nonumber \\ x_{n+2} & = & x_{n+1}\wedge(x_{n+1}\mathtt{>>}b)\label{eq:URE:Zufallszahlen:Marsaglia:left}\\ x_{n+3} & = & x_{n+2}\wedge(x_{n+2}\mathtt{<<}c)\nonumber \end{eqnarray}$$ bzw. $$\begin{eqnarray} x_{n+1} & = & x_{n}\wedge(x_{n}\mathtt{>>}a)\nonumber \\ x_{n+2} & = & x_{n+1}\wedge(x_{n+1}\mathtt{<<}b)\label{eq:URE:Zufallszahlen:Marsaglia:right}\\ x_{n+3} & = & x_{n+2}\wedge(x_{n+2}\mathtt{>>}c)\nonumber \end{eqnarray}$$ für die 64-Bit-Ganzzahlen $x_{n}$ und Iterationsschritten $n\geq0$ sowie Startwerten $x_{0}\neq0$ . Diese Operationen lassen sich in den 64-Bit-Registern moderner Prozessoren sehr schnell ausführen. Die Sequenzen von XOR-SHIFT-Operationen sind Spezialfälle, die aus der Zerlegung einer allgemeinerem binären $N\times N$ -Transformationsmatrix $\mathbf{Q}$ in nichtsinguläre Matrizen ($\mathbf{I}+\mathbf{L}^{a}$ ) bzw. ($\mathbf{I}+\mathbf{R}^{b}$ ) mit $\mathbf{Q}=(\mathbf{I}+\mathbf{L}^{a})(\mathbf{I}+\mathbf{R}^{b})(\mathbf{I}+\mathbf{L}^{c})$ entstehen, wobei $\mathbf{I}$ die Einheitsmatrix, $\mathbf{L}=\left(\begin{array}{cccc} 0 & 0 & \cdots & 0\\ 1 & 0 & \cdots & 0\\ \vdots & \ddots & \ddots & \vdots\\ 0 & \cdots & 1 & 0 \end{array}\right)$ bzw. $\mathbf{R}=\mathbf{L}^{T}$ die Matrixdarstellungen des Links- bzw. Rechtsverschiebungsoperators sind. Die Periode $p$ ist durch $\mathbf{Q}^{p}=\mathbf{I}$ gegeben. Für das Tripel $(a,b,c)$ der Positionsverschiebungen müssen geeignete positive ganzzahlige Werte gewählt werden. Nach [13] sind die Tripel in der Top-Liste (4↓), gekennzeichnet durch die Generator-Bezeichnung, für beide Varianten (\ref{eq:URE:Zufallszahlen:Marsaglia:right}↓) und (\ref{eq:URE:Zufallszahlen:Marsaglia:left}↓) gute Kandidaten. Sie wurden aus einer viel größeren Möglichkeitsmenge ausgewählt und bestehen die „Diehard“-Tests.

Generator-Bezeichnung	$a$	$b$	$c$
A1	21	35	4
A2	20	41	5
A3	17	31	8
A4	11	29	14
A5	14	29	11
A6	30	35	13
A7	21	37	4
A8	21	43	4
A9	23	41	18

Tabelle4 Mögliche Tripel nach [13], S. 347, für die 64-Bit-Xorshift-Methode von Marsaglia

Die XOR-SHIFT-Methode nach Marsaglia ist mit gewissen Typen linear rückgekoppelter Schieberegister verwandt.

Die Erzeugungsmechanismen lassen sich koppeln und man erhält in günstigen Fällen weitere Verbesserungen, wenn man die Bits mit den besten Eigenschaften aus mehreren Generatoren in einer neuen Kombination verwendet, wofür in [13] einige Rezepte angegeben werden. So wird als eine mögliche Kombination die Hintereinanderausführung der Generatoren C1 und A6 erwähnt, die einen neuen Generator $\mathrm{C1}(\mathrm{A6})$ ergeben. Besonders empfohlen wird in [13] der Generator mit der Bezeichnung Ran, welcher nach der Kompositionsregel $$\begin{equation} \mathrm{Ran}=\left[\mathrm{A1}_{l}(\mathrm{C3})+\mathrm{A3}_{r}\right]\wedge\mathrm{B1}\label{eq:URE:Zufallszahlen:Press:Ran} \end{equation}$$ aus den 4 Generatoren mit den Bezeichnungen A1, C3, A3, B1 gebildet wird. Die Indizes $l$ und $r$ an den Generatoren nach dem Marsaglia-Verfahren A1 bzw. A3 kennzeichnen, ob als erste Schiebeoperation eine Links- oder eine Rechtsverschiebung erfolgt. Intern werden die Zustände der unabhängigen Generatoren C3, A3, B1 nach jedem Schritt aktualisiert. Als einfache und schnelle Varianten werden die Generatoren mit dem Namen Ranq1 $$\begin{equation} \mathrm{Ranq1}=\mathrm{D1}(\mathrm{A1})\label{eq:URE:Zufallszahlen:Press:Ranq1} \end{equation}$$ und Ranq2 $$\begin{equation} \mathrm{Ranq2}=\mathrm{A3}_{r}\wedge\mathrm{B1}\label{eq:URE:Zufallszahlen:Press:Ranq2} \end{equation}$$ empfohlen.

Der von Matsumoto und Nishimura entwickelte Mersenne-Twister (MT) ist ein schneller und hoch-qualitativer Generator zur Erzeugung von Zufallszahlen und hat eine matrixbasierte lineare Rekurrenz über dem binären Feld $\mathbb{F}_{2}$ zur Grundlage. Seine Periodenlänge wird durch die namensgebende Mersenne-Primzahl festgelegt. Verbreitetet sind die 32-Bit-Version MT19937 und die 64-Bit Version MT19937-64 mit einer Periode von $2^{19937}-1$ . Er besitzt auch in höheren Dimensionen gute Gleichverteilungseigenschaften und gute Unkorreliertheit verschobener Sequenzen und besteht die „Diehard“-Tests. Wegen der Prognostizierbarkeit der Sequenz ist er eher für Monte-Carlo-Simulationen geeignet, als für kryptographische Zwecke. Der SIMD [C]  [C] SIMD: Single Instruction Multiple Data-orientierte Mersenne-Twister (SFMT) ist eine Weiterentwicklung und speziell für 128-Bit-SIMD-Operationen konzipiert und nutzt die Möglichkeiten moderner CPUs . Für diese Architekturen ist er schneller als der ursprüngliche Mersenne-Twister.

Sowohl für die bitorientierte Implementierung in spezieller Hardware wie den FPGA (Abk. für Field-Programmable Gate Array) [19] oder in (massiv) parallelen Computerarchitekturen allgemein, als auch zur Implementierung als Software existieren Entwicklungen von Zufallsgeneratoren auf der Basis zellulärer Automaten (s. u.). Die Zellen, die man sich als Register zum Speichern von Zustandswerten vorstellen kann, sind in einer bestimmten Geometrie angeordnet, z. B. als lineare Kette oder in einem quadratischen Gitter. Die Gesamtheit der Zellen des zellulären Automaten bilden somit ein riesiges Zustandsfeld bzw. Register, wobei FPGA architektonisch im Wesentlichen einer solchen zweidimensionalen Anordnung entsprechen. Zufallsgeneratoren als zelluläre Automaten besitzen, wenn auch nur in Spezialfällen, eine gewisse Verwandtschaft mit den Zufallsgeneratoren basierend auf linearen rückgekoppelten Schieberegistern. Sie sind diesen aber in der Qualität überlegen. Die Zustandsüberführung einer Zelle $i$ erfolgt nach vorgegebenen Regeln in Abhängigkeit des Zustandes dieser Zelle und der Zustände in einer Nachbarschaft für alle Zellen zeitlich synchron, d. h. parallel, und kann über Look-Up-Tabellen erfolgen. Eine solche Regel $f$ für $k$ -wertige Zustände $a_{i}^{(n)}\in\left\{ 0,1,\ldots,k-1\right\}$ und einem Nachbarschaftsradius $r$ kann beispielsweise durch die iterative Abbildung $$\begin{equation} a_{i}^{(n+1)}=f(a_{i-r}^{(n)},a_{i-r+1}^{(n)},\ldots,a_{i}^{(n)},\ldots,a_{i+r-1}^{(n)},a_{i+r}^{(n)})\label{eq:URE:Zufallszahlen:ZA:Wolfram1} \end{equation}$$ für die aufeinanderfolgenden Zeitpunkte $n$ und $n+1$ beschrieben werden. Wegen der zumeist lokalen Nachbarschaft kann die Zustandsaktualisierung und damit die Erzeugung der Zustandszahlen sehr schnell erfolgen.

Entsprechend der Klassifikation nach Wolfram kann die Evolution einer bestimmten Startkonfiguration bzw. eines Musters in eine fixierte Konfiguration (1) münden, es können einfache periodische Strukturen (2) erscheinen, aber auch aperiodische (z. B. selbstähnliche bzw. fraktale) und als chaotische erscheinende Strukturen (3) können auftreten. Außerdem sind komplizierte, lokalisierte Strukturen (4) möglich. Für potenzielle Zufallsgeneratoren ist nur der 3. Fall mit zumeist nichtlinearen Regeln von Bedeutung und die hiermit aufgrund der Kompliziertheit verbundene praktische Unvorhersagbarkeit ist wesentlich für die Eignung.

Ein solcher einfacher, eindimensionaler zellulärer Zufallsautomat nach Wolfram [16] bestehend aus $N$ Zellen mit Zuständen $a_{i}^{(n)}$ aus der Zustandsmenge der Binärzahlen 0 oder 1, d. h. $a_{i}^{(n)}\in\left\{ 0,1\right\}$ für $1\leq i\leq N$ , besitzt die Regel („Regel 30“) $$\begin{equation} a_{i}^{(n+1)}=a_{i-1}^{(n)}\,\mathrm{XOR}\,(a_{i}^{(n)}\,\mathrm{OR}\,a_{i+1}^{(n)})\label{eq:URE:Zufallszahlen:ZA:Wolfram2} \end{equation}$$ für die Zustandsüberführung, wobei der neue Zustand zum Zeitpunkt $n+1$ in der Zelle $i$ in Abhängigkeit der Zustände der nächsten Nachbarn $i-1$ und $i+1$ mit Hilfe der logischen Operationen $\mathrm{XOR}$ (Exklusives Oder) und $\mathrm{OR}$ (Oder) gebildet wird. Diese Regel (\ref{eq:URE:Zufallszahlen:ZA:Wolfram2}↓) ist äquivalent mit der nichtlinearen numerischen Vorschrift $$\begin{equation} a_{i}^{(n+1)}=a_{i-1}^{(n)}+a_{i}^{(n)}+a_{i+1}^{(n)}+a_{i}^{(n)}a_{i+1}^{(n)}\,(\mathrm{mod}2)\label{eq:URE:Zufallszahlen:ZA:Wolfram3} \end{equation}$$ in Modulo-2-Arithmetik. Der Zahlencode 30 für die „Regel 30“ berechnet sich als Dezimalwert aus den Wahrheitswerten für alle Kombinationen der Eingangswerte: Es werden periodische Randbedingungen angenommen, so dass man sich den zellulären Zufallsautomaten auch als zirkuläres Register, z. B. bestehend aus einem oder mehreren Computerregistern, vorstellen kann. Die Anfangskonfiguration mit dem Zustandswert 0 in allen Zellen muss wegen der trivialen Periodenlänge 1 ausgeschlossen werden. In einem solchen Zufallsgenerator treten die möglichen Bitsequenzen mit gleicher Wahrscheinlichkeit auf. Von Wolfram wurde zwischen der maximalen Periodenlänge $\pi_{N}$ in Abhängigkeit von der Zellenzahl $N$ die näherungsweise, empirische Beziehung $$\begin{equation} \pi_{N}\cong2^{0,61\,(N+1)}\label{eq:URE:Zufallszahlen:ZA:Wolfram4} \end{equation}$$ für periodische Randbedingungen gefunden und ist vergleichsweise klein gegenüber der Länge $2^{N}-1$ beim LFSR . Die Zufallssequenz lässt sich aus dem Zustand einer Zelle, etwa dem mit Index 0, nach jedem oder jeweils nach einer größeren Schrittzahl auslesen. Die Bildungsvorschrift (\ref{eq:URE:Zufallszahlen:ZA:Wolfram2}↓) ist ein einfaches Beispiel mit guten statistischen Eigenschaften. Noch allgemeiner können auch Abhängigkeiten von Zuständen weiter zurückliegender Zeitpunkte, etwa durch $$\begin{equation} a_{i}^{(n+1)}=f(a_{i-r}^{(n)},a_{i-r+1}^{(n)},\ldots,a_{i}^{(n)},\ldots,a_{i+r-1}^{(n)},a_{i+r}^{(n)})\,\mathrm{XOR}\,a_{i}^{(n-1)}\label{eq:URE:Zufallszahlen:ZA:Wolfram5} \end{equation}$$ berücksichtigt werden, wobei dann entsprechend der Standardform (\ref{eq:URE:Zufallszahlen:ZA:Wolfram1}↓) effektiv Transformationen mit größeren Zustandszahlen $k>2$ beschrieben werden. Jedoch ist es hierfür schwierig, geeignete Kandidaten für Zufallsgeneratoren zu finden.

Zelluläre Automaten basierte Zufallsgeneratoren wie die „Regel 30“ lassen sich auch in feingranulierten parallelen Computersystemen, insbesondere in zellulären Automaten einsetzen. Da jedoch zwischen benachbarten Zellen für eine kurze Zeit eine gewissen Korrelation der Zufallswerte existiert, muss man einen bestimmten Zeitabstand zwischen dem Auslesen der Zufallswerte verstreichen lassen oder man fügt Zellen zwischen diesen ein, so dass das Auslesen mit jedem Zeittakt erfolgen kann. Gibt man die Gleichartigkeit der Regeln für alle Zellen auf, so kann man durch Kombinationen von (auch linearen) Regeln gleich gute wie die „Regel 30“ oder bessere Zufallsgeneratoren konstruieren. Ein solche Kombination aus zwei Regeln sind die „Regel 90“ (Code 0) und die „Regel 150“ (Code 1) nach der Klassifikation von Wolfram, die ihrerseits keine guten Zufallsgeneratoren sind. Durch bestimmte Kombinationen (Sequenzfolgen der Regeln, z. B. $1101010$ mit der Gesamtlänge $N=7$ ) kann man maximale Zyklenlängen erreichen, die denen der LFSR gleichen und man kommt mit festen Randbedingungen aus Werten von 0 aus. Diese spezielle Regelkombination zeigt aber Probleme in der Gleichverteilung der Nullen und Einsen, wobei mal die Nullen überwiegen können und im darauf folgenden Schritt die Einsen, die man aber wieder durch Einfügen von Zellen überwinden kann. Zudem treten noch unerwünschte Symmetrien auf.[17, 18]