Pseudozufall

Als Pseudozufall wird bezeichnet, was zufällig erscheint, in Wirklichkeit jedoch berechenbar ist. In diesem Sinn generieren Pseudozufallszahlengeneratoren, wie kryptographisch sichere Zufallszahlengeneratoren, pseudozufällige Zahlen.

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

Die wichtigste Anwendung von Pseudozufallszahlen sind die sogenannten Zufallsgeneratoren, die in praktisch allen Programmiersprachen verfügbar sind. Dass es sich dabei meist lediglich um Pseudozufallszahlengeneratoren (englisch PRNG, pseudo random number generator) handelt, wird häufig übersehen. 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 pseudozufällige Zahlenfolge erzeugt.

Sie verletzen damit bestimmte Eigenschaften echter Zufallszahlen, sind jedoch von Computern wesentlich einfacher herzustellen. Oft werden periodische Zahlenfolgen erzeugt, die gleichen Zahlen wiederholen sich also nach einer bestimmten Länge. Der Vorteil von PRNGs ist die hohe Geschwindigkeit. Durch geschickte Wahl der Parameter kann man die Periode genügend groß machen. Einige Pseudozufallszahlengeneratoren generieren nur endliche Zahlenfolgen.

Verwendung von Pseudozufallszahlen

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 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.

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^{lrsr 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

Weblinks

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