Pseudozufall

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Pseudozufallszahl)
Wechseln zu: Navigation, Suche
Dieser Artikel ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Die fraglichen Angaben werden daher möglicherweise demnächst entfernt. Bitte hilf der Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst.

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

Pseudozufall in der Berechenbarkeitstheorie[Bearbeiten | Quelltext bearbeiten]

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 harter Funktionen voraus.

Pseudozufallszahlen[Bearbeiten | Quelltext bearbeiten]

Die wichtigste Anwendung von Pseudozufallszahlen sind die so genannten Zufallsgeneratoren, die in praktisch allen Programmiersprachen verfügbar sind. Dass es sich dabei meist lediglich um Pseudozufallszahlengeneratoren (engl. 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 so genannten Saat (engl. 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[Bearbeiten | Quelltext bearbeiten]

Pseudozufallszahlen finden u. a. Anwendung

  • bei der künstlichen Erzeugung von Rauschen

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[Bearbeiten | Quelltext bearbeiten]

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 gilt, was immer der Fall ist, wenn die Wurzel keine ganze Zahl ist. Klassischerweise kann man statt 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 eine irrationale Zahl ist, also 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 erzeugtes Pseudozufallssignal, das mit der Frequenz abgetastet/eingelesen wird.

Erzeugung von Pseudo-Zufallszahlen durch primitive Polynome[Bearbeiten | Quelltext bearbeiten]

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 2lrsr length - 1) mit primitiven Polynomen in Beziehung.

Sei z. B. ein primitives Polynom gegeben. Man beginnt mit einer benutzerdefinierten Startwert (engl. 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 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 , dass dieser Vorgang Pseudo-Zufallszahlen erzeugt, bevor die Sequenz sich wiederholt.

Literatur[Bearbeiten | Quelltext bearbeiten]

Donald E. Knuth: The Art of Computer Programming. Pearson Education, 3. Auflage 1997.

Weblinks[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Tietze/Schenk, "Halbleiter-Schaltungstechnik", 3. Auflage 1976, S.590 ff, in späteren Auflagen nicht mehr beschrieben.