Pseudozufall

Als Pseudozufall wird bezeichnet, was zufällig erscheint, in Wirklichkeit jedoch berechenbar ist, d. h. durch einen bekannten Algorithmus mit bekannten Eingabedaten reproduziert werden kann. In diesem Sinn generieren Pseudozufallszahlengeneratoren pseudozufällige Zahlen. Mit bestimmten Eingabedaten gestartet, erzeugen diese immer wieder dieselbe Abfolge von Pseudozufallszahlen.

Pseudozufall in der Berechenbarkeitstheorie

In der Berechenbarkeitstheorie wird alles das als pseudozufällig bezeichnet, was aus der Perspektive des Betrachters nicht von wirklicher Zufälligkeit unterschieden werden kann. Das Ergebnis eines Münzwurfs wird beispielsweise generell als zufällig angesehen. Befindet sich die Münze bereits in der Luft, ist es theoretisch möglich, anhand ihrer Rotation, Geschwindigkeit usw. das Ergebnis vorherzusagen. Jemandem, dem entsprechende Messgeräte (und Rechenkapazität) nicht zur Verfügung stehen, erscheint der Wurf aber immer noch zufällig; der Wurf mit der Münze in der Luft ist für ihn pseudozufällig. Generell definiert man in der Berechenbarkeitstheorie als pseudozufällig, was durch effiziente Algorithmen nicht vorhergesagt werden kann. Pseudozufälligkeit ist aber immer noch berechenbar (man kann sie effizient erzeugen), nur nicht vorhersagbar. Pseudozufallsgeneratoren nach dieser Definition von Pseudozufälligkeit setzen die Existenz expliziter schwerer Funktionen voraus.

Pseudozufallszahlen

Pseudozufallszahlen werden von Pseudozufallszahlengeneratoren (englisch PRNG, pseudo random number generator) erzeugt, die in praktisch allen Programmiersprachen verfügbar sind. Sie erzeugen eine Zahlenfolge, die zwar zufällig aussieht, es aber nicht ist, da sie durch einen deterministischen Algorithmus berechnet wird. Bei jedem Start der Zufallszahlenberechnung mit gleichem Startwert, der sogenannten Saat (englisch seed), wird die gleiche Zahlenfolge erzeugt.

Sie erfüllen damit nicht die Eigenschaften echter Zufallszahlen, sind jedoch von Computern wesentlich einfacher zu erzeugen. Dabei ist die entstehende Zahlenfolge in der Regel periodisch, die Zahlen wiederholen sich also nach einer bestimmten Periodenlänge, die aber meist so groß ist, dass sie in einer Anwendung, die den PRNG nutzt, nicht vollständig durchlaufen wird (typisch ist für viele heutige PRNGs eine Periodenlänge von $2^{64}$). Der Vorteil von PRNGs im Vergleich zu echten Zufallsgeneratoren ist die einfache Implementierung und die hohe Geschwindigkeit.

Verwendung von Pseudozufallszahlen

Vor allem in Computerprogrammen wird aus Einfachheitsgründen ein Pseudozufallszahlengenerator verwendet, wenn man Zufallszahlen benötigt, die allerdings nicht zwingend echt zufällig sein müssen. Pseudozufallszahlen finden darüber hinaus u. a. Anwendung

• in der Computersimulation, bei der stochastische Prozesse mit Hilfe von Software simuliert werden (Monte-Carlo-Simulation),
• in Computerspielen, bei denen prozedural generierte Welten oder z. B. Spielkarten-Mischungen über einen einzigen Wert rekonstruiert werden können,
• bei der Fehlersuche in Computerprogrammen,
• bei der künstlichen Erzeugung von Rauschen (Pseudozufallsrauschen),
• in der Spreizspektrum-Technik,
• im Bereich der Kryptographie, siehe Kryptographisch sicherer Zufallszahlengenerator.

Unangebracht ist das Nutzen von Pseudozufallszahlen in Bereichen, wo echter Zufall vonnöten ist. Zur Erzeugung echter Zufallszahlen benötigt man entweder einen echten Zufallsgenerator (z. B. durch Digitalisieren von Rauschen oder durch Ausnutzen von Quanteneffekten) oder zumindest eine Quelle quasizufälliger (normalerweise nicht vorhersagbarer) Ereignisse wie Zeiten von Benutzereingaben oder Netzwerkaktivität.

Die PRNGs in der Laufzeitbibliothek einer Programmierumgebung sind nicht immer von hoher Qualität. In Anwendungen, in denen die Qualität der verwendeten Pseudozufallszahlen kritisch ist, sollte man dies überprüfen und ggfs. einen eigenen PRNG implementieren.

Nicht-periodischer/unendlicher Generator

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 ${\sqrt {n}}\notin \mathbb {Q}$ gilt, was immer der Fall ist, wenn die Wurzel keine ganze Zahl ist. Klassischerweise kann man statt ${\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 ${\tfrac {f_{1}}{f_{2}}}$ eine irrationale Zahl ist, also $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 $f_{1}$ erzeugtes Pseudozufallssignal, das mit der Frequenz $f_{2}$ abgetastet/eingelesen wird.

Erzeugung von Pseudo-Zufallszahlen durch primitive Polynome

Primitive Polynome definieren eine wiederkehrende Relation, die verwendet werden kann, um Bits von Pseudozufallszahlen zu erzeugen. Tatsächlich steht jedes linear rückgekoppelte Schieberegister mit maximalem Zyklus (dieser ist 2^{lfsr length} - 1) mit primitiven Polynomen in Beziehung.

Sei z. B. ein primitives Polynom $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 $2^{10}-1=1023$ Pseudo-Zufalls-Bits zu erzeugen. Für eine Maximum Length Sequence sind ganz bestimmte Ausgänge des Schieberegisters erforderlich.

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

Literatur

• Donald E. Knuth: The Art of Computer Programming. Pearson Education, 03. Auflage 1997.
• Harvard.edu: Pseudorandomness (in Englisch)

Weblinks

Commons: Pseudozufall – Sammlung von Bildern, Videos und Audiodateien

• Die Website naRND ist eine Dokumentation über nicht-arithmetische (Pseudo-)Zufallszahlen