Archiv verlassen und diese Seite im Standarddesign anzeigen : Wie zufällig sind Zufallsgeneratoren wirklich?
Und warum sagt man immer, daß Computergenerierte Zufallszahlen nie zufällig sind?
http://de.wikipedia.org/wiki/Zufallszahlengenerator
anderer Gast
2009-01-01, 04:20:25
Da kann man Danke sagen...
Da kann man Danke sagen...
Danke kannst du via Google suchen.
redfalcon
2009-01-01, 11:58:39
Und warum sagt man immer, daß Computergenerierte Zufallszahlen nie zufällig sind?
Weil sie sich irgendwo vom System ein nicht-zufälliges Element zur Berechnung abgreifen. Bei math.random() in Java ist es z.B. (afaik) die aktuelle Systemzeit.
Gnafoo
2009-01-01, 13:55:31
Naja sie sind eben deterministisch. Wenn du den Anfangswert und den Algorithmus kennst, kannst du die gesamte Folge voraussagen. So etwas geht bei echtem Zufall nicht. Wobei man das auch etwas verbessern kann: man kann auch äußere mehr oder weniger zufällige Quellen hinzuziehen um die Zahlen zu berechnen. z. B. die Mausbewegung. TrueCrypt hat beispielsweise diese Möglichkeit beim Generieren von Passwörtern.
Trotzdem bleibt die Berechnung der nächsten Zahl an sich deterministisch.
Monger
2009-01-01, 16:41:28
An der Stelle wird es schnell philosophisch: gibt es irgendeinen Zufall der nicht deterministisch ist? :ugly:
Das Problem bei computergenerierten Zufallszahlen ist die Anfangszahl (oftmals als "Seed" bezeichnet). Der selbe Seed erzeugt immer die selbe Reihe an Zufallszahlen - diese sind allerdings so gut gestreut, dass man da von einer Gleichverteilung sprechen kann.
Manchmal kann das nützlich sein. Manchmal ist es wünschenswert, dass man ein bestimmtes zufälliges Verhalten reproduzieren kann. Dann braucht man nur den richtigen Seed, und hat wieder genau die selben Ausgangsbedingungen. Das muss aber der Entwickler entscheiden - und die richtige Wahl des Seeds ist wieder eine Wissenschaft für sich.
Rhönpaulus
2009-01-01, 16:58:11
mittels software kann man logischerweise niemals gute zufallszahlen generieren da sie immer auf einem durchschaubaren algorythmus basieren.
wenn für ein system nur eine geringe anzahl pseudozufällig generierter zahlen notwendig ist so reicht das aus weil zur analyse des algorythmus große mengen dieser zahlen erforderlich sind.
kaum vorhersagbare zufallszahlen gewinnt man durch digitalisierung von rauschquellen deren entstehung auf nicht vorhersagbaren quantenmechanischen effekten beruht.
wenn der zahlenraum groß genug ist helfen auch statisitische analysemethoden auf große zahlenmengen angewannt nicht weiter.
mittels software kann man logischerweise niemals gute zufallszahlen generieren da sie immer auf einem durchschaubaren algorythmus basieren.Das ist aber irrelevant wenn die Zufallszahlenfolge statistisch nicht von echten Zufallszahlen unterscheidbar ist und die Periode so groß ist, dass sie sich während des Laufens der Applikation nicht wiederholt.
An der Stelle wird es schnell philosophisch: gibt es irgendeinen Zufall der nicht deterministisch ist? :ugly:Ja.
Manchmal kann das nützlich sein. Manchmal ist es wünschenswert, dass man ein bestimmtes zufälliges Verhalten reproduzieren kann. Dann braucht man nur den richtigen Seed, und hat wieder genau die selben Ausgangsbedingungen. Das muss aber der Entwickler entscheiden - und die richtige Wahl des Seeds ist wieder eine Wissenschaft für sich.Da gibt es keinen "richtigen" Seed. Man muss nur denselben Randomseed nehmen.
Spasstiger
2009-01-01, 21:58:34
Das ist aber irrelevant wenn die Zufallszahlenfolge statistisch nicht von echten Zufallszahlen unterscheidbar ist
Genau da liegt aber das Problem.
Die Momente der errechneten Zufallsfolge sollten eigentlich nicht von den theoretischen Momenten der verwendeten Verteilungsfunktion abweichen - mit einer Ungenauigkeit von 1/n, wobei n die Länge der Zufallsfolge ist.
Jetzt habe ich mal in Matlab die Momente von gleichverteilten Zufallsfolgen errechnet, welche mit dem Mersenne-Twister-Algorithmus mit einer Periodenlänge von (2^19937-1)/2 erzeugt wurden (der Standard-Algorithmus für Gleichverteilungen seit Matlab 7.4).
Das sind die Momente der verwendeten Gleichverteilung:
Erwartungswert = 0,5
Varianz = 1/12 = 0.08333...
Schiefe = 0
Kurtosis = 1,8
Diese Statistik sollte auch durch die generierten Zufallsfolgen abgebildet werden. Die Folgen sind jeweils 10^5 Werte lang, also ist der systembedingte Fehler 10^-5 = 0,00001. Da der Zufallsgenerator Zahlen in Double-Precision-Darstellung mit 64 Bit Genauigkeit erzeugt, sollten Rundungsfehler eigentlich vernachlässigbar sein.
Erlaubter Fehler e = 0,00001
Die folgende Statistik ergibt sich im Mittel bei der Auswertung von 1000 solcher Zufallsfolgen:
Erwartungswert = 0,499994645733748... => Abweichung = 5,4*e
Varianz = 0.083330896452396... => Abweichung = 2,4*e
Schiefe = 1.503142090204923e-005 => Abweichung = 15,0*e
Kurtosis = 1.800032404925645... => Abweichung = 32,4*e
Die Abweichungen von den Idealwerten sind also jeweils deutlich größer als der erlaubte Fehler, vor allem beim 4.Moment (Kurtosis) ist die Abweichung auffällig groß.
Gut, ein gewisser Fehler ist natürlich immer noch zufallsbedingt, aber der sollte imo nicht so groß sein wie bei den Werten oben.
Durch das Gesetz der großen Zahl nimmt der absolute Fehler wahrscheinlich zu. Relativ gesehen nimmt er ab. Gerade weil du Zufallszahlen hast, kommst du nie genau auf den Mittelwert.
Spasstiger
2009-01-01, 22:34:30
Durch das Gesetz der großen Zahl nimmt der absolute Fehler wahrscheinlich zu. Relativ gesehen nimmt er ab.
Wie meinst du das? Ich verstehe nicht ganz, was du hier mit dem Gesetz der großen Zahlen meinst.
Die Abweichungen sind auf jeden Fall sehr konstant, auch wenn ich mehr Folgen auswerte. Wenn die Abweichungen auch rein stochastisch wären, dürften sie ja nicht für jede Folge ungefähr gleich sein.
RavenTS
2009-01-02, 12:01:14
Wollte man da nicht mal irgendwelche Einheiten in CPUs einbauen, die explizit versuchen irgendwelches Rauschen zu erzeugen, aus dem man dann nur für kryptografische Berechnungen Nutzen ziehen kann.?!
Pinoccio
2009-01-02, 12:16:47
Das ist aber irrelevant wenn die Zufallszahlenfolge statistisch nicht von echten Zufallszahlen unterscheidbar ist und die Periode so groß ist, dass sie sich während des Laufens der Applikation nicht wiederholt.Praktisch ja, theoretisch nein. Eine Folge der Länge n ist schon nicht merh (n+1)-dimensional Normalverteilt.
Wollte man da nicht mal irgendwelche Einheiten in CPUs einbauen, die explizit versuchen irgendwelches Rauschen zu erzeugen, aus dem man dann nur für kryptografische Berechnungen Nutzen ziehen kann.?!Ja, gibt es seit 2003(? also veröffentlicht 2003 (http://www.heise.de/newsticker/VIAs-Prozessor-der-siebten-Generation--/meldung/33868) und lieferbar 2005 oder so ähnlich):
VIA PadLock-Security-Initiative (http://de.viatech.com/de/initiatives/padlock/), mit wohl durchaus brauchbaren Resultaten (http://www.via.com.tw/en/downloads/whitepapers/initiatives/padlock/evaluation_padlock_rng.pdf).
mfg
Praktisch ja, theoretisch nein. Eine Folge der Länge n ist schon nicht merh (n+1)-dimensional Normalverteilt.Was bei genügend großen n keine praktische Relevanz mehr hat. Von einigen Spezialproblemen abgesehen sind heute bekannte gute Verfahren schnell genug und halten alle statistischen Anforderungen stand, die echte Zufallszahlen auch haben.
Selbst wenn Verfahren und letzte Zufallszahl bekannt sind, lässt sich bei vielen Verfahren (mit vertretbarem Aufwand) nicht die folgende Pseudozufallszahl bestimmen.
Wie meinst du das? Ich verstehe nicht ganz, was du hier mit dem Gesetz der großen Zahlen meinst.
Die Abweichungen sind auf jeden Fall sehr konstant, auch wenn ich mehr Folgen auswerte. Wenn die Abweichungen auch rein stochastisch wären, dürften sie ja nicht für jede Folge ungefähr gleich sein.Du hattest die Abweichungen von 1000 Zufallsfolgen genannt.
Mit dem Gesetz der großen Zahl meine ich, dass du bei 1000000 Münzwürfen (bei angenommener Gleichverteilung) wahrscheinlich eine höhere absolute Differenz von Erwartungswert hast als bei 1000 Münzwürfen. Die relative Abweichung sinkt natürlich (jedenfalls wahrscheinlich.)
In der aktuellen c't (2 2009) gibt es einen Artikel zu Zufallszahlen.
Pinoccio
2009-01-04, 14:03:12
Was bei genügend großen n keine praktische Relevanz mehr hat. Von einigen Spezialproblemen abgesehen sind heute bekannte gute Verfahren schnell genug und halten alle statistischen Anforderungen stand, die echte Zufallszahlen auch haben.(Erfreulicherweise) ja.
Selbst wenn Verfahren und letzte Zufallszahl bekannt sind, lässt sich bei vielen Verfahren (mit vertretbarem Aufwand) nicht die folgende Pseudozufallszahl bestimmen.I.d.R. lässt sich nie herausfinden, wo man gerade ist, da die ausgegebenen (Einzel-)Zahlen zu kurz sind. (Man betrachte als Gedankenexperiment einen Zufallsgenerator, der nur 0 oder 1 ausspuckt ...)
Du hattest die Abweichungen von 1000 Zufallsfolgen genannt.
Mit dem Gesetz der großen Zahl meine ich, dass du bei 1000000 Münzwürfen (bei angenommener Gleichverteilung) wahrscheinlich eine höhere absolute Differenz von Erwartungswert hast als bei 1000 Münzwürfen. Die relative Abweichung sinkt natürlich (jedenfalls wahrscheinlich.)Ich hab in einer meiner Statistikvorlesungen zu hören bekommen, daß jede genannte Zahl zu klein sei im Sinne des Gesetztes der großen Zahlen ...
@Spasstiger: Kannst du dein matlab-Skript mal posten (oder auch per PN)?
In der aktuellen c't (2 2009) (http://www.heise.de/ct/09/02/006/) gibt es einen Artikel zu Zufallszahlen.Danke für den Tip!
mfg
Was bei genügend großen n keine praktische Relevanz mehr hat. Von einigen Spezialproblemen abgesehen sind heute bekannte gute Verfahren schnell genug und halten alle statistischen Anforderungen stand, die echte Zufallszahlen auch haben.
Selbst wenn Verfahren und letzte Zufallszahl bekannt sind, lässt sich bei vielen Verfahren (mit vertretbarem Aufwand) nicht die folgende Pseudozufallszahl bestimmen.
Du hattest die Abweichungen von 1000 Zufallsfolgen genannt.Trotzdem sind die Anfroderungen zb. der NSA schon anders was Zufallsgeneratoren angeht.
Alles andere hat ja nicht zu unrecht den Namen PSEUDOzufallszahlengenerator. Gute Softwarelösungen bieten daher die Option der zusätzlichen Entropie, also das Sammeln von Zufallswerten durch eine Interaktion mit dem Benutzer. Zb. Mausbewegungen über einem s/w "Rauschbild", Tasteneinschläge usw.
Andere ernstzunehmende Lösungen die nicht auf die Interaktion setzen können bringen dagegen etliche zusätzliche Skills zum puren Programmkode. So werden etliche Systemeigenschaften der Entropie hinzugefügt die man in das Berechnen einfliessen läßt. Größen aus dem Speichermanagment des Systems, Temperaturen, irgendwelche Systemeinstellungen, Daten der Datenträger (Belegung von zufällig gewählten Dateien), Uhr/Timer-Werte, PIDs der Prozesse, Systemeinstellungen usw. usw.
Das alles dann auch mathematisch zufällig ausgewählt.
Wie man sieht vertrauen Profis nicht alleine auf die auch so guten mathematischen Formeln, sonder lassen wie gesagt immer auch weitere Entropie in die Berechnung einfliessen.
Bei solchen Lösungen kann man aber ruhig sagen, daß sie ausgezeichnete Pseudozufallszahlen liefern.
Wirklich angesehen habe ich mir mal nur den Generator von KeePass angesehen. Und muß sagen, der machts wirklich so wie man es von einem Profi erwarten würde.
Durch das Gesetz der großen Zahl nimmt der absolute Fehler wahrscheinlich zu. Relativ gesehen nimmt er ab. Gerade weil du Zufallszahlen hast, kommst du nie genau auf den Mittelwert.
Es gibt nicht das Gesetz der großen Zahl. Mittelwert != Erwartungswert
das schwache Gesetz der großen Zahlen sagt aus das für jedes Epsilon > 0
der Grenzwert der Wahrscheinlichkeit größergleich Epsilon der Summe paarweiser (stoch) unabhängiger ZG minus dem denselben Erwartungswert im Mittel 0 ist.
Zurück zur Ausgangsfrage:
Wenn ein Zufall ein Ereignis ist, welches sich nicht vorhersehen läßt, dann muß man auch immer dazu fragen: für wen?
Wenn ein Zufallsgenerator in einem Computer einen zufälligen Wert generiert, dann ist dieser Wert für einen Menschen der Gegenwart ohne Hilfsmittel in der Regel nicht vorhersehbar und damit zufällig. Für einen Menschen mit einem Computer als Hilfsmittel, trifft diese Aussage bereits nicht mehr zu. Der andere Computer, der über denselben Algorithmus verfügt, kann ohne Probleme jedes generierte Ergebnis nachvollziehen und sogar mit 100%iger Wahrscheinlichkeit voraussagen. Der Mensch hat sich inzwischen mit dem Werkzeug: Computer so gut vertraut gemacht, daß sämtliche elektronisch erzeugten 'Zufälle' keine Zufälle im eigentlichen Sinne mehr sind.
Echte Zufälle (wenn es diese überhaupt gibt) müssen daher über Vorgänge generiert werden, die sich der menschlichen Kontrolle entziehen (und das tun technische Apparate gerade nicht - ansonsten bekommen sie ein kleines Schildchen mit dem Aufkleber: defekt). Zur Zeit noch denkbar wäre zum Beispiel ein Zufallsgenerator, der an die Anzahl und Stärke von Sonneneruptionen gekoppelt wäre. Oder ein chemisches/physikalisches/reales Ereignis mit einem -für einen Menschen der Gegenwart- ungewissem Ausgang.
Ein echter Zufall würde sogar den Schöpfer 'überraschen'. Ich denke daher, daß man hier den Bereich der seriösen Wissenschaften verläßt/verlassen muss: An Zufälle muß man glauben.
PS: Heutige Zufallsgeneratoren sind genauso zufällig, wie die Maschinen mit denen man sie erzeugt, unzuverlässig sind. ;) Denk da mal drüber nach. Der perfekte Zufallsgenerator wäre zum Beispiel in der Lage bis in alle Ewigkeit dasselbe Ergebnis zu produzieren. Leider würde ein solcher echter Zufallsgenerator zweifelsohne vom Menschen als unbrauchbar/defekt betrachtet werden: Ich stell mir grad einen Informatiker vor, der ein kleines 'idiotensicheres' Programm zur Auswertung von Wahrscheinlichkeiten anhand eines Würfels aus dem Ärmel geschüttelt hat - und jemand hätte heimlich einen echten Zufallsgenerator in alle seine PCs eingebaut, die -egal welche Parameter er ändert & nur bei diesem einen Programm- den PC immer Sechsen 'würfeln' läßt.... ich glaube, der gute Mann würde wahnsinnig werden.
Es gibt schon Zufallsgeneratoren die auf Rauschen basieren, das z.B. durch radioaktiven Zerfall erzeugt wird. Die sind dann auch mit identischer Hard- und Software nicht nachvollziehbar, allerdings verlässt man hier auch den Bereich der Heimhardware.
Nicht unbedingt. Via-Prozessoren oder gewisse Chipsätze haben z.B. integrierte Zufallszahlgenerator die auf thermischem Rauschen basieren.
Für einen Menschen mit einem Computer als Hilfsmittel, trifft diese Aussage bereits nicht mehr zu. Der andere Computer, der über denselben Algorithmus verfügt, kann ohne Probleme jedes generierte Ergebnis nachvollziehen und sogar mit 100%iger Wahrscheinlichkeit voraussagen.
Dazu braucht man nicht nur den selben Algorithmus, sondern auch den gleichen Random-Seed und die Position. Der Seed wird normal aus Entropiequellen wie den Tastaturanschlägen o.ä. gewonnen und ist daher nicht so einfach vorhersehbar.
Ein echter Zufall würde sogar den Schöpfer 'überraschen'. Ich denke daher, daß man hier den Bereich der seriösen Wissenschaften verläßt/verlassen muss: An Zufälle muß man glauben.
Muss man nicht. Es gibt gibt in der Physik nicht deterministisch bestimmbare Dinge wie den radioaktiven Zerfall. Selbst wenn man den Zustand des Teilchens kennen würde hilft einem das nichts.
Genauer gesagt ist fast alles zufällig wenn man nur den Maßstab genug verkleinert.
Zur Zeit noch denkbar wäre zum Beispiel ein Zufallsgenerator, der an die Anzahl und Stärke von Sonneneruptionen gekoppelt wäre. Oder ein chemisches/physikalisches/reales Ereignis mit einem -für einen Menschen der Gegenwart- ungewissem Ausgang.
In der weiter oben erwähnten c't wird z.B. ein Programm vorgestellt, dass das einfach anhand einer billigen, abgedunkelten Webcam macht. Da wird dann nämlich das sehr starke Rauschen der Webcam bei wenig Licht als Zufallsquelle genutzt.
PS: Heutige Zufallsgeneratoren sind genauso zufällig, wie die Maschinen mit denen man sie erzeugt, unzuverlässig sind. ;) Denk da mal drüber nach. Der perfekte Zufallsgenerator wäre zum Beispiel in der Lage bis in alle Ewigkeit dasselbe Ergebnis zu produzieren. Leider würde ein solcher echter Zufallsgenerator zweifelsohne vom Menschen als unbrauchbar/defekt betrachtet werden: Ich stell mir grad einen Informatiker vor, der ein kleines 'idiotensicheres' Programm zur Auswertung von Wahrscheinlichkeiten anhand eines Würfels aus dem Ärmel geschüttelt hat - und jemand hätte heimlich einen echten Zufallsgenerator in alle seine PCs eingebaut, die -egal welche Parameter er ändert & nur bei diesem einen Programm- den PC immer Sechsen 'würfeln' läßt.... ich glaube, der gute Mann würde wahnsinnig werden.
Naja, man stellt ja schon so ein paar Bedingungen an die Zufallszahlen. Z.B wäre Gleichverteilung in den meisten Fällen das, was man sich unter Zufall vorstellt. Da wird dein immer 6 Generator scheitern. Denkbar wäre auch, dass sich die Punkte nicht zu stark häufen, d.h. dass gewählte Teilintervalle auch mal ne Zahl abbekommen. Oder dass man auch bei Pärchen/Tripeln annähernd Gleichverteilung hat.
Auch kommt es immer auf die Anwendung an, im Test haben die "richtigen" Zufallsgeneratoren 50-200 kByte Zahlen pro Sekunde geliefert, der Mersenne Twister aber z.B. um die 70-80 MByte pro Sekunde. Wenn du also z.B. Zufall für Simulationen brauchst, wäre es nicht so schlau, die langsame Variante zu wählen.
Naja, man stellt ja schon so ein paar Bedingungen an die Zufallszahlen. Z.B wäre Gleichverteilung in den meisten Fällen das, was man sich unter Zufall vorstellt. Da wird dein immer 6 Generator scheitern. Denkbar wäre auch, dass sich die Punkte nicht zu stark häufen, d.h. dass gewählte Teilintervalle auch mal ne Zahl abbekommen. Oder dass man auch bei Pärchen/Tripeln annähernd Gleichverteilung hat.
Nur als Hinweis. In der Statistik verwendet man da den Kolmogorov-Smirnov-Test (http://de.wikipedia.org/wiki/Kolmogorov-Smirnov-Test) oder den X²-Anpassungstest (http://de.wikipedia.org/wiki/Chi-Quadrat-Test), gibt auch noch weitere, man testet ja nicht auf exakte Gleichverteilung sondern nur innerhalb eines Signifikanzniveaus
lizardking
2009-01-08, 09:03:22
An der Stelle wird es schnell philosophisch: gibt es irgendeinen Zufall der nicht deterministisch ist?
Es gibt diesen echten Zufall, der auch als objektiver Zufall bezeichnet wird, bereits und zwar in der Quanteninformatik.
Nachdem durch die Bellsche Ungleichung ( http://de.wikipedia.org/wiki/Bellsche_Ungleichung ) bewiesen wurde, dass Quanten keine verborgenen Parameter besitzen, ist die Messung purer Zufall. Dieser ist nicht von einem konkreten Ausgangswert abhängig, nur von der eingestellten Wahrscheinlichkeit.
Auch wurde solche System bereits realisiert und auch für erste Überweisungen zwischen Banken eingesetzt: http://www.heise.de/newsticker/Erstes-Quantenkryptographie-Netz-in-Wien--/meldung/117082
Pinoccio
2009-01-08, 11:08:18
gibt auch noch weiterez.B. hier (http://www.stat.fsu.edu/pub/diehard/).
mfg
Nochmal auf die Ausgangsfrage zurückkommend, und zwar diesmal ohne Umherwerfen von Fachbegriffen sich-selbst-beweisen-müssender Statistiker (bin auch einer :)) und auch ohne philosophischen Ballast, das Ganze ist nämlich weitaus weniger philosophisch, als die Populärwissenschaften glauben machen wollen.
Wie funktioniert ein Pseudozufallsgenerator?
Zuerst hat man irgend 'ne Zahl, z.B. eine, die aus der aktuellen Uhrzeit gewonnen wird. Beispiel: Es ist jetzt 11:02:27. Bilde die Summe aus Stunden, Minuten, Sekunden. Also: 40. Behauptung: Dies ist eine Zufallszahl.
(Für Statistiker: Ja, in der Regel werden die Zufallszahlen normiert, um eine Gleichverteilung anzusteben. Warum? Weil sich daraus relativ einfach Zufallszahlen mit anderen Verteilungen berechnen lassen, z.B. über den ZGS normalverteilte Zufallszahlen).
Wenn man also nur eine einzige Zufallszahl braucht, wäre das doch schon eine brauchbare Lösung. Bedenke aber: Dies ist eine deterministische (also nicht vom Zufall abhängende) Berechnung. Zufällig ist hier gar nichts.
Wenn man mehrere Zufallszahlen braucht, wird es mit unserer Methode aber schon problematisch: Wenn ich eine Sekunde später nochmal 'ne Zufallszahl brauche, kommt mit derselben Berechnungsmethode 41 heraus. Wenn ich ein Programm schreibe, das mehrere (möglicherweise tausende von) Zufallszahlen pro Sekunde berechnen kann, kommt innerhalb eine Sekunde immer dieselbe Zahl heraus.
Das ist natürlich wenig zweckdienlich und erweckt nicht gerade den Eindruck von Zufall. Wenn ich innerhalb einer Sekunde mehrere Zufallszahlen erzeugen lassen, ist das Ergebnis 40, 40, 40, 40, ...
Das ist natürlich eine sehr einfach zu durchschauende Abhängigkeitstruktur. Wenn ich jeweils eine Sekunde warte, ist das Ergebnis (bzw. die Folge von Ergebnissen) 40, 41, 42, 43, 44, ...
Ebenfalls leicht zu durchschauen. Es muss also Ziel eines Pseudozufallsgenerators sein, die Abhängigkeitsstruktur innerhalb einer Folge von Zufallszahlen zu verwischen. Die Struktur soll nicht so leicht zu durchschauen sein, statt dessen soll der Eindruck von Zufälligkeit erzeugt werden.
Dafür bedient man sich zweier Tricks: Als erstes nimmt man für die Berechnung nicht eine so einfache Formel wie "Summe aus Stunden, Minuten, Sekunden", sondern arbeitet mit hochdimensionalen Potenzen und Wurzeln, Sinusfunktionen und was man noch so findet und mag.
Das allein nützt aber noch nicht viel. Der eigentliche Clou ist, eine Startzahl festzulegen für die erste Zufallszahl (den sog. "seed") und die zweite Zufallszahl auf Basis des Ergebnisses der ersten Berechnung zu berechnen. Beispiel: Berechne Quadratwurzel aus (Stunden³ + Minuten³ + Sekunden³).
11³ = 1.331
02³ = 8
27³ = 19.683
Summe = 21.022
Wurzel aus Summe = 144,98965.
Das ist die erste Zufallszahl. Die weiteren Zufallszahlen werden berechnet als "Quadratwurzel aus (letzte Zufallszahl)³". Die nächste Zahl ist also 1.745,84427, die nächste 72.947,1373.
Natürlich werden die Zahlen immer größer, was meist unerwünscht ist und selbst wieder eine Abhängigkeitstruktur darstellt. Durch eine andere Berechnungsmethode kann man dieses Problem lösen (tatsächlich verwendete Algorithmen leiden nicht nur nicht unter diesem Problem, sondern sind auch viel komplexer), aber die Idee ist klar geworden: Die Abhängigkeitsstruktur ist weitaus weniger offensichtlich. Noch verwaschener wird es, wenn man nicht nur die letzte Zahl, sondern auch noch ein paar der vorangegangenen Zahlen hinzuzieht.
Auch hier sieht man wieder: Das alles ist deterministisch, nix mit Zufall.
Welche Probleme ergeben sich?
Trotz sehr komplexer Berechnung der Zahlen kann man Abhängigkeiten aufdecken. Man erinnere sich an das Beispiel vom Anfang: Dort ergaben sich als Zufallszahlen 41, 42, 43, 44, ... In einem Diagramm wäre das eine lineare Verbindung der Zahlen, die Zahlen liegen also im weitesten Sinne irgendwie "nahe beieinander". Nehmen wir mal die Zahlen als Zweiertupel her:
(41, 42)
(43, 44)
(44, 45)
(46, 47) usw.
Dies kann man als Punkte oder (x, y)-Koordinaten in einem zweidimensionalen Diagramm darstellen. Würde man das zeichnen, wäre deutlich zu sehen, wie diese Punkte einen sog. Cluster bilden, also sehr nahe beieinander liegen. man kann die Zahlen aber auch als Dreiertupel zusammenfassen, also
(41, 42, 43)
(44, 45, 46)
(47, 48, 49) usw.
und als (x, y, z)-Koordinaten in ein dreidimensionales Diagramm einzeichnen. Oder auch als noch höher dimensionale Tupel (z.B. 8er-Tupel oder 162354er-Tupel). Dies kann man nun nicht mehr graphisch darstellen, aber man kann trotzdem mathematisch analysieren, ob sich Cluster bilden.
Bei Pseudozufallszahlen bilden sich fast immer solche Cluster, wenn man die Dimension der Tupel nur hoch genug wählt. Wenn man die Zahlen blos ansieht, kann man keine Abhängigkeit erkennen, auch nicht im zwei- oder dreidimensionalen Diagramm. Wohl aber in einem hundertdimensionalen Raum.
Man kann also die Abhängigkeit von Pseudozufallszahlen aufdecken, ohne den Berechnungsalgorithmus zu kennen. Je nach Anwendungsgebiet kann es also sein, dass Pseudozufallszahlen nicht "zufällig" genug sind. Wenn man sich in niedrigdimensionalen Räumen bewegt und/oder nur wenige Zahlen braucht, reichen Pseudozufallszahlen oft aus.
Aus den Gründen, die wir jetzt kennen, kann es sonst aber auch mal kritisch werden.
Was haben wir gelernt?
- Pseudozufallszahlen aus einem Zufallsgenerator sind nicht im Geringsten zufällig. An ihnen ist nichts, aber auch gar nichts zufällig, alles deterministische Berechnung.
- Pseudozufallszahlen sind gut, wenn es ihnen gelingt, die Abhängigkeitsstruktur zu verwischen, um den Eindruck zu erwecken, zufällig zu sein.
- Pseudozufallszahlen neigen zur Clusterbildung in hochdimensionalen Räumen, womit man Pseudozufallszahlen fast immer also solche entlarven kann.
Mehr oder weniger "echt" zufällige Zahlen (hier kommen jetzt die Philosophen wieder auf den Plan) kriegt man schnell und kostenlos z.B. bei Random.org (http://www.random.org), wo die Zahlen aus dem atmosphärischen Rauschen gewonnen werden. Es empfiehlt sich, solche Zahlen zu verwenden, wenn man z.B. Monte-Carlo-Simulationen durchführen will.
Von der anderen als der hier betrachteten Seite kommt man, wenn man bereits Zahlen hat (also keine Zufallszahlen erzeugen will) und diese analysieren will. Beispielsweie nehmen wir eine verschlüsselte Datei. Im Idealfall sieht dieser verschlüsselte Datenhaufen aus wie völlig zufälliges Kauderwelsch. Wenn es nicht gelingt, Abhängigkeitsstrukturen dieser als Zahlen aufzufassenden Daten nachzuweisen, liegt eine gute Verschlüsselung vor (also "gute" Pseudozufallszahlen). Andernfalls kann man aufgrund der Abhängigkeitstruktur erste Rückschlüsse auf den Verschlüsselungsalgorithmus ziehen. Schon bald ist dann eine Verschlüsselung geknackt. Einfache XOR-Verschlüsselungen beispielsweise kann man hiermit leicht aufdecken, dort ergibt sich oft eine charakteristische Clusterbildung.
So gesehen ist ein Verschlüsselungsalgorithmus ein Pseudozufallszahlengenerator!
Mittlerweile ist es 12:22. Dass die blöden Chefs auch zwischendurch immer mit Arbeit stören müssen... :-/
Teflon
2009-01-13, 12:45:30
Hallo,
lest mal den Beitrag in der c't 2/09 Seite 172.
Das Problem von Computergenerierten Zufallszahlen ist der Determinismus.
Heißt, die erzeugten Zufallszahlenreihen sind irgendwann doch wieder periodisch und deshalb vorhersehbar. Darum muß man sich mit externen Mittels behelfen.
Ist frei zitiert meinerseits.
Nicht gleich meckern. Erst lesen den Artikel lesen!
BAGZZlash
2009-01-13, 14:17:49
Das Problem von computergenerierten Zufallszahlen ist der Determinismus.
Heißt, die erzeugten Zufallszahlenreihen sind irgendwann doch wieder periodisch [...]
Nein, das heißt das nicht.
anorakker
2009-01-13, 21:32:59
Man könnte z.B. die Zahl pi hernehmen: Die ist garantiert nicht periodisch und für jemanden, der nicht wüsste was pi bedeutet, würden die Stellen wie Zufallszahlen aussehen - nur sind die eben absolut deterministisch, egal an welcher Stelle ich beginne.
RavenTS
2009-01-13, 23:08:03
Nein, das heißt das nicht.
Heißt jetzt welche Aussage genau nicht?
Der Determinismus ist wohl nicht auszuschließen ;-) und bei den mir bekannten Algorithmen (Mid-Square, verschiedene Kongruenz-Methoden) gibt es eben Periodizität, die man aber auch minimieren kann durch geschickt gewählte Parameter.
Andererseits ist der Determinismus auch ein Vorteil, wenn man gewisse "Zufallszahlen" (eben Pseudozufallszahlen) eben immer wieder erneut erzeugen kann um bei verschiedenen Simulationen nicht ständig allein dadurch neue Zustände zu bekommen...
kackspecht
2009-01-14, 02:13:55
Die Schwankungen bei den verschiedenen Spannungen und Lüfterdrehzahlen, die ausgelesen werden können, dürften zufällig sein. Zumindest "zufälliger" als die Systemzeit.
BAGZZlash
2009-01-14, 07:49:54
Heißt jetzt welche Aussage genau nicht?
Aus Determinismus folgt nicht notwendigerweise Periodizität.
Die Schwankungen bei den verschiedenen Spannungen und Lüfterdrehzahlen, die ausgelesen werden können, dürften zufällig sein. Zumindest "zufälliger" als die Systemzeit.
Schöne Idee, zumindest, um einen guten seed zu finden. Allerdings ist da wohl die Streuung zu gering: Wenn man mal die angezeigten Lüfterwerte beobachtet, sieht man, dass (wohl aufgrund von Messungenauigkeiten, je nach Messmethode) die Drehzahl i.d.R. nur drei oder vier verschiedene Werte annimmt.
Man könnte aber als seed die Anzahl verwenden, wie oft sich die Drehzahl in der letzten Minute oder Stunde verändert hat. Oder wie oft sie vom kleinsten auf den größten Wert gesprungen ist. Oder so.
Die "geringe Zufälligkeit" der Systemzeit ist übrigens nicht das Problem. Ein Zufallsgenerator steht und fällt nicht mit dem seed, sondern mit den Algorithmus.
Insgesamt schon komisch, was für mystische Vorstellungen viele von Zufallsgeneratoren haben. In #28 hab' ich doch (als Gast) geschrieben, wie sowas funktioniert. Da ist keine schwarze Kunst im Spiel, Leute. :smile:
Pinoccio
2009-01-14, 12:17:11
Aus Determinismus folgt nicht notwendigerweise Periodizität.Richtig, siehe die BBP-Reihe für Pi (http://de.wikipedia.org/wiki/Bailey-Borwein-Plouffe-Formel) oder die Liouville-Zahl (http://de.wikipedia.org/wiki/Liouville-Zahl), beide sind deterministisch, aber nicht periodisch.
mfg
kackspecht
2009-01-14, 14:44:50
Schöne Idee, zumindest, um einen guten seed zu finden. Allerdings ist da wohl die Streuung zu gering: Wenn man mal die angezeigten Lüfterwerte beobachtet, sieht man, dass (wohl aufgrund von Messungenauigkeiten, je nach Messmethode) die Drehzahl i.d.R. nur drei oder vier verschiedene Werte annimmt.
Man könnte aber als seed die Anzahl verwenden, wie oft sich die Drehzahl in der letzten Minute oder Stunde verändert hat. Oder wie oft sie vom kleinsten auf den größten Wert gesprungen ist. Oder so.
Die "geringe Zufälligkeit" der Systemzeit ist übrigens nicht das Problem. Ein Zufallsgenerator steht und fällt nicht mit dem seed, sondern mit den Algorithmus.
Je mehr Sensorwerte/Schwankungen man als Grundlage für den Algorithmus nehmen würde, desto besser. Die Systemzeit könnte man ja auch noch mit verwursten. :D
BAGZZlash
2009-01-14, 15:28:00
Je mehr Sensorwerte/Schwankungen man als Grundlage für den Algorithmus nehmen würde, desto besser. Die Systemzeit könnte man ja auch noch mit verwursten. :D
Ja klar, wie gesagt: Keine schlechte Idee. (y)
Man muss nur dafür sorgen, dass sowas portabel ist. Es muss auf allen Systemen funktionieren, d.h. es muss immer ein Tachosignal vorhanden sein, das ausgewertet werden kann (hallo, Leute mit WaKü :wave2:) und das muss betriebsystemunabhängig funktionieren. Diese Dinge sind wohl die Gründe dafür, dass das nicht so gemacht wird. Außerdem: Aus der Systemzeit kann man schon ziemlich gute Schwankungen ziehen, wenn man auch im Millisekundenbereich misst. Daraus wird als seed eine normierte Zahl berechnet, die schön im Double-Bereich auflöst.
Für Schwankungen aus dem Lüfter müsste man erstmal zumindest mehrere Sekunden lang das Signal aufzeichnen, was i.d.R. indiskutabel ist. Und wie gesagt: Der Knackpunkt ist der Algo, nicht der seed. Man beachte, dass der Algo auch folgendes leisten muss:
Angenommen, der seed ist 0,21786. Dafür muss eine völlig andere Folge von Zufallszahlen herauskommen als für einen seed von 0,21787. Dies ist keineswegs trivial, wird aber von jedem anerkannten Algo geleistet. Daran sieht man, dass der seed gar nicht sooooo wichtig ist.
Pinoccio
2009-01-14, 15:59:53
Angenommen, der seed ist 0,21786. Dafür muss eine völlig andere Folge von Zufallszahlen herauskommen als für einen seed von 0,21787. Dies ist keineswegs trivial, wird aber von jedem anerkannten Algo geleistet. Daran sieht man, dass der seed gar nicht sooooo wichtig ist.Naja, das hängt vom Problem ab, was man mit seinem PRNG machen will. Für Kryptografische Zwecke ist das ein völlig unbrauchbarer Weg, da man durchaus 2^20 oder mehr Seeds durchprobieren kann. (Siehe Rainbow-Tables für md5, der ja im Prinzip auch als PRNG durchgeht kann.)
mfg
BAGZZlash
2009-01-14, 16:27:07
Naja, das hängt vom Problem ab, was man mit seinem PRNG machen will. Für Kryptografische Zwecke ist das ein völlig unbrauchbarer Weg, da man durchaus 2^20 oder mehr Seeds durchprobieren kann. (Siehe Rainbow-Tables für md5, der ja im Prinzip auch als PRNG durchgeht kann.)
mfg
Selbstverständlich, hatte ich ja auch schon in #28 geschrieben. Dafür sind sowieso besser "echte" Zufallszahlen heranzuziehen. 2^20 ist ja auch nicht so wahnsinnig viel. Die 2^32 eines Doubles sind zwar schon erheblich mehr, trotzdem bleibt das natürlich eine Schwachstelle. Um eine spezifische Pseudozufallszahl nachzustellen, muss man jedoch nicht nur alle seeds ausprobieren, sondern erstens auch den Algo kennen (der bei MD5 ja bekannt ist) und zweitens den Pfad der Realisationen bis zu einer gewissen Tiefe nachrechnen.
Das Problem ist, dass das zwar ziemlich viele Berechnungen sind, aber ziemlich einfache, die damit also schnell durchzuführen sind. Du spricht hier also wirklich einen kritischen Punkt an, ja.
Yavion
2009-01-14, 17:39:46
Ich würde einfach das Rauschen des Mic-Eingangs auslesen. Die Varianz des Seed mag vielleicht nicht so toll sein, für die meisen Dinge sollte es aber reichen.
BAGZZlash
2009-01-14, 17:59:56
Ich würde einfach das Rauschen des Mic-Eingangs auslesen. Die Varianz des Seed mag vielleicht nicht so toll sein, für die meisten Dinge sollte es aber reichen.
Mit dem Rauschen des Mikrofons kannst Du auch direkt arbeiten. Aber warum sollte da die Streuung zu gering sein? Problem ist auch hier: Das Ganze ist hardwareabhängig und damit nicht systemunabhängig.
in der aktuellen ct ist ein artikel über zufallsgeneratoren drin.
auch werden verschiedene vorgestellt, verschiedene methoden um den eigenen generator testen zu lassen usw.
vBulletin®, Copyright ©2000-2024, Jelsoft Enterprises Ltd.