imported>Skranon am 23. September 2025 um 20:50 Uhr

2025-09-23T20:50:48Z

Neue Seite

{{Quellen|2=Dieser Artikel}}
Als '''Pseudozufall''' wird bezeichnet, was [[Zufall|zufällig]] erscheint, in Wirklichkeit jedoch [[Berechenbarkeit|berechenbar]] ist, d. h. durch einen bekannten [[Algorithmus]] mit bekannten Eingabedaten reproduziert werden kann. In diesem Sinn generieren [[Zufallszahlengenerator|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 [[Effizienz (Informatik)|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 [[NP-Schwere|schwerer Funktionen]] voraus.

== Pseudozufallszahlen ==
Pseudozufallszahlen werden von Pseudozufallszahlengeneratoren (englisch PRNG, pseudo random number generator) erzeugt, die in praktisch allen [[Programmiersprache]]n verfügbar sind. Sie erzeugen eine [[Folge (Mathematik)|Zahlenfolge]], die zwar [[Zufall|zufällig]] aussieht, es aber nicht ist, da sie durch einen [[Determinismus (Algorithmus)|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 [[Zufallszahl]]en, sind jedoch von [[Computer]]n 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 <math>2^{64}</math>). Der Vorteil von PRNGs im Vergleich zu echten [[Zufallszahlengenerator|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 [[Stochastischer Prozess|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 [[Computerprogramm]]en,
* bei der künstlichen Erzeugung von [[Rauschen (Physik)|Rauschen]] ([[Pseudozufallsrauschen]]),
* in der [[Frequenzspreizung|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 [[Zufallszahl]]en benötigt man entweder einen echten [[Zufallszahlengenerator|Zufallsgenerator]] (z. B. durch [[Digitalisierung|Digitalisieren]] von Rauschen oder durch Ausnutzen von [[Quantenmechanik|Quanteneffekten]]) oder zumindest eine Quelle quasizufälliger (normalerweise nicht vorhersagbarer) Ereignisse wie Zeiten von Benutzereingaben oder Netzwerkaktivität.

Die PRNGs in der [[Laufzeitbibliothek]] einer [[Integrierte Entwicklungsumgebung|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 [[Ganze Zahl|ganzen Zahl]] als Zufallszahlen. Hierbei ist selbstverständlich darauf zu achten, dass die resultierende Wurzel eine [[irrationale Zahl]] ist, das heißt, dass <math>\sqrt{n}\notin \mathbb{Q}</math> gilt, was immer der Fall ist, wenn die Wurzel keine ganze Zahl ist. Klassischerweise kann man statt <math>\sqrt{n}</math> 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 [[Inkommensurabilität (Mathematik)|inkommensurabel]] sind; wenn also deren Frequenzverhältnis <math>\tfrac{f_1}{f_2}</math> eine irrationale Zahl ist, also <math>n_1 \cdot f_1 = n_2 \cdot f_2</math> nicht erfüllt wird. Weil unter den [[Reelle Zahl|reellen Zahlen]] die [[Rationale Zahl|rationalen Zahlen]] eine [[Lebesgue-Maß|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 <math>f_1</math> erzeugtes Pseudozufallssignal, das mit der Frequenz <math>f_2</math> abgetastet/eingelesen wird.

=== Erzeugung von Pseudo-Zufallszahlen durch primitive Polynome ===
[[Primitives Polynom|Primitive Polynome]] definieren eine wiederkehrende Relation, die verwendet werden kann, um Bits von Pseudozufallszahlen zu erzeugen. Tatsächlich steht jedes [[linear rückgekoppeltes Schieberegister|linear rückgekoppelte Schieberegister]] mit maximalem Zyklus (dieser ist 2<sup>lfsr length</sup> - 1) mit primitiven Polynomen in Beziehung.

Sei z. B. ein primitives Polynom <math>X^{10} + X^3 + 1</math> 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 [[Kontravalenz|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 <math>2^{10}-1 = 1023</math> Pseudo-Zufalls-Bits zu erzeugen. Für eine [[Maximum Length Sequence]] sind ganz bestimmte Ausgänge des Schieberegisters erforderlich.<ref>Tietze/Schenk, "Halbleiter-Schaltungstechnik", 3. Auflage 1976, S. 590 ff, in späteren Auflagen nicht mehr beschrieben.</ref>

Allgemein gilt für ein primitives Polynom des Grades <math>m</math>, dass dieser Vorgang <math>2^m -1</math> Pseudo-Zufallszahlen erzeugt, bevor die Sequenz sich wiederholt.<ref>{{Internetquelle |url=https://de.wikibooks.org/wiki/Waldbrandsimulation#PseudoRandom |titel=Waldbrandsimulation / Abschnitt PseudoRandom – Wikibooks, Sammlung freier Lehr-, Sach- und Fachbücher |sprache=de |abruf=2024-12-03}}</ref>

== Literatur ==
* Donald E. Knuth: ''The Art of Computer Programming.'' Pearson Education, 03. Auflage 1997.
* [http://people.seas.harvard.edu/~salil/pseudorandomness/ Harvard.edu: Pseudorandomness] (in Englisch)

== Weblinks ==
{{Commonscat|Pseudorandomness|Pseudozufall}}
* [http://www.narnd.de Die Website naRND ist eine Dokumentation über nicht-arithmetische (Pseudo-)Zufallszahlen]

== Einzelnachweise ==
<references />

[[Kategorie:Kryptologie]]
[[Kategorie:Stochastik]]

Pseudozufall - Versionsgeschichte

imported>Skranon am 23. September 2025 um 20:50 Uhr