Idee für guten Zufallszahlen-Algorithmus |
| 25.11.2010, 19:40 | blackdrake | Auf diesen Beitrag antworten » |
| Idee für guten Zufallszahlen-Algorithmus Heute hatten wir in "Wahrscheinlichkeitslehre" ein paar einfache Zufallszahlengeneratoren und die Wichtigkeit bei kryptografischen Anwendungen betrachtet (allerdings alles nur angeschnitten, leider). Ich hatte mir mal Gedanken gemacht, wie ein Rechenwerk wohl eine kryptografisch sichere Zahl erzeugen kann und habe mal versucht, mir einen eigenen Algorithmus aus Interesse zu überlegen. Mir ist folgender Algorithmus eingefallen: Als Grundlage benötigen wir eine transzedente Zahl, z.B. PI oder die eulerische Zahl. Diese Zahl ist in einer Datei gespeichert. Um so mehr Nachkommastellen wir haben, desto besser. (Eine 10 MB Datei dürfte wohl auch bei heutigen Speicherverhältnissen bei Computern niemand stören.) 1. Wir lesen die Zahl pi bzw. e aus der Datei ein. Die Länge der Zahl ist L. 2. Als Saat nehmen wir die aktuelle Zeit in Millisekunden. Diese Saat sei c. 3. Nun gehen wir zu Position p(1) = c mod L. (Wenn also c>L ist, dann gehen wir wieder an den Anfang) 4. Wir lesen die Ziffer an dieser Position und geben diese Ziffer, nennen wir sie einmal d(1), als Zufallszahl aus. 5. Anschließend gehen wir (c+d(1)) mod L Stellen weiter nach rechts. Wir springen also zu Position p(2) = p(1) + (c+d(1)) mod L. Die auszugebende Zufallszahl an dieser Stelle heißt nun d(2). 6. Nachdem wir bei p(2) angekommen sind, verfahren wir genau so wie bei Schritt 4. Was meint ihr? Ist dieser Algorithmus gut? Vielleicht sogar krytografisch sicher? Meiner Ansicht nach, hat dieser Algorithmus folgende Vorteile (bitte berichtigt mich, wenn ich falsch liege): 1. Die Zufallszahlen wirken möglicherweise wie echte Zufallszahlen. ich denke nicht, dass sie eine Struktur aufweisen werden. (Aber ich teste das demnächst mit einem selbstgeschriebenen Computerprogramm mal!) 2. Man kann von einer Menge an Zufallszahlen nicht auf das ursprüngliche L oder c deuten. 3. Man kann bei einer Zufallszahlenfolge, ohne Kenntnis von c, nicht auf die nachfolgenden Zahlen schließen. Nachteile: 1. Man braucht eine große Datei mit der Zahl pi oder e, also nicht gut für Geräte mit wenig Speicher. Gruß Daniel // Edit: Hatte vergessen, die Summen von dem mod in Klammern zu setzen. // Edit 2: Klammern nochmal verbessert |
||
| 25.11.2010, 22:23 | blackdrake | Auf diesen Beitrag antworten » |
So... hab das ganze mal in JAVA geschrieben und untersucht. Das Ergebnis der Untersuchung mit PI bei meinem Algorithmus: Zahl Pi der Länge 31417 Seed: 1 Anzahl Zufallszahlen untersucht: 1000000 %-Stat 0: 10.1902% %-Stat 1: 10.0509% %-Stat 2: 9.2758% %-Stat 3: 10.5051% %-Stat 4: 9.3815% %-Stat 5: 9.9275% %-Stat 6: 10.559401% %-Stat 7: 9.819799% %-Stat 8: 10.0479% %-Stat 9: 10.2418995% Fehler: 3.190801% Das Ergebnis der Untersuchung der Zahl PI ohne Algorithmus: Zahl Pi der Länge 31417 untersucht %-Stat 0: 9.943661% %-Stat 1: 10.182385% %-Stat 2: 9.70812% %-Stat 3: 9.930929% %-Stat 4: 10.166471% %-Stat 5: 10.134641% %-Stat 6: 10.032785% %-Stat 7: 9.880001% %-Stat 8: 9.956393% %-Stat 9: 10.064614% Fehler: 1.1617913% Das Ergebnis der Untersuchung mit E bei meinem Algorithmus: Zahl E der Länge 10000 Seed: 1 Anzahl Zufallszahlen untersucht: 1000000 %-Stat 0: 9.4567% %-Stat 1: 9.9451% %-Stat 2: 11.1411% %-Stat 3: 10.9242% %-Stat 4: 10.1621% %-Stat 5: 8.8048% %-Stat 6: 10.5969% %-Stat 7: 9.8915% %-Stat 8: 10.7069% %-Stat 9: 8.3707% Fehler: 7.0623994% Das Ergebnis der Untersuchung der Zahl E ohne Algorithmus: Zahl E der Länge 10000 untersucht %-Stat 0: 9.74% %-Stat 1: 9.889999% %-Stat 2: 10.05% %-Stat 3: 10.08% %-Stat 4: 9.82% %-Stat 5: 9.92% %-Stat 6: 10.79% %-Stat 7: 10.08% %-Stat 8: 9.94% %-Stat 9: 9.690001% Fehler: 2.0% Die Zahlen sind leider weniger gleichverteilt. Aber ich hätte mir schon eine bessere Gleichverteilung erwünscht. Scheinbar sortiert mein Algorithmus die Zahlen. Mh... vielleicht hat die leicht unsaubere Verteilung ja damit was zu tun? http://www.spiegel.de/wissenschaft/mensc...,353818,00.html . Desweiteren habe ich festgestellt, dass der Fall c = 0 (Seed) ausgeschlossen werden muss. Bei der Zahl pi würde es sonst zu einem "Deadlock" kommen, bei dem die Position stehen bleibt und der Zufallszahlengenerator immer "0" ausgibt. Durch c > 0 wird dies ausgeschlossen, weil das Programm dazu gezwungen wird, zumindestens eine Stelle nach rechts zu gehen. Gruß Daniel // Edit: Java Code entfernt, da es den Post sprengt. // Edit: Zahl e auch untersucht |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
