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

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.

cooky451

SeppJ hat eigentlich alles geschrieben was es dazu zu schreiben gibt..

srand schrieb:

Sowas kann man in der Kryptographie nicht brauchen, denke ich.

Autsch. http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator

cooky451 schrieb:

SeppJ hat eigentlich alles geschrieben was es dazu zu schreiben gibt..

srand schrieb:

Sowas kann man in der Kryptographie nicht brauchen, denke ich.

Autsch. http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator

Mal ein Beispiel.
Hier mal ein perfekter, indeterministischer Zufallszahlengenerator:

int zufall(int seed)
{
     return (wuerfeln(void) * seed);
}

diese funktion, so trivial sie doch ist, ist perfekt.

Sie liefert vom Seed unabhängige, also indeterministische, Werte.
Ein Traum jedes Kryptographen oder Mathematikers.

knivil

1.) Die meisten Prozessoren haben ein echtes Zufallsdevice.
2.) Schliesse eine digitale Camera an und miss das thermische Rauschen. Gab mal einen Artikel in der c't.

int zufall(int seed) 
{ 
     return (wuerfeln(void) * seed); 
}

Wozu brauchst du hier einen seed?

cooky451

Oder auch so.

knivil schrieb:

1.) Die meisten Prozessoren haben ein echtes Zufallsdevice.
2.) Schliesse eine digitale Camera an und miss das thermische Rauschen. Gab mal einen Artikel in der c't.

Ja, aber das ist alles spezielle Hardware.

"echtes Zufallsdevice", das ist wahrscheinlich auch irgendso ein asynchroner Stromkreis, was? Das ist im Prinzip das gleiche.

Ich glaube aber nicht, dass rand() aus der stdlib sowas benutzt.

cooky451 schrieb:

Oder auch so.

Jaein. In meinem Beispiel wird immer neu gewürfelt, so werden inteterministische Werte erzeugt.

Im Grunde wird doch das hier besprochen, was ich mir schon erschlossen hatte: man braucht ein inteterministisches Medium, um echte Zufallszahlen zu erzeugen.

knivil

Ich glaube

Ach darum geht es ...

man braucht ein inteterministisches Medium, um echte Zufallszahlen zu erzeugen

Das ist ja mal die Erkenntnis schlechthin.

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.