Wie programmiert man zufall?

[3d]

ich habe leider keine ahnung vom programmieren.
könnte mir jemand "einfach" erklären wie man zufall programmiert?
bitte möglichst nicht so technisch, außer es geht nicht anderes.

[Bucko]

http://www.galileocomputing.de/openbook/javainsel4/javainsel_05_003.htm
Punkt 5.4 "Die Random-Klasse"

Es gibt eigentlich immer schon eine implementierte Funktion für Zufall, ich denke kaum einer programmiert sich das selbst.

[RaumKraehe]

aber irgend jemand muss sich die Funktion ja mal ausgedacht haben. Welche Faktoren fließen da in den Zufall mit ein?

[Inquisitor]

AFAIK bedient man sich dabei der internen Rechneruhr. Damit hast Du schon zufällige (zeitabhängige) Zahlen...

[peecee]

Soweit ich weiss gibts eigentlich keine wirkliche Zufalls Funktion.


#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
int i;
int maxi = 10;

for(i = 1; i <= maxi; ++i) {
printf("%d. Zufallszahl = %d\n", i, rand());
}

system("PAUSE");
return 0;
}


Dieses Programm gibt immer dieselben Pseudo Zufallszahlen aus. Wenn man die Zufalls Funktion allerdings mit der Uhrzeit initialisiert gibts schon ganz gute Zufallszahlen.

[Trap]

Ohne Hardware die als Zufallszahlengenerator genutzt wird kann man nur Pseudozufallszahlen erzeugen.

Pseudozufallszahlen sind Zahlen die zufällig wirken es aber nicht sind. Es gibt sehr viele verschiedene Verfahren zu messen wie zufällig etwas ist, und sehr viele verschiedene Algorithmen die unterschiedlich gut in unterschiedlichen Messungen abschneiden.

Grundsätzlich hat ein Zufallszahlengenerator einen Zustand und wechselt bei jeder entnommenen Zahl den Zustand. Woraus der Zustand besteht und wie er wechselt ist algorithmenspezifisch.

[HellHorse]

einfach von /dev/random lesen :)

[RaumKraehe]

aber der genaue Menchanismus der dahinter steht ist doch das interessante. :|

[Gast]

linearer Kongruenzgenerator mit richtiger Wahl der Parameter für maximale Periodenlänge
Blum-Blum-Shub

[RaumKraehe]

cool, und nun nochmal für den 0815-Technikbegeisterten. :|

[RaumKraehe]

da :)

http://www2.users.fh-sbg.ac.at/~entacher/zufall/Zufall.htm

Edit: Das ebenen Experiment hatte ich mir schon damals für den Spektrum ausgedacht. Aber mir nie erklären können warum ich keine gleichmäßige Verteilung hatte. Ein Programmierfehler also. soso. :)

[maximAL]

cool, und nun nochmal für den 0815-Technikbegeisterten. :|

naja, wo ist denn das verständnisproblem, wenn man die system-uhr nimmt? damit hat man einen sich ständig ändernden wert und mit einem netten algorithmus macht mann da eine "zufalls"-zahl draus.

[RaumKraehe]

Tja hättest du meine Link gelesen dann wüsstest du das eben nicht die System-Uhr genommen wird. :|

Und auch bei deiner Antwort hätte ich mich gefreut den Algorithmus zu sehen. Klar kann ich mir Vorstellen die aktuelle Zeit mit der deklination des Mondes zu verechnen. :rolleyes:

[Trap]

Der in deinem Link beschriebene Algorithmus ist nur einer unter vielen. Um den 1. Wert festzulegen wird auch bei dem verlinkten Algorithmus in fast allen Implementierungen die Systemzeit benutzt.

Ein anderer (pseudo) Zufallszahlengenerator: http://de.wikipedia.org/wiki/Mersenne_Twister

[Senior Sanchez]

Das mit der Uhrzeit das ist wahr, aber sowas kann auch ganz schnell gegen den baum gehen ;)

Inner 8. Klasse war ich inner AG, die sich mit der Simulationssprache microGPSS beschäftigt. Da wurden ständig zufallszahlen erzeugt um eine simulation zu erzeugen und da kam es zum teil kurioserweise vor, das alle (!!!) 8 PCs die selben Zufallszahlen erzeugt hatten. Soviel zum Thema ;)


Afaik gibt es aber son Via Prozessor der irgendwelche elektrischen Werte im Prozessor misst und daraus Zufallszahlen berechnen kann.


Aber wie alle Physik-LKler zumindest wissen, gibt es eh keinen Zufall, höchstens im makroskopischen Sinn ;) (im mikroskopischen, Stichwort: Laplace'scher Dämon)



mfg Senior Sanchez

[maximAL]

Tja hättest du meine Link gelesen dann wüsstest du das eben nicht die System-Uhr genommen wird. :|

stimmt, der war mir jetzt zu lang. aber da gehts doch auch um die lineare kongruenzmethode, oder?
letztendlich wird in der praxis, also sagen wir mal wenn du zb. in C rand() benutzt, trotzdem auf die systemzeit zurückgegriffen. denn auch der tollstes zufallszahlen algorithmus braucht irgendeinen input, und der sollte immer unterschiedlich sein, damit jedesmal eine andere zahl rauskommt.

[RaumKraehe]

Ja, Ok .. aber in dem Fall würde die Uhrzeit wirklich nur als "startwert" gelten. Aus einem Wert könnten "unendliche" viele Zufallszahlen generiert werden. Doch zumindest weiß ich nun aus meinem Link warum das eben so ist. Und so richtig hat das bis her auch niemand beantwortet.

[Bane]

Ich habe noch im Gedächnis, das man mit Hilfe eines Weißes-Rauschen - Generator wirklichen Zufall programmieren kann.

Intel Chipsätze müßten das können bzw. so einen Generator haben (bzw. hatten so etwas mal).

Statistik : in der Wahrscheinlichkeitsrechnung oder Statistik bezeichnet der Name weißes Rauschen einen Prozess von unkorellierten Zufallsvariablen mit Erwartungswert null und konstanter Varianz. Das weiße Rauschen stellt somit den einfachsten stochastischen Prozess dar, jedoch werden viele komplexere Prozesse und Zeitreihen aus solchen konstruiert, etwa der Random Walk oder ARMA-Prozesse. Ein Spezialfall ist hierbei das gaußsche weiße Rauschen, hier sind die Zufallsvariablen normalverteilt.

http://de.wikipedia.org/wiki/Wei%C3%9Fes_Rauschen

[The Hypnotoad]

Ich habe noch im Gedächnis, das man mit Hilfe eines Weißes-Rauschen - Generator wirklichen Zufall programmieren kann.

Intel Chipsätze müßten das können bzw. so einen Generator haben (bzw. hatten so etwas mal).

Ich glaube die aktuellen Via Cpus, haben auch etwas ähnliches eigenbaut - quasi nen Hardware Zufallszahlengenerator- funktioniert glaub ich durch das elektrische Rauschen der Cpu.

edit: wen es genauer interessiert http://www.viatech.com/en/downloads/whitepapers/initiatives/padlock/wp040519padlock.pdf
bzw.
Zitat von der Via Seite:"How to Generate Random Numbers

In general there are three methods for generating random numbers: software, physical sources, and Quantum randomness.

Software
The most common approach to generating random numbers is by using a deterministic algorithm implemented by a computer program. Such deterministic algorithms cannot generate truly random numbers (at best they are predictable and reproducible, and at worst, have bad statistical characteristics). Thus, software generators are usually called pseudo-random or quasi-random generators.

Physical Sources
A second approach to generate random numbers is to use physical phenomena that fall in between software generators and quantum based hardware generators. For example, the Linux operating system has random number generators that use entropy generated by the keyboard, mouse, interrupts, and disk drive behavior as the seed. Microsoft's CryptGenRandom function (part of the Microsoft CryptoAPI) is similar using, for instance, mouse or keyboard timing input, that are then added to both a stored seed and various system data and user data.

While these physical activities may look random, their randomness cannot be proven, and they run the risk of generating poor entropy (or no entropy) if the sampled physical activity is dormant or repetitive. There are several potential security vulnerabilities when using such physical activities. For example, in networked applications such as browsers, the application traffic between a client and server effectively publishes the locations and sequence of the client's mouse-events. Similarly, users may enable "snap-to" options that center the mouse pointer in the center of the button to be pressed and make the click locations predictable. As a result, the entropy from mouse movements in these environments could be far less than an RNG designer expected.

Quantum Mechanism
The only truly random generator is a mechanism that detects quantum behavior at the sub-atomic level. This is because randomness is inherent in the behavior of sub-atomic particles. A quantum based hardware generator is practical, with examples that have been used including...." oder http://www.viatech.com/en/initiatives/padlock/hardware.jsp ;)

[Shink]

Wenn mich nicht alles täuscht, hatten Intel-Mainboardchipsätze mal einen eingebauten HW-Zufallsgenerator. Aber da scheints irgendwelche Probleme gegeben zu haben (beim Messen/Auslesen).

[Gast]

was soll ein mainboardchipsatz mit einem zufallsgenerator?

[mrdigital]

für vernünftige Krytografie braucht man Zufallszahlen...

[RaumKraehe]

Netzwerk-Karten haben glaub ich auch nen HW-Zufalls Generator. Zumindest wenn es kolisionen gibt wird zufällig ausgewürfelt welche der NICs wann wieder senden kann. Oder macht das eher die Firmeware von NICs?

[Gast]

ich habe leider keine ahnung vom programmieren.
könnte mir jemand "einfach" erklären wie man zufall programmiert?
bitte möglichst nicht so technisch, außer es geht nicht anderes.Naja. Bevor man sich daran macht, einen Generator für Zufallszahlen zu programmieren, sollte man erst einmal definieren, was Zufall ist.

Ich versuche es mal stark vereinfacht zu erklären:
Echte Zufallszahlen sind Zahlen, deren Wahrscheinlichkeit, dass sie gezogen werden, genau gleich hoch ist, wie bei jeder anderen Zahl. Wenn du also beispielsweise eine Million Mal einen Würfel wirfst, dann ist die Wahrscheinlichkeit für die Zahlen 1 bis 6 zu erscheinen je 166.667 Mal. Je mehr Würfe du machst, desto genauer wird das Ergebnis.
Dies gilt allerdings nur für gleichmäßig verteile Zufallszahlen. Es gibt nämlich auch noch andere Arten von Zufallszahlen, z.B. normalverteilte. Die werden häufig in statistischen Auswertungen eingesetzt. So kann man eine Bevölkerung ja nicht gleichmäßig verteilen. Denn es gibt logischerweise mehr Menschen in der Lebensmitte als Säuglinge oder Greise.
Es gibt aber ernsthafte Abhandlungen darüber, dass es echte Zufallszahlen gar nicht geben kann, da immer irgendwelche äußere Einflüsse einwirken.

[RaumKraehe]

Die für mich am vernünftigst klingende Methode ist das nutzen des kosmischen Rauschens um Zufalls-Zahlen zu erzeugen. würde bestimmt auch ein sehr gleichmäßiges Bild ergeben. :)

[Trap]

Je nach Definition ist auch
return a=((a+1) % 6)+1; // mit globalem a
ein Zufallsgenerator ...

[Gast]

für vernünftige Krytografie braucht man Zufallszahlen...
... was natürlich falsch ist. Für vernünftige Kryptographie reichen Pseudozufallszahlen komplett aus. Der vom Gast erwähnte BBS Generator ist sogar mathematisch nachweisbar zufällig - also auch nachweisbar kryptografisch sicher. Wer es nicht glauben will wird mit einem - wohl für viele - "kryptischen" Beweis gequält.

-frank

[mrdigital]

... was natürlich falsch ist. Für vernünftige Kryptographie reichen Pseudozufallszahlen komplett aus. Der vom Gast erwähnte BBS Generator ist sogar mathematisch nachweisbar zufällig - also auch nachweisbar kryptografisch sicher. Wer es nicht glauben will wird mit einem - wohl für viele - "kryptischen" Beweis gequält.

-frank
Was ist daran dann bitte falsch? Es mag vielleicht "overkill" sein, aber falsch ist es definitv nicht.
Klar liefert ein guter PRNG hinreichend zufällige Zahlen für die Kryptografie, aber der Teufel ist ein Eichhörnchen, und das Eichhörnchen ist hier die Implementierung. Wie stellt man sicher, dass der PRNG "gut" funktioniert? Er muss jedes mal mit einer anderen Seed gestartet werden und es gibt mehr als ein Programm / Kryptosystem das genau an dieser Stelle versagt hat, weil der Programmierer dachte dass sein eignener Initialisierungsmechanismus zufällig wäre, es dann aber doch nicht ist. Wie kann man also ein wirklich sicheres System machen, dass selbst einen Angriff "überlebt" wenn der Quellcode offenliegt? Man braucht eine echte Zufallsquelle, da führt halt leider kein Weg dran vorbei (ich habe sowas für ein embedded System geschrieben, auf Basis eines A/D Wandlers). Wenn man also keine HW Zufallsgeneratoren braucht, wieso werden sie dann mittlerweile überall integriert?

[Gast]

Der vom Gast erwähnte BBS Generator ist sogar mathematisch nachweisbar zufällig - also auch nachweisbar kryptografisch sicher. Wer es nicht glauben will wird mit einem - wohl für viele - "kryptischen" Beweis gequält.Kannst du einen Link mit dem Beweis oder einen Artikel/ein Buch angeben? Ist er genau dann "nachweisbar zufällig", wenn die Faktorisierung des Modulus nicht bekannt ist?

[Kladderadatsch]

ist das von programmiersprache zu programmiersprache unterschiedich?

was passiert den in delphi, wenn man
" randomize;
x:= random (50); "
rechnen lässt?
werden die zahlen zwischen 1 und 50 dann durch die systemuhr gewürfelt?

[del_4901]

stimmt, der war mir jetzt zu lang. aber da gehts doch auch um die lineare kongruenzmethode, oder?
letztendlich wird in der praxis, also sagen wir mal wenn du zb. in C rand() benutzt, trotzdem auf die systemzeit zurückgegriffen. denn auch der tollstes zufallszahlen algorithmus braucht irgendeinen input, und der sollte immer unterschiedlich sein, damit jedesmal eine andere zahl rauskommt.


die Folge von Rand wird mit einem Startwert aus der Uhr gestartet (srand()).
rand() selber funzt ohne. ich kann srand mit jeder belibiger Zahl iniziallisieren, nimmt man dafür die Uhr hat man einen schoen Nichtdeterminismus.

[del_4901]

ist das von programmiersprache zu programmiersprache unterschiedich?

was passiert den in delphi, wenn man
" randomize;
x:= random (50); "
rechnen lässt?
werden die zahlen zwischen 1 und 50 dann durch die systemuhr gewürfelt?

Vergesst die Systemuhr, die braucht man nur einmal ganz am Anfang(oder auch nicht).

random 50 spuckt was zw. 0 und 50 aus.

[Trap]

was passiert den in delphi, wenn man
" randomize;
x:= random (50); "
rechnen lässt?
werden die zahlen zwischen 1 und 50 dann durch die systemuhr gewürfelt?
randomize hat ziemlich sicher was mit der Systemzeit zu tun, aber random hat nichts mit der Systemzeit zu tun.
Was genau passiert ist wahrscheinlich abhängig davon welche Delphi-Implementierung man benutzt.

[Gast]

Was ist daran dann bitte falsch? Es mag vielleicht "overkill" sein, aber falsch ist es definitv nicht.
Klar liefert ein guter PRNG hinreichend zufällige Zahlen für die Kryptografie, aber der Teufel ist ein Eichhörnchen, und das Eichhörnchen ist hier die Implementierung. Wie stellt man sicher, dass der PRNG "gut" funktioniert? Er muss jedes mal mit einer anderen Seed gestartet werden und es gibt mehr als ein Programm / Kryptosystem das genau an dieser Stelle versagt hat, weil der Programmierer dachte dass sein eignener Initialisierungsmechanismus zufällig wäre, es dann aber doch nicht ist. Wie kann man also ein wirklich sicheres System machen, dass selbst einen Angriff "überlebt" wenn der Quellcode offenliegt?
Wer Pseudozufallsgeneratoren wie den BBS- oder RSA Generator mit Spielzeugzahlen füttert und sich nicht an die gegebenen Empfehlungen hält, ist selber Schuld, wenn am Ende nichts heraus kommt.

Letztendlich was willst du? Beide sind kryptografisch "provable" sicher. Klar ist die Defintion von "provable security" ist eine andere als "unconditional security". Aber das ganze ist doch hinreichend gut, um auf echte Zufallszahlen zu verzichten.



Man braucht eine echte Zufallsquelle, da führt halt leider kein Weg dran vorbei (ich habe sowas für ein embedded System geschrieben, auf Basis eines A/D Wandlers). Wenn man also keine HW Zufallsgeneratoren braucht, wieso werden sie dann mittlerweile überall integriert?Eine echte Zufallsquelle ist beleibe nicht schlecht und natürlich sinnvolles Beiwerk - einfach aus dem Grund, dass man sich dann keine Mühe mehr mit der Mathematik machen muss. Ansonsten würde ich das nicht überbewerten.

Für das One-Time Pad (welches ja wohl den Hauptnutzen bei der ganzen Kryptogeschichte hier zieht) würde ich sofort bedenkenlos den BBS einsetzen. Wer dann (Pseudo)Zufallsfolgen doppelt verwendet (wie es die Russen damals gemacht haben), ist selbst schuld, wenn die sichersten Systeme versagen. Du hast Recht mit: "der Teufel ist ein Eichhörnchen". Aber das kann dir an jeder Ecke drohen. Wer Empfehlungen dabei missachtet, ist wie erwähnt selber schuld.


Kannst du einen Link mit dem Beweis oder einen Artikel/ein Buch angeben? Ist er genau dann "nachweisbar zufällig", wenn die Faktorisierung des Modulus nicht bekannt ist?
Ich kann dir weder Link nich Buch/Artikel angeben, da das ganze Bestandteil einer meiner Mathediplomprüfungen war und mein Wissen quasi aus einem Jahr Vorlesung gezehrt wird. Aber google doch einfach mal nach NextBitTest und BBS. Irgendwo wird es da schon was geben. Ansonsten Email an: http://www.forum-3dcenter.de/vbulletin/member.php?u=166

-f

[Gast]

Ich kann dir weder Link nich Buch/Artikel angeben, da das ganze Bestandteil einer meiner Mathediplomprüfungen war und mein Wissen quasi aus einem Jahr Vorlesung gezehrt wird. Aber google doch einfach mal nach NextBitTest und BBS. Irgendwo wird es da schon was geben.
http://www.win.tue.nl/~henkvt/boneh-bbs.pdf Du beziehst dich also auf den Beweis in [VV84]?

[mrdigital]

das ist nicht mein Quote, der letzte Teil frank! ;)