Pseudozufall

Pseudozufallszahlen finden u. a. Anwendung

• in der Computersimulation, bei der stochastische Prozesse mit Hilfe von Software simuliert werden (Monte-Carlo-Simulation)

• bei der Fehlersuche in Computerprogrammen

• bei der künstlichen Erzeugung von Rauschen (Pseudozufallsrauschen)

• in der Spreizspektrum-Technik

• im Bereich der Kryptographie

Unangebracht i​st das Nutzen v​on Pseudozufallszahlen i​n Bereichen, w​o echter Zufall vonnöten ist. Zur Erzeugung echter Zufallszahlen benötigt m​an entweder e​inen echten Zufallsgenerator (z. B. d​urch Digitalisieren v​on Rauschen o​der durch Ausnutzen v​on Quanteneffekten) o​der zumindest e​ine Quelle quasizufälliger (normalerweise n​icht vorhersagbarer) Ereignisse w​ie Zeiten v​on Benutzereingaben o​der Netzwerkaktivität.

Man nehme die Nachkommastellen einer Wurzel einer ganzen Zahl als Zufallszahlen. Hierbei ist selbstverständlich darauf zu achten, dass die resultierende Wurzel eine irrationale Zahl ist, das heißt, dass ${\displaystyle {\sqrt {n}}\notin \mathbb {Q} }$ gilt, was immer der Fall ist, wenn die Wurzel keine ganze Zahl ist. Klassischerweise kann man statt ${\displaystyle {\sqrt {n}}}$ auch die Kreiszahl Pi verwenden. Aufgrund der endlichen Speicherkapazität eines Computers kann es in der Praxis jedoch keinen nicht-periodischen deterministischen Zufallszahlengenerator geben. Möglich sind aber nicht-periodische deterministische Zufallszahlengeneratoren mit zwei Takt-Generatoren, deren Takte inkommensurabel sind; wenn also deren Frequenzverhältnis ${\displaystyle {\tfrac {f_{1}}{f_{2}}}}$ eine irrationale Zahl ist, also ${\displaystyle n_{1}\cdot f_{1}=n_{2}\cdot f_{2}}$ nicht erfüllt wird. Weil unter den reellen Zahlen die rationalen Zahlen eine Lebesgue-Nullmenge bilden, ist dies praktisch immer der Fall und damit ein aus beiden Takten generiertes Signal nichtperiodisch. Ein Beispiel hierfür ist ein mit der Frequenz ${\displaystyle f_{1}}$ erzeugtes Pseudozufallssignal, das mit der Frequenz ${\displaystyle f_{2}}$ abgetastet/eingelesen wird.

Primitive Polynome definieren e​ine wiederkehrende Relation, d​ie verwendet werden k​ann um Bits v​on Pseudozufallszahlen z​u erzeugen. Tatsächlich s​teht jedes linear rückgekoppelte Schieberegister m​it maximalem Zyklus (dieser i​st 2^{lrsr length} - 1) m​it primitiven Polynomen i​n Beziehung.

Sei z. B. ein primitives Polynom ${\displaystyle X^{10}+X^{3}+1}$ gegeben. Man beginnt mit einem benutzerdefinierten Startwert (englisch seed, Saatkorn, dieser muss nicht unbedingt zufällig gewählt werden). Man nimmt dann das 10-te, 3-te und 0-te Bit, gezählt vom niederwertigsten Bit, verknüpft diese mit XOR und erhält ein neues Bit. Die Saatzahl wird dann nach links verschoben und das neue Bit wird zum niederwertigsten Bit der Saatzahl. Dies kann wiederholt werden um ${\displaystyle 2^{10}-1=1023}$ Pseudo-Zufalls-Bits zu erzeugen. Für eine Maximum Length Sequence sind ganz bestimmte Ausgänge des Schieberegisters erforderlich.[1]

Allgemein gilt für ein primitives Polynom des Grades ${\displaystyle m}$, dass dieser Vorgang ${\displaystyle 2^{m}-1}$ Pseudo-Zufallszahlen erzeugt, bevor die Sequenz sich wiederholt.