PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Zufallszahlengenerator - Wahrscheinlichkeitstheorie


Corrail
2004-07-02, 12:59:37
Hello!

Ich brauche einen Zufallszahlengenerator für C++ den ich einstellen kann. Und zwar hätte ich gerne konkret eine Normalverteilung oder Beta/Gammaverteilung wo ich Mittelwert und Varianz einstellen kann. Ich kenne nur die rand() Funktion von C++, aber welche Verteilung hat die? Gleichverteilung?
Wenn es sowas nicht gibt so hab ich mir überlegt das ganze selbst zu schreiben indem ich über eine Zufallsgröße abhängig von der Zeit gehe (z.B. Zeit in ms von Programmbeginn modulu 17 oder so). Das sollte dann eigentlich eine diskrete Gleichverteilung ergeben. Frage ist nur wie transformiere ich die in eine Normalverteilung bzw. Beta/Gammaverteilung?

Vielen Dank!

Xmas
2004-07-02, 13:42:45
rand() ist diskret Gleichverteilt von 0 bis RAND_MAX.

Normalverteilung:
n = s * sqrt(-2 * ln(rnd())) * sin(2 * Pi * rnd()) + m;

wobei rnd() eine gleichverteilte Zufallszahl zwischen 0 und 1 liefern sollte, also ((float)rand())/(RAND_MAX + 1)

Corrail
2004-07-02, 13:51:18
Vielen Dank!
s ist dann die Varianz und m der Mittelwert, oder?
Und müssen die 2 Zufallszahlen, die durch rnd() bestimmt sind gleich sein oder sind das zwei verschiedene?

D-Swat
2004-07-02, 18:13:34
Vielleicht ist das hier (http://www.boost.org/libs/random/index.html) noch nützlich.

mrdigital
2004-07-02, 20:12:37
Zu diesem Thema soll ich eine Studienarbeit schreiben ;)
Ich dachte mir als Ansatz das Rauschen eines A/D Wandlers zu verwenden, das niederwertigste Bit "flattert" eigentlich immer ganz schön hin und her. Wenn du also eine Soundkarte hast, dann kannst du das als Zufallsquelle nehmen.

Xmas
2004-07-02, 22:46:42
Original geschrieben von Corrail
Vielen Dank!
s ist dann die Varianz und m der Mittelwert, oder?
Und müssen die 2 Zufallszahlen, die durch rnd() bestimmt sind gleich sein oder sind das zwei verschiedene?
Zwei verschiedene.

Gast
2004-07-04, 21:13:27
Original geschrieben von mrdigital
Zu diesem Thema soll ich eine Studienarbeit schreiben ;)
Ich dachte mir als Ansatz das Rauschen eines A/D Wandlers zu verwenden, das niederwertigste Bit "flattert" eigentlich immer ganz schön hin und her. Wenn du also eine Soundkarte hast, dann kannst du das als Zufallsquelle nehmen. Da echte Zufallszahlen mit den heutigen System afaik unmöglich erzeugt werden können, wäre der Ansatz mit dem A/D-Wander sicher eine gute Idee.

Weitere Möglichkeiten die mir noch so einfallen:
-Tastendrücke
-Mausbewegungen
-Sektornummer und Zugriffszeit von Festplattenoperation
-Aktuelle Mausposition
-Inhalt des angezeigten Bildschirms
-Inhalt von Fat
-CPU-Auslastung
-Ankunftszeit von Netzpaketen

mrdigital
2004-07-05, 10:27:26
Original geschrieben von Gast
Da echte Zufallszahlen mit den heutigen System afaik unmöglich erzeugt werden können, wäre der Ansatz mit dem A/D-Wander sicher eine gute Idee.

Weitere Möglichkeiten die mir noch so einfallen:
-Tastendrücke
-Mausbewegungen
-Sektornummer und Zugriffszeit von Festplattenoperation
-Aktuelle Mausposition
-Inhalt des angezeigten Bildschirms
-Inhalt von Fat
-CPU-Auslastung
-Ankunftszeit von Netzpaketen
Diese Sachen kann man teilweise als Zufallsquelle einsetzten, allerdings muss man da oft noch Randbedingungen beachten.
- Bei der Tastatur hat man das Problem, dass nicht alle Tasten gleichverteilt sind, d.h. die Tasten, die unter den Fingern liegen, werden auch häufiger gedrückt, damit hat man schon keinen so schönen Zufall mehr.
- Mausbewegungen verhalten sich ähnlich wie die Tastatur (leider), ausser man verlangt vom User gezielt, dass er in einem vorbestimmten Feld rumrutscht.
- Sektornummern und Zugriffszeiten sind nicht so schlecht, da die sich mit den Randbedingungen ständig verändern und vor allem sind sie nicht so leicht (vorhersagbar) zu manipulieren.
- Bildschirminhalte sind ok, aber auch wieder gefährlich, weil der sehr leicht manipulierbar ist.
- Die FAT ist wieder nicht gut, weil sie selbst ein bestimmtes Aufbaumuster hat, und sich das auch in den Zufallszahlen widerspeigeln würde, zudem verändert sich die FAT nicht, das heisst, der Inhalt der FAT ist nur einmal zufällig ;)
- CPU-Auslastung ist solala, sie ist auch wieder leicht manipulierbar.
- Die Ankunftszeit von Netzwerkpaketen ist wieder gut, das kann man wirklich nicht vorhersagen, bzw. die Manipulation wäre äusserst schwer.

Mit Manipulierbar meine ich, dass ein Angreifer, der weiss, dass ich Zufallszahlen für bestimme Operationen benötige und der auch weiss, wie ich diese gewinne, versuchen könnte, diesen Zufall einzuschränken, d.h. den Wertebereich zu reduzieren, damit beispielsweise eine anschliessende Brute Force Attacke nur einen kleineren Zahlenraum durcharbeiten muss (wenn man mit den Zufallszahlen Schlüssel für krypto Operationen gewinnen möchte ;))

Muh-sagt-die-Kuh
2004-07-05, 13:00:36
Systemevents wie IRQs, Syscall oder Netzwerkpakete sind prinzipiell ein ganz gutes Mittel zur Erzeugung von Zufallszahlen, das Problem ist eigentlich nur, dass man einen begrenzten Pool an Zufallsereignissen hat.....deshalb ist man eigentlich immer zusätzlich auf einen guten Pseudozufallszahlengenerator angewiesen, dem man einen echten Zufallswert als Initialisierungsvektor geben sollte.

Linux verwendet das oben vorgestellte Konzept zur Erzeugung von Zufallszahlen im Kernel. Das random device liefert echte Zufallszahlen und blockt falls der Entropiepool leer ist, urandom liefert im Zweifelsfalle Pseudozufallszahlen.

Xmas
2004-07-05, 15:58:59
Was ist denn eigentlich aus dem Intel Random Number Generator geworden? Gibt es eine einfache Library die den nutzt?

Vedek Bareil
2004-07-06, 00:27:27
Mal ein bißchen Theorie zum Thema Transformation zwischen Wahrscheinlichkeitsverteilungen :)

Nimm an du hast eine (z.B. Gleich-)Verteilung w(x) auf einer Menge X und eine Funktion y(x). Und du willst jetzt die Verteilung w(y) für die Funktionswerte y bestimmen.
Dazu kannst du ausnutzen, daß die Wahrscheinlichkeit dafür, daß x in einem infitesimal kleinen Intervall dx liegt, durch w(x) dx gegeben ist und zudem gleich der Wahrscheinlichkeit dafür ist, daß der Funktionswert y im entsprechenden Intervall dy = y(x+dx)-y(x) liegt. Daraus folgt

w(x) dx = w(y) dy (1)

was sich zu

w(y) = w(x) dx/dy = w(x(y)) x'(y)

umstellen läßt.

Dein Problem ist jetzt aber genau umgekehrt, du hast zwei Verteilungen w(x) und w(y) und suchst die Funktion y(x). Dazu könntest du (1) umstellen zu

dy/dx = w(x)/w(y) (2)

um dann einfach nach x zu integrieren:

y(x) = int dy/dx dx = int w(x)/w(y(x)) dx

Dummerweise tritt aber y im Integranden auf und muß dort als Funktion von x behandelt werden. Und weil du die Funktion y(x) natürlich nicht kennst, sondern erst ermitteln willst, kannst du das Integral nicht lösen.
Man kann aber anders vorgehen und (1) statt zu (2) zu

dx/dy = w(y)/w(x)

umstellen und durch Integration nach y die Umkehrfunktion x(y) bestimmen:

x(y) = int dx/dy dy = int w(y)/w(x(y)) dy

Auf den ersten Blick hat das nicht viel gebracht, da jetzt x(y) im Integranden steht. Aber: w(x) ist ja eine Gleichverteilung, und damit konstant, w(x)=c. Damit wird

x(y) = int w(y)/c dy (3)

Durch Bilden der Umkehrfunktion erhälst du dann y(x).

Mit der Beta- und Gamma-Verteilung kenn ich mich nicht so aus, die Normalverteilung ist glaube ich die Gaußverteilung(?). Bei der kommt jedoch das Problem hinzu, daß da y^2 im Exponenten steht, womit das Integral (3) nicht analytisch gelöst werden kann.
AFAIK gibt's da ne andere Möglichkeit, an die Funktion y(x) zu kommen, ich weiß die nur nicht :D

Vedek Bareil
2004-07-06, 01:58:17
Ich hab hier noch was gefunden:
http://matheboard.de/lexikon/index.php/Normalverteilung (bis "Berechnung von normalverteilten Zufallsvariablen" runterscrollen)

Die Formel von XMas entspricht der Methode von Box-Muller. Diese hat allerdings den Nachteil, daß eine sqrt-, eine log- und eine sin- bzw. cos-Funktion ausgewertet werden muß. Daneben gibt es die Methode von Marsaglia, die neben einer log-Auswertung nur mit Grundrechenarten auskommt und daher performancemäßig günstiger ist.

Beide Methoden umgehen offenbar das Problem mit der Integration von exp(-y^2), indem sie statt von einer Gleichverteilung w(x) auf einer eindimensionalen Menge von einer Gleichverteilung w(x1,x2) auf einer zweidimensionalen Menge ausgehen, daher die zwei Zufallsvariablen.
Gleichung (1) wird damit zu

w(x1,x2) dx1 dx2 = w(y) dy

Den Rest überleg ich mir auch noch ;)

Frank
2004-07-06, 09:40:54
Original geschrieben von Muh-sagt-die-Kuh
Systemevents wie IRQs, Syscall oder Netzwerkpakete sind prinzipiell ein ganz gutes Mittel zur Erzeugung von Zufallszahlen, das Problem ist eigentlich nur, dass man einen begrenzten Pool an Zufallsereignissen hat.....deshalb ist man eigentlich immer zusätzlich auf einen guten Pseudozufallszahlengenerator angewiesen, dem man einen echten Zufallswert als Initialisierungsvektor geben sollte.Ein Generator für Pseudozufallszahlen reicht auch vollkommen allein, um ein ordentliches Ergebnis zu bringen. Mit ordentlich meine ich kryptografisch sicher. Im Falle des BBS läßt sich diese "perfekte Sicherheit" sogar beweisen.

Wozu also noch irgendwelche anderen Dinge mit einbringen?

MeLLe
2004-07-06, 11:08:06
Weil sonst immer wieder gleiche Pseudozufallszahlen (der Name ist ja bekanntlich Programm!) erzeugt werden, wenn mit keinem zufälligen Startwert initialisiert wird?

Frank
2004-07-06, 12:41:06
Original geschrieben von MeLLe
Weil sonst immer wieder gleiche Pseudozufallszahlen (der Name ist ja bekanntlich Programm!) erzeugt werden, wenn mit keinem zufälligen Startwert initialisiert wird? Selbst wenn. Wenn beim BBS sich die Zufallszahlen irgendwann wiederholen hantiert man mit Spielzeugbeispielen. In der Praxis wird der mit Parametern gefüttert, wo das Wort Wiederholung keine Rolle spielt.

mrdigital
2004-07-19, 15:59:25
Wie kann man eine Zahlenfolge darauf untersuchen, ob sie zufällig ist oder nicht?

Vedek Bareil
2004-07-20, 01:20:12
Original geschrieben von mrdigital
Wie kann man eine Zahlenfolge darauf untersuchen, ob sie zufällig ist oder nicht?
dazu gibt es z.B. folgendes Verfahren. Man trägt in einem x-y-Diagramm jeweils das aktuelle Folgenglied u_i gegen dessen Vorgänger u_{i-1} auf. D.h. aus der Folge u_i konstruiert man eine Folge von Punkten

(x_i, y_i) = (u_{i-1}, u_i)

und zeichnet diese in ein 2D-Koordinatensystem ein. Wären die u_i eine Folge von "echten" Zufallszahlen, so dürften in der entstehenden Punktmenge keinerlei Korrelationen vorhanden sein.
Je schwächer daher bei einer Folge von Pseudozufallszahlen die Korrelationen sind, desto "besser" ist die Folge, d.h. desto "echter" ist ihre Zufälligkeit.

Man stelle sich z.B. eine denkbar schlechte Folge vor, bei der einfach jedes Folgenglied gegenüber seinem Vorgänger um eine konsntante Differenz delta_u erhöht ist:

u_i^(verybad) = u_{i-1}^(verybad) + delta_u

Dann würde die Punktmenge (x_i, y_i) einfach eine Gerade bilden und somit hochgradig korreliert sein.

Frank
2004-07-21, 13:06:45
Original geschrieben von mrdigital
Wie kann man eine Zahlenfolge darauf untersuchen, ob sie zufällig ist oder nicht? Dafür gibt es verschiedene Tests:

Die Pseudozufallszahlenfolge darf sich im statistischen Verhalten natürlich nicht von den einer echten Folge unterscheiden. Dafür gibt es zwei Testmethoden: Man testet die Folge selbst auf Zufälligkeit oder man testet auf Möglichkeit der Vorhersagbarkeit. Im ersteren Fall kann man zum Beispiel das machen, was Vedek Bareil angesprochen hat. Man kann aber zum Beispiel auch die Verteilung per Chi^2 Test prüfen. Es gibt aber auch abseits solcher Mathematischen Tests genormte Untersuchungen: zb. der US Behörden Test auf Zufälligkeit: FIPS PUB 140-1. Der dürfte meines Wissens insgesamt 4 Einzeluntersuchungen auf eine 20000bit lange 0/1 Folge haben: zb. Monobit Test und Longruntest. (falls Interess kann ich dazu auch genauer schreiben)

Die andere Sache ist dann halt eine Überprüfung auf Vorhersagbarkeit. Da gibt es den Next-Bit-Test und noch ein äquivalenten für Polynomschieberegister. Der BBS Generator erfüllt ersteren beweisbar. (auch hier: falls Interesse mehr)

ethrandil
2004-07-21, 13:16:52
Also, ich hab an sowas grundsätzlich immer interesse, oh du mein Mathe-Gott :D

Ich brauch das allerdings nicht wirklich... nur Interesse...
erklär mal "Monobit Test und Longruntest" =)

- Eth

Frank
2004-07-21, 14:07:37
Also nach FIPS 140-1 wird eine 20000bit langes Teilstück aus Nullen und Einsen nach folgenden Kritierien geprüft:

1. Monobit Test:
- Anzahl n1 der Einsen muss im Bereich 9654 < n1 < 10364 liegen.
- damit (n1-n2)^2/n < 692^2/20000

2. Poker Test:
- Folge wird in 5000 Blöcke der Länge 4 geteielt
- i ist Binärzahl zwischen 0 und 15
- f(i) ist die Anzahl der auftretenden Blöcke mit der Binärzahl i
- http://rcswww.urz.tu-dresden.de/~fh468638/math/pokertest.gif

3. Runs Test:
- es werden wieder Blöcke untersucht
- http://rcswww.urz.tu-dresden.de/~fh468638/math/runstest.gif
- für die Längen 1, 2, 3, 4, 5 und 6+ gibt es dann einen fest vorgeschriebenen Bereich in der die Anzahl liegen sollte

4. Long Runs Test:
- sagt bloß aus, dass es keine Blöcke Bi und Gi für i>34 gibt.

mrdigital
2004-07-21, 14:12:53
Original geschrieben von Frank
Also nach FIPS 140-1 wird eine 20000bit langes Teilstück aus Nullen und Einsen nach folgenden Kritierien geprüft:

1. Monobit Test:
- Anzahl n1 der Einsen muss im Bereich 9654 < n1 < 10364 liegen.
- damit (n1-n2)^2/n < 692^2/20000

2. Poker Test:
- Folge wird in 5000 Blöcke der Länge 4 geteielt
- i ist Binärzahl zwischen 0 und 15
- f(i) ist die Anzahl der auftretenden Blöcke mit der Binärzahl i
- http://rcswww.urz.tu-dresden.de/~fh468638/math/pokertest.gif

3. Runs Test:
- es werden wieder Blöcke untersucht
- http://rcswww.urz.tu-dresden.de/~fh468638/math/runstest.gif
- für die Längen 1, 2, 3, 4, 5 und 6+ gibt es dann einen fest vorgeschriebenen Bereich in der die Anzahl liegen sollte

4. Long Runs Test:
- sagt bloß aus, dass es keine Blöcke Bi und Gi für i>34 gibt.
:up:
Danke dir! Die genaue Spec zu diesem Test finde ich in FIPS 140-1? Ist die frei zugänglich?

ethrandil
2004-07-21, 14:13:03
Hmm, k, aber alle diese Methoden sind doch eigentlich ziemlich primitiv, oder?

Im Prinzip müsste man doch ne Mustererkennung über die bitfolge machen, und dabei variable Längen zulassen...

Ich weiß das sowas viel länger dauert, und viel schwerer zu beweisen ist, aber...... die oben genannten Tests kann man doch auch mit recht primitiven Methoden schlagen, oder?

- Eth

mrdigital
2004-07-21, 15:21:09
FIPS 140 gibts hier:
http://www.cerberussystems.com/INFOSEC/stds/fip140-1.htm

Frank
2004-07-21, 15:45:50
Original geschrieben von mrdigital
:up:
Danke dir! Die genaue Spec zu diesem Test finde ich in FIPS 140-1? Ist die frei zugänglich? Sowas wie FIPS PUB 140-1 ist immer frei zugänglich, da das offene Standards sind. Zb. steht FIPS 46 für das alte DES Verfahren und FIPS 197 für AES.
Original geschrieben von ethrandil
Hmm, k, aber alle diese Methoden sind doch eigentlich ziemlich primitiv, oder?

Im Prinzip müsste man doch ne Mustererkennung über die bitfolge machen, und dabei variable Längen zulassen...

Ich weiß das sowas viel länger dauert, und viel schwerer zu beweisen ist, aber...... die oben genannten Tests kann man doch auch mit recht primitiven Methoden schlagen, oder?

- Eth Tja was heißt schlagen? Man kann natürlich immer einen Angriff auf eine Zufallszahlenfolge machen, aber letztendlich ist doch die Frage, wofür man das eigentlich braucht. Und wenn man das klassische OneTimePad zur Verschlüsselung nimmt, welches nun gerade solch eine Zufallsfolge zum Kodieren benötigt, dann stell ich mir bei solch bestandenen Zufallszahlentest, dass mehr als schwer vor. Selbst bei einen KnownPlainText Angriff sollte man dann schon fast von vornherein wissen, mit welchem Zufallszahlengenerator (der nun also den FIPS 140 "gerade so" geschafft hat) das dann kodiert wurde. ... hmm :|

Man wird aber eine Folge sowieso nicht nur mit diesen Test prüfen. Die Vorhersagbarkeit spielt ja auch noch mit hinein.

Corrail
2005-02-13, 20:51:30
*maltotengräberspiel*

Ich stehe nun wieder vor dem selben Problem, allerdings müsste ich mit einer diskreten Gleichverteilung (mit rand() ) jetzt eine Gamma-Verteilung erzeugen. Hat dafür wer einen Code?

Vielen Dank!

Trap
2005-02-13, 21:23:23
http://www.gnu.org/software/gsl/manual/gsl-ref_19.html#SEC300