"Zufallszahlen"
Probabilistische Algorithmen 2
Einführung
Für probabilistische Algorithmen und Vorhersagen benötigt man Zufällige Ereignisse.
Der Computer ist auf Grund des Determinismus (eine bestimmte Eingabe führt bei identischer Verarbeitung stets zu der selben Ausgabe) ein schlechter Zufallszahlengenerator. Die Frage, was kann man überhaupt als Zufall bezeichnen?, beantworten wir für uns so: Ein Zustand tritt dann zufällig ein, wenn er nicht vorhersagbar ist.
Im folgenden Beispiel nehmen wir einen Anfangswert (seed) und berechnen daraus unsere "Zufallszahl" ... schon die Aussage Zufallszahl BERECHNEN lässt uns erahnen, dass dahinter "nur" ein deterministischer Algorithmus steckt, der jedoch auf Grund seiner Komplexität einfach nicht so leicht überschaubar ist.
Wir nutzten für den Aufruf die Java-Funktion "Random".
Der Algorithmus, der sich dahinter verbirgt arbeitet in etwa so: Zufallszahl = (sehr_große_Prim * seed + sehr_große_Prim2) modulo 2⁶⁴
Damit kann man nun auch eine "zufällige" Kette von Zahlen erzeugen: Zufallszahl = (sehr_große_Prim * Zufallszahl-1 + sehr_große_Prim2) modulo 2⁶⁴
Nun liefert uns das jedoch zwar eine große Zahl, jedoch jedes mal die gleiche...wenn wir nun jedes Mal eine beliebige Zahl eingeben würden hätten wir ein durchaus unduchschaubares Ergebnis, JEDOCH nur wenn wir das Ergebnis noch nicht kennen. Noch besser währe es, wenn wir nichteinmal die Eingabezahl wüssten... Der implementierte Algorithmus kann das.
Rufen Sie die Prozedur ohne Eingabeparameter auf.
Der hierbei verwendete seed ist die UNIX-Systemzeit. Das ist ausreichend unvorhersehbar für zum Beispiel Simulationen, reicht jedoch noch lange nicht aus in der Kryptologie.
Der prinzipielle Anspruch an Zufallszahlen ist: möglicht große bzw möglichst keine erkennbare Periode, gleichförmige Verteilung und keinerlei Zusammenhänge zwischen den gewonnen Zahlen.
Der Anspruch an Zufallszahlen variiert sehr stark je nach Anwendungsbereich. Für ein simples Würfelspiel reicht es schon aus, wenn man den Algorithmus nicht durchschauen kann...dh. die Ergebnisse ausreichend unvorhersehbar und ausreichend gleich verteilt sind. Für Anwendungen in der Kryptografie hingegen ist es unbedingt erforderlich nicht reproduzierbare Zahlen zu erzeugen - also benötigen wir ein nicht deterministisches Verfahren.
Da das ureigenste Prinzip des Computers der Determinismus ist, ist uns dieses nicht möglich. Vielmehr können wir nur versuchen unseren seed schon sehr beliebig (möglichst zufällig) zu wählen.
Hierfür bietet sich die UNIX-Systemzeit an (ein sich immerhin im Sekundentakt ändernder Wert). Für Anwendungen die unter allen Umständen unnachvollziehbar bleiben sollen oder eine sehr hohe Taktrate an Zufallszahlen benötigen ist dies jedoch immernoch nicht ausreichend.
Testen sie die Java-Prozedur myRandom, zunächst mit selbst gewähltem seed. Bei keinem selbst vorgegebenen seed, nimmt die Prozedur myRandom die UNIX-Systemzeit und wir erhalten (für uns) echte unvorhersagbare Zufallszahlen.
<eval> myRandom(123456789); </eval>
...ein kleiner Anreiz zum ausprobieren: java.lang.Math.abs(myRandom()%100);
Es gibt natürlich auch noch andere Möglichkeiten Zufallszahlen zu erzeugen
Um für die manche Anwendungsfälle in der Praxis taugliche Zufallszahlen zu erzeugen werden physikalische Zufallszahlengeneratoren verwendet. Sie nutzten physikalische Prozesse wie elektrisches oder thermisches Rauschen, Bildrauschen von Web-Cams oder Radioaktiven Zerfall. Ein nettes Beispiel findet ihr hier: http://von-und-fuer-lau.de/randcam.html