Pseudozufälligkeit - Pseudorandomness

Eine pseudozufällige Zahlenfolge scheint statistisch zufällig zu sein , obwohl sie durch einen vollständig deterministischen und wiederholbaren Prozess erzeugt wurde.

Hintergrund

Die Generierung von Zufallszahlen hat viele Verwendungsmöglichkeiten, wie zum Beispiel für Zufallsstichproben , Monte-Carlo-Methoden , Brettspiele oder Glücksspiele . In der Physik sind jedoch die meisten Prozesse, wie die Erdbeschleunigung, deterministisch, d. h. sie führen immer vom gleichen Ausgangspunkt zum gleichen Ergebnis. Einige bemerkenswerte Ausnahmen sind der radioaktive Zerfall und die Quantenmessung , die beide als wirklich zufällige Prozesse in der zugrunde liegenden Physik modelliert werden. Da diese Prozesse keine praktischen Quellen für Zufallszahlen sind, verwenden Menschen Pseudozufallszahlen, die idealerweise die Unvorhersehbarkeit einer echten Zufallsfolge aufweisen, obwohl sie durch einen deterministischen Prozess erzeugt werden.

In vielen Anwendungen ist der deterministische Prozess ein Computeralgorithmus, der als Pseudozufallszahlengenerator bezeichnet wird und dem zuerst eine als Zufallsstartwert bezeichnete Zahl bereitgestellt werden muss . Da derselbe Seed jedes Mal dieselbe Sequenz ergibt, ist es wichtig, dass der Seed gut ausgewählt und verborgen bleibt, insbesondere in Sicherheitsanwendungen , wo die Unvorhersehbarkeit des Musters ein kritisches Merkmal ist.

In einigen Fällen , in denen es wichtig , dass die Sequenz nachweislich unberechenbar zu sein, haben die Menschen von einer Funk abgestimmt zwischen den Stationen oder vermischten Timings von Menschen physische Quellen von Zufallszahlen, wie radioaktive Zerfall, atmosphärisches elektromagnetisches Rauschen geerntet verwendet Tastenanschlägen . Der Zeitaufwand, der erforderlich ist, um diese Zahlen zu erhalten, führt zu einem Kompromiss: einige dieser physikalischen Messwerte als Keim für einen Pseudozufallszahlengenerator zu verwenden.

Geschichte

Vor der modernen Informatik erzeugten Forscher, die Zufallszahlen benötigten, diese entweder durch verschiedene Mittel ( Würfel , Karten , Rouletteräder usw.) oder nutzten vorhandene Zufallszahlentabellen.

Der erste Versuch, den Forschern einen Vorrat an Zufallsziffern zur Verfügung zu stellen, war 1927, als die Cambridge University Press eine von LHC Tippett entwickelte Tabelle mit 41.600 Ziffern veröffentlichte . 1947 generierte die RAND Corporation Zahlen durch die elektronische Simulation eines Rouletterads; die Ergebnisse wurden schließlich 1955 als A Million Random Digits mit 100.000 normalen Abweichungen veröffentlicht .

In rechnerischer Komplexität

In der theoretischen Informatik , eine Verteilung ist Pseudo - Zufall gegen eine Klasse von Gegnern , wenn kein Gegner aus der Klasse aus der gleichmäßigen Verteilung mit signifikantem Vorteile unterscheiden kann. Dieser Begriff der Pseudozufälligkeit wird in der Computational Complexity Theory untersucht und findet Anwendung in der Kryptographie .

Formal seien S und T endliche Mengen und sei F = { f : ST } eine Klasse von Funktionen. Eine Verteilung D über S ist ε- pseudozufällig gegen F, wenn für jedes f in F der statistische Abstand zwischen den Verteilungen und , wobei und von D abgetastet wird , und , wobei und von der Gleichverteilung auf S abgetastet wird, höchstens ε . ist .

In typischen Anwendungen beschreibt die Klasse F ein Berechnungsmodell mit begrenzten Ressourcen, und man ist daran interessiert, Verteilungen D mit bestimmten Eigenschaften zu entwerfen , die gegen F pseudozufällig sind . Die Verteilung D wird oft als Ausgabe eines Pseudozufallsgenerators angegeben .

Siehe auch

Verweise

  1. ^ a b George Johnson (12. Juni 2001). „Kenner des Chaos bieten ein wertvolles Produkt: Zufall“ . Die New York Times .
  2. ^ SP Vadhan (2012). Pseudozufälligkeit . Pseudozufälligkeit, die Theorie der effizienten Erzeugung von Objekten, die „zufällig aussehen“, obwohl sie mit geringer oder keiner Zufälligkeit konstruiert wurden
  3. ^ Mark Ward (9. August 2015). "Die Zufallszahlen des Webs sind zu schwach, warnen Forscher" . BBC .
  4. ^ Jonathan Knudson (Januar 1998). "Javatalk: Hufeisen, Handgranaten und Zufallszahlen". Sun-Server . S. 16–17.
  5. ^ a b "Eine Million zufällige Ziffern" . RAND Corporation . Abgerufen am 30. März 2017 .
  6. ^ Oded Goldreich. Computational Complexity: Eine konzeptionelle Perspektive. Cambridge University Press. 2008.
  7. ^ "Pseudozufälligkeit" (PDF) .

Weiterlesen

Externe Links