Wie könnte ein Computer -richtige- Zufallszahlen erzeugen?

knivil schrieb:

int zufall(int seed) 
{ 
     return (wuerfeln(void) * seed); 
}
Wozu brauchst du hier einen seed?

Stimmt auch wieder.

Verbesserte Version:

int zufall(int AnzahlDerWuerfelseiten)
{
     return (wuerfeln(AnzahlDerWuerfelseiten));
}

knivil schrieb:

Das ist ja mal die Erkenntnis schlechthin.

Ja. Die leute von der c-stdlib haben das anscheinend nicht erkannt.

knivil

Sie schreiben dir nicht vor, welchen seed du benutzt und wie er gewonnen wird.

Ja. Die leute von der c-stdlib haben das anscheinend nicht erkannt.

Und du hast nicht erkannt, warum die Dinge so sind, wie sie sind.

knivil schrieb:

Sie schreiben dir nicht vor, welchen seed du benutzt und wie er gewonnen wird.

Ja. Die leute von der c-stdlib haben das anscheinend nicht erkannt.

Und du hast nicht erkannt, warum die Dinge so sind, wie sie sind.

Naja, ich muss es irgendwie schaffen, einen halbwegs ordentlichen seed zur laufzeit zu erzeugen.

entweder der seed, oder der algorithmus muss indeterministisch sein.

für den seed kämen also nur so triviale sachen wie uhrzeit, anzahl der laufenden prozesse, mausbewegungen usw. infrage.

Warum sind denn die Dinge so wie sie sind?
Richtig, weil ein Computer ohne Extra-Hardware keine ordentlichen Seeds erzeugen kann.
Ergo: Computer können ohne spezielle Hardware keine Zufallszahlen erzeugen.
Ergo: die vermutung meines eingangsposts ist im kern richtig.

cooky451

Lustig, dass SeppJs "Fakten" sich über drei Seiten gehalten haben.

vario-500

srand schrieb:

Warum sind denn die Dinge so wie sie sind?
Richtig, weil ein Computer ohne Extra-Hardware keine ordentlichen Seeds erzeugen kann.
Ergo: Computer können ohne spezielle Hardware keine Zufallszahlen erzeugen.
Ergo: die vermutung meines eingangsposts ist im kern richtig.

du willst es auch nicht wahrhaben, dass man keine extra-hardware heutzutage mehr braucht, oder ? hier noch ein link, extra für dich http://spectrum.ieee.org/computing/hardware/behind-intels-new-randomnumber-generator/0 sogar mit geschichte
wenn du sogar im besitz eines neueren intel prozessors sein solltest, kannst du es ja sogar benutzen, so, wie es hier beschrieben wird http://software.intel.com/sites/default/files/m/f/f/4/7/7/37157-BullMountainGuide-20110619.pdf

knivil

Ergo: die vermutung meines eingangsposts ist im kern richtig.

Also du meinst beispielsweise diese hier?

Um richtige Zufallszahlen zu erzeugen, braucht man genügend Kausalität.

Aber auf deinen Eingangspost genauer einzugehen:

Beispielsweise könnte man viele kleine Kügelchen, die alle einen bestimmten Wert haben, nach dem "Lotto-Prinzip" ziehen.

Was haltet ihr davon?

Nix! Angenommen ich habe ein Device D was unabhaengig und gleichverteilt mir Zufallszahlen aus {1,2,3} liefert. Ich kann D leider nicht benutzen, um auch unabhaengige Zufallszahlen aus {1,2,3,4,5} zu ziehen, ohne Ziehungen zu wiederholen. D.h. es ist wahrscheinlich nicht performant.

knivil schrieb:

Ergo: die vermutung meines eingangsposts ist im kern richtig.

Also du meinst beispielsweise diese hier?

Um richtige Zufallszahlen zu erzeugen, braucht man genügend Kausalität.

Nein. Meine Kernvermutung war, dass man spezielle Hardware braucht, um richtige Zufallszahlen zu erzeugen.

Und? Dann hab ich halt diese Begriffe falsch verwendet. Du bist doch nicht so kleinkariert, oder?

cooky451

Also deine Vermutung war, dass eine Turingmaschine nur Dinge berechnen kann? Wahnsinn, wer hätte das gedacht.

cooky451 schrieb:

Also deine Vermutung war, dass eine Turingmaschine nur Dinge berechnen kann? Wahnsinn, wer hätte das gedacht.

Von der Turingmaschine hab ich nix gesagt.

P.s.: Komisch, ich hab doch im Firefox "Cookies ablehnen" eingestellt

knivil

Nun, die CPU ist so das deterministische was ich kenne, anderfalls waere ihr Nutzen auch sehr beschraenkt. Waehrend Turingmaschine eine etwas theoretische Rechenmaschine ist, so ist die praktische Umsetzung in Form von CPU + RAM zu finden.

Schließe einfach ein Geigermüllerzählrohr an den Computer an, dann hat du einen echten Zufallsgenerator.

oder Rauschgenerator

großbuchstaben schrieb:

oder Rauschgenerator

gibts ja schon unter linux (/dev/random)

SeppJ

/dev/random schrieb:

großbuchstaben schrieb:

oder Rauschgenerator

gibts ja schon unter linux (/dev/random)

/dev/random ist kein Rauschgenerator, das sammelt bloß Entropie aus verschiedenen Quellen, die jedoch in der Regel keine speziellen Hardwarezufallsgeneratoren sind (weil diese erst recht neu sind). Laut Manpage gehören zu den Hauptquellen der zeitliche Abstand zwischen Tastaturereignissen und die zeitliche Abfolge von Interrupts. Daher kann /dev/random nicht als Dauerquelle großer Mengen echter Zufallszahlen dienen, da es eben eine Weile dauert, bis sich genügend Entropie angesammelt hat.

Klassischer Test:

cat /dev/random

Das leert den gegenwärtigen Pool und wartet dann auf neue Ereignisse. Bewegt man die Maus oder tippt ein bisschen auf der Tastatur, so bekommt man nach einer Weile einen Schub weiterer Zufallszahlen (in Form wilder Zeichenfolgen).

Gregor

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"?