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

Hallo,

wie könnte ein Computer richtige Zufallszahlen erzeuegn?

Die Sachen aus den Standardbibliotheken, srand oder rand oder wie auch immer, sind ziemlich schlecht.

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

Wenn ich einen Laplace-Würfel werfe, dann kommen da viele Faktoren zusammen:
- Temperatur der Umgebung
- Höhe des Abwurfes
- Geschwindigkeit, mit der der Würfel geworfen wurde
- Temperatur meiner Hand
- Luftfeuchtigkeit
- Konsistenz der Fläche, auf der der Würfel aufschlägt
usw.

Das alles hat der Computer nicht, er kann nur rechnen, also Zufallszahlen berechen, was aber dann Pseudozufallszahlen sind.

Ich verstehe nicht ganz, wie die "sichereren" (Pseudo-)Zufallsgeneratoren, z.b. Marsenne-Twister, funktioniert.

Der Computer kann einfach nicht genügend Kausalität erzeugen.

Wie wäre es, wenn man spezielle Hardware baut, die diese Kausalität erzeugen kann.

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

Was haltet ihr davon?

Nathan

Es gibt bereits Generatoren, die echte Zufallszahlen erzeugen.
Seit C++11 sind sie auch in der Standardbibliothek.

SeppJ

Lies bitte erst einmal Wikipedia. Du scheinst die Hälfte der Hauptwörter in deinem eigenem Beitrag (besonders Kausalität^*, Mersenne-Twister⁺, Laplacewürfel^# und Zufall^@) nicht (oder falsch) zu verstehen.

Weiterhin ist längst alles erfunden, was man braucht, um am Computer mit Zufallszahlen glücklich zu werden:
-einfache PRNGs
-PRNGs für wissenschaftliche Ansprüche
-PRNGs für kryptografische Ansprüche
-Echtzufallszahlen. Lange nur in relativ kleinen Mengen als Seed für PRNGs, neuerdings auch schnell und unbegrenzt.

Was will man mehr?

Informiere dich über diese Techniken und wie sie funktionieren. Wenn du konkrete Fragen hast, frag.

^*: Falsches Wort. Vermutlich ist Entropie gemeint.
⁺: Kein "sicherer" Generator im Sinne von Kryptografie
^#: Kein echter Würfel, sondern ein idealisiertes Modell
^@: Muss ich das wirklich noch erläutern?

Nathan schrieb:

Es gibt bereits Generatoren, die echte Zufallszahlen erzeugen.
Seit C++11 sind sie auch in der Standardbibliothek.

Das glaube ich nicht.

Computer können überhaupt keine richtigen Zufallszahlen erzeugen.

Wahrscheinlich sowas wie rand() in c.

SeppJ

glaub ich nicht schrieb:

Nathan schrieb:

Es gibt bereits Generatoren, die echte Zufallszahlen erzeugen.
Seit C++11 sind sie auch in der Standardbibliothek.

Das glaube ich nicht.

Computer können überhaupt keine richtigen Zufallszahlen erzeugen.

Wahrscheinlich sowas wie rand() in c.

Also ein Troll. Schade, da hätte ich mir die ernste Antwort oben auch sparen können.

[/thread]

Ich hatte die Antwort schon geschrieben und deine nicht gelesen.

Aha, du willst also Zufallszahlen auf Basis eines Seeds erzeugen?

Wie erzeugst du den Seed?

Am Ende hast du eh wieder das übliche deterministische Zeugs.

Edit:

Ok, das ist im Grunde genauso, wie ich mir das vorgestellt hatte.

Diese "Pseudozufallszahlengeneratoren" arbeiten alle mit Seeds.

Diese Seeds könnten sich als Schwachstelle herausstellen, vor allem wenn der gleiche Seed das gleiche Ergebnis gibt.

vario-500

http://software.intel.com/en-us/articles/intel-digital-random-number-generator-drng-software-implementation-guide punkt 3.2.1

vario-500 schrieb:

http://software.intel.com/en-us/articles/intel-digital-random-number-generator-drng-software-implementation-guide punkt 3.2.1

Ok, das ist mal eine Aussage. Diese Seeds werden über asynchron geschaltete Stromkreisläufe erzeugt.

Im Grunde sollte der eigentliche Algorithmus, mit dem die Zufallszahlen erzeugt werden, egal sein.

Solange die Seeds zufällig und nicht-deterministisch erzeugt werden, sollten die meisten Algorithmen gut arbeiten.

Gregor

srand - edit schrieb:

Diese Seeds könnten sich als Schwachstelle herausstellen, vor allem wenn der gleiche Seed das gleiche Ergebnis gibt.

Was heisst denn Schwachstelle? Was genau willst Du mit Deinen Zufallszahlen machen. "Reproduzierbare Zufallszahlen" sind fuer diverse Anwendungen durchaus wichtig. Stell Dir vor, Du schreibst eine Simulation, die vom Zufall abaengt. Dann willst Du Simulationslaeufe reproduzieren koennen.

Um was fuer ein Anwendungsgebiet geht es also?

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.

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.