G
srand schrieb:
Um was fuer ein Anwendungsgebiet geht es also?
Naja, um universelle Einsatzbereiche, z.b. in der Kryptographie.
Die Frage, ob "echte Zufallszahlen" fundamental etwas anderes sind als "Pseudozufallszahlen" ist theoretisch nicht geklaert. Diese Frage tritt zum Beispiel im Rahmen der Komplexitaetstheorie auf.
Wenn ich einen Seed habe, und so auf einem Blatt Papier berechnen kann, welche "Zufallszahl" am Ende rauskommt, dann kann das kein besonders guter Algorithmus sein.
Warum "Komplexitaetstheorie"? Das Problem mit dem (In-)Determinismus, auf das sich das Problem hier stützt, gibt es seit der Antike und ist eher ein philosophisches Problem.
Gleiche Ursache führt zur gleichen Wirkung.
Gleicher Seed führt zur gleicher "Zufallszahl".
Das ist Determinismus.
Sowas kann man in der Kryptographie nicht brauchen, denke ich.
1. Auch wernn es nicht direkt angesprochen wurde: Kryptographie hat eine ganze Menge mit Komplexitätstheorie zu tun. Du willst etwas so kodieren, dass die Kodierung und Dekodierung mit Schlüssel effizient zu machen ist, die Dekodierung ohne Schlüssel aber einen enormen Arbeitsaufwand erfordert. Wenn Du derartiges nicht gewährleisten kannst, dann musst Du dafür sorgen, dass das Verschlüsselungsverfahren insgesamt geheim bleibt. Das ist in der Geschichte aber schon sehr oft schief gegangen.
2. Man kann einen Text praktisch perfekt verschlüsseln, wenn man einen hinreichend zufällig konstruierten Schlüssel nimmt, der mindestens die gleiche Länge wie der Text hat. So etwas nennt man ein One-Time-Pad. Das Problem eines One-Time-Pads ist allerdings, dass man den Schlüssel auch irgendwie an den Empfänger der Nachricht übermitteln muss. Und wenn irgendwelche Leute die Nachricht abfangen können, dann können sie auch den Schlüssel abfangen. Um so ein One-Time-Pad zu konstruieren, könntest Du natürlich "echte Zufallszahlen" nutzen.
3. Was man aber eigentlich haben will sind kurze Schlüssel, weil man die einfacher sicher austauschen kann.
4. Es gibt in der Komplexitätstheorie das Konzept einer One-Way function. Das sind Funktionen, die man effizient berechnen kann, deren inverses aber nicht effizient berechnet werden kann. Es ist ungeklärt, ob es One-Way functions gibt und diese Frage hängt stark mit dem Problem zusammen, ob die Komplexitätsklassen P und NP identisch sind. Wenn es One-Way functions gibt, dann impliziert das, dass diese beiden Komplexitätsklassen nicht identisch sind.
5. Man kann zeigen, dass wenn es One-Way functions gibt, dass man mit diesen dann aus einem kurzen Schlüssel eine beliebig lange Sequenz an "Pseudozufallszahlen" generieren kann, die aus Sicht der Komplexitätstheorie nicht effizient von einem sicheren One-Time Pad unterscheidbar sind (Hardcore-Link hierzu). Im Prinzip kann man also zeigen, dass unter dieser Annahme in diesem Zusammenhang Pseudozufallszahlen genauso "mächtig" wie echte Zufallszahlen sind. Mit diesem aus dem kurzen Schlüssel generierten längeren Schlüssel kann man dann einen Text sicher verschlüsseln.
6. AFAIK stützt sich die moderne Kryptographie sehr auf die Annahme, dass es One-Way functions gibt. Wenn irgendwer zeigt, dass das nicht so ist, dann könnten alle Verschlüsselungsverfahren schnell wertlos werden.
7. "Zufall" tritt noch an vielen weiteren Stellen innerhalb der Komplexitätstheorie auf. Zum Beispiel gibt es die Komplexitätsklasse ZPP für Problemstellungen, die mit Turingmaschinen, die Zufall ausnutzen können, effizient entschieden werden können. Auch hier ist natürlich in keinster Weise klar, ob diese Klasse echt größer als die Komplexitätsklasse P ist.
Die Komplexitätstheorie macht also einige Aussagen dazu, ob man "echten Zufall" von "gut gemachtem Pseudozufall" (effizient) unterscheiden kann. Wenn man im Rahmen seiner Möglichkeiten aber keinen Unterschied zwischen beiden feststellen kann, warum braucht man dann "echten Zufall"?