Formel für Pseudozufallszahlen

DraconiX schrieb:
> y = rand() % Bereich;

oder auch mit seed natürlich:

1

int seed = 542;

2

3

y = rand(seed) % Bereich

Das hat vor ein paar Tagen schonmal gefragt. Ich habe aber jetzt nicht 
nachgelesen, ob es Antworten gibt.
Beitrag "Deterministischer Pseudozufall"

Also ne mathematische Funktion y = f(x) kann es so in dem Sinne nicht 
geben, den die ist deterministisch und Zufallszahlen sollen ja gerade 
nicht deterministisch sein.

Anders gesagt: Wenn du ne feste mathematische Funktion wie y = x² + 2x - 
5 hast, dann kannst du die beliebig oft ausrechnen und es wird jedesmal 
für das gleiche x auch das gleiche y rauskommen.

Das gilt auch für Differentialgleichungen, Integrale und was es da sonst 
noch gibt.

Wenn du jetzt ne Pseudozufallszahl haben willst, dann gibts da 
verschiedene Verfahren, das rückgekoppelte Schieberegister wurde schon 
genannt.
Das ist auch deterministisch, mit dem gleichen Startwert kommt immer die 
gleiche Zufallszahlenfolge raus.
Die Zufallszahlen sind also in sich schon zufällig (in dem Sinne, dass 
alle Zahlen des Intervalls gleich große Wahrscheinlichkeit haben, wie 
bei einem fairen Würfelwurf). Aber die Zahlen sind trotzdem vorhersagbar 
und taugen daher nicht für Krypto.
y = rand(seed); ist sowas. Zumindest meistens, Doku lesen.

Es gibt noch die häufig eingesetzte Lösung y = rand(seed) wobei seed ein 
tatsächlich komplett zufälliger Wert ist, der jedesmal neu gewählt wird. 
Beliebt: Seed von Random.org holen. Aber dann mehrfach und daraus nen 
Hash berechnen und die Hashes dürfen nicht gleich sein. Es gab mal den 
Fall wo random.org down war und die Seeds waren alles Hashes der 404 
Fehlermeldung. Da hat sich dann irgendein schlauer Mensch selbst 1000 
Bitcoins überwiesen ;)

Weitere Quellen für Zufälligkeit (Entropie genannt):

- Maus- und Tastaturereignisse mitschneiden, in eine Integer-Zahl 
verwursten, daraus nen Hash berechnen
- Zeit in ms seit Rechner- bzw. Programmstart
- Absolute Uhrzeit in Unix-millisekunden
- MAC-Adresse und IP des primären Netzwerkadapters zu nem Hash 
verwursten

usw usw

Danke für die Antworten!

THOR schrieb:
> Anders gesagt: Wenn du ne feste mathematische Funktion wie y = x² + 2x -
> 5 hast, dann kannst du die beliebig oft ausrechnen und es wird jedesmal
> für das gleiche x auch das gleiche y rauskommen.

Genau so war die Frage gemeint.

Gibt es eine Formel wie z.B.

y = (3*x^(x+2)+5*x^(x+4)+7*x^(x+6))/(2*x^(x+1)+4*x^(x+3)+6*x^(x+5))

die für jedes x eine feste "Zufallszahl" y ausspuckt?

Stefan schrieb:
> Gibt es eine Formel wie z.B.
>
> y = (3*x^(x+2)+5*x^(x+4)+7*x^(x+6))/(2*x^(x+1)+4*x^(x+3)+6*x^(x+5))
>
> die für jedes x eine feste "Zufallszahl" y ausspuckt?
Nicht in der Art, aber eine Hashfunktion macht das.

Stefan schrieb:

> weiß jemand, ob es eine mathematische Funktion gibt, mit der man
> Pseudozufallszahlen generieren kann, also eine Funktion in der Form
>
> y = f(x)
>
> Wobei y dann die Pseudozufallszahl zum jeweiligen x ist.

schau mal nach "Linear rückgekoppeltes Schieberegister" engl LFSR oder 
"Maximum length sequence". Damit erzeugt man Sequenzen zufällig 
verteilter Binärzahlen. x währe dann der Index in dieser Sequenz 
generecht ab dem Initialisierung.

Die Mathematik dazu findet sich wohl unter dem Stichwort Galoisfelder 
o.ä..

Daniel F. schrieb:
> verdammt, zu spät dran mit bearbeiten.
>
> Stefan schrieb:
>> Gibt es eine Formel wie z.B.
>>
>> y = (3*x^(x+2)+5*x^(x+4)+7*x^(x+6))/(2*x^(x+1)+4*x^(x+3)+6*x^(x+5))
>>
>> die für jedes x eine feste "Zufallszahl" y ausspuckt?
>
> da für jedes x eine "feste Zufallszahl" gefragt ist, erfüllt jede
> injektive funktion die genannte bedingung.
>
> im einfachsten fall: y = x

Etwas allgemeiner ausgedrückt: y kann nur so zufällig sein wie x. Oder 
im Fachterminus: Die Entropie lässt sich mit deterministischen 
Funktionen nicht steigern.
Daher ist in der Praxis Entropiegewinnung äußerst wichtig. Die gesamte 
Kryptographie hat das Problem, dass Computer deterministisch sind (also 
wie y=x).

y=sin(x) ausrechnen und dann die 4., 5. und 6 Stelle nach dem Komma 
verwenden. Den Rest wegwerfen. x wahlweise als fortlaufenden Wert oder 
das y verwenden. Das hat für die Spielprogrammierung unter der Bank in 
der Berufsschule (vor 30 Jahren) ausgereicht.

nixundnul schrieb:
> Das hat für die Spielprogrammierung unter der Bank in
> der Berufsschule (vor 30 Jahren) ausgereicht.

Ein genialer mathematischer Beweis ...

SCNR

@Stefan:
By the way, aus welcher Zahlenmenge, bzw Definitionsbereich  soll denn x 
und y sein?
N, R, Z, ...?

Oder beschreibe einfach mal dein eigentliches Problem.

Der Andere schrieb:
> nixundnul schrieb:
>> Das hat für die Spielprogrammierung unter der Bank in
>> der Berufsschule (vor 30 Jahren) ausgereicht.
>
> Ein genialer mathematischer Beweis ...
>
> SCNR

war der gefragt? Schließlich geht es um Pseudo-Zufallszahlen. Und 
rückgekoppeltes Schieberegister ist deterministisch und wiederholt sich 
auch. Es geht (mir) eher darum, wie man in einer gegebenen 
Programmiersprache mit dem wenigsten Aufwand ein ausreichendes 
Ergebnis erzielt. Programmiersprache und Anforderungen kennen wir nicht. 
GOTO 10.
(damals war es SHARP1210-Basic)

Stefan schrieb:
> weiß jemand, ob es eine mathematische Funktion gibt, mit der man
> Pseudozufallszahlen generieren kann, also eine Funktion in der Form

ja. gibt es. Man sollte nur wissen, wozu man die Zufallszahlen benötigt.
Für Verschlüsselung braucht es andere ufallszahlen wie für statistische 
Testverfahren.

Schreiber schrieb:
> Stefan schrieb:
>> weiß jemand, ob es eine mathematische Funktion gibt, mit der man
>> Pseudozufallszahlen generieren kann, also eine Funktion in der Form
>
> ja. gibt es. Man sollte nur wissen, wozu man die Zufallszahlen benötigt.
> Für Verschlüsselung braucht es andere ufallszahlen wie für statistische
> Testverfahren.

Die meisten Antworten sind so blöd, wie die von Schreiber.

Hier ein Link zur Frage:

http://www.math.uni-frankfurt.de/~numerik/lehre/Vorlesungen/Comp_Fin09/skript/n-shell3.pdf

Baldrian schrieb:
> Schreiber schrieb:
>> Stefan schrieb:
>>> weiß jemand, ob es eine mathematische Funktion gibt, mit der man
>>> Pseudozufallszahlen generieren kann, also eine Funktion in der Form
>>
>> ja. gibt es. Man sollte nur wissen, wozu man die Zufallszahlen benötigt.
>> Für Verschlüsselung braucht es andere ufallszahlen wie für statistische
>> Testverfahren.
>
> Die meisten Antworten sind so blöd, wie die von Schreiber.

Der Schreiber hat aber schon recht, es gibt unterschiedliche 
Anforderungen an Pseudozufallsreihen. Und das meint nicht nur die 
spektralen Eigenschaftzen sondern auch den Ressourcenbedarf bei der 
Generierung.

> http://www.math.uni-frankfurt.de/~numerik/lehre/Vo...

Naja mit der Forderung nach Unverhersehbarkeit (s. S.46) schliessen die 
schon mal die in der Praxis häufig verwenden Generatoren aus. Es geht ja 
hier um Pseudozufall und nicht Zufall im Sinne der ergrauten 
Mathematiker im universitären Elfenbeinturm.

schau dir das mal an:

1

x = 4x(1-x)

x müsste man dann multiplizieren, und mit modulo den gewünschten bereich 
rausrechen.
ob und wie periodisch das ganze ist weiß ich nicht.

1

#!/usr/bin/perl

2

3

my $x = 0.1487423874; # seed zwischen 0..1

4

5

while (true) {

6

  $x = 4*$x*(1-$x);

7

  print "$x\n";

8

}

1

0.0616415806104669

2

0.231367584601241

3

0.711346501588114

4

0.821330625065862

5

0.586986517579131

6

0.969733383037822

7

0.11740219543937

8

0.414475679781545

9

0.970742362604685

10

0.113606512197437

11

0.402800290335083

12

0.962208865764223

13

0.1454518576358

14

0.49718245898438

15

0.999968245850501

16

0.000127012564691813

17

0.000507985730000895

18

0.00203091072199604

19

0.00810714449454129

20

0.0321656748107437

21

0.124524176698853

22

0.436071624465302

23

0.983652651205979

24

0.0643204519257122

25

0.240733325559137

26

0.731123166097503

27

0.786328328372264

28

0.672064353486179

29

0.881575433037533

30

0.417600755608878

31

0.972841458095088

32

0.105683822026044

33

0.378059007152044

34

0.94052157705302

35

0.223762960602882

36

0.694772392260461

37

0.848254860852549

THOR schrieb:
> MAC-Adresse und IP des primären Netzwerkadapters zu nem Hash
> verwursten

Beides ist, zumindest bei mir, nicht entropiebehaftet sondern immer 
identisch (zumindest auf meinem Rechner).

Such mal nach m-Folge Generator oder linear rückgekoppletes 
Schieberegister.

nixundnul schrieb:
> y=sin(x) ausrechnen und dann die 4., 5. und 6 Stelle nach dem Komma
> verwenden.

Mit etwas Überlegen finden sich bestimmt noch umständlichere Verfahren, 
die sich auf einem uC noch schlechter implementieren lassen.

Warum das einfach zu implementierende bitweise Schieberegister nehmen, 
welches mit ein paar Shifts und Xors auskommt, wenn man so richtig 
Rechenzeit und Speicher verschwenden kann?

Axel S. schrieb:
> peziell bei einem µC stellt sich das Problem der Initialsierung des
> Zufallsgenerators. Denn nach dem Einschalten der Stromversorgung werden
> alle Variablen mit definierten Werten initialisiert. Der Generator
> liefert dann immer die gleiche Zahlenfolge. Wenn man das ändern will,
> muß man sich irgendwie einen echt zufälligen Startwert beschaffen.

das kann man mit einem A/D machen der zB. das Rauschen einer Diode 
misst.
Oder ich bilde eine CRC über den RAM Bereich der ja dann rein zufällige 
Werte hat, sofern er nicht systematisch geleert wird. Oder Oder Oder

Stephan schrieb:
> Axel S. schrieb:
>> liefert dann immer die gleiche Zahlenfolge. Wenn man das ändern will,
>> muß man sich irgendwie einen echt zufälligen Startwert beschaffen.
>
> das kann man mit einem A/D machen der zB. das Rauschen einer Diode
> misst.

Da ein AD-Wandler nur eine begrenzte Auflösung hat, beispielsweise 8bit 
oder ^10Bit und damit nur einen sehr begrenzten Wertebereich (256, 1024 
Elemente) aufweist ist das wohl kaum als "echt zufälliger Startwert" zu 
bezeichnen.

Baldrian schrieb:
> Die meisten Antworten sind so blöd, wie die von Schreiber.
>
> Hier ein Link zur Frage:
>
> 
http://www.math.uni-frankfurt.de/~numerik/lehre/Vorlesungen/Comp_Fin09/skript/n-shell3.pdf

Baldian ist also der Selbe wie Stefan und das ist eine (Haus)aufgabe.
Halte dich an die Forumsregeln!

der "echte" ist doch nur echt, weil nicht vorhersehbar. Das ist doch 
durch zB. das Rauschen gegeben. Ich glaube Intel hat sowas auch in den 
CPU mal gemacht. Dann kann ich doch damit weiterrechnen wie ich will.

Axel S. schrieb:

> Ein Pseudozufallsgenerator ist idR. nicht als Funktion
> implementiert, [...]

... wobei auch das ohne weiteres moeglich ist.

Im Zusammenhang mit dem DES habe ich gelesen, dass es
umfangreiche Untersuchungen gibt, die seine Qualitaeten
als Pseudozufallszahlengenerator belegen.

Possetitjel schrieb:
> Im Zusammenhang mit dem DES habe ich gelesen, dass es
> umfangreiche Untersuchungen gibt, die seine Qualitaeten
> als Pseudozufallszahlengenerator belegen.

Ja weil des ja ein Qualitätsmerkmal eines guten Encoders ist. Dessen 
Output ist mit statistischen Mitteln nicht von Rauschen unterscheidbar, 
alle statistischen Eigenschaften des plain textes wie 
Buchstabenhäufigkeit sind durch das Codieren "entfernt".

Ruediger A. schrieb:
> Allerdings wird der TO ja (hoffentlich) wissen, warum er EXPLIZIT nach
> einem Pseudrandomgenerator gefragt hat...
Hat er ja noch nichtmal. Das ist nur im Betreff falsch angegeben. 
Deshalb verstehe ich die Diskussion über Startwerte nicht. Er braucht 
keinen Startwert.

Anscheinend will er eine Funktion, die Eingabewerte auf zufällig 
scheinende Ausgabewerte abbildet.
Deshalb der Vorschlag mit den Hasfunktionen. Die machen genau sowas.
Die letzten vier Stellen von MD5 zum Beispiel ergeben
0->64da
1->849b
2->862c
3->baf3
Die Eingangsfolge ist linear, die Ausgangsfolge 'zufällig' verteilt.

Da er nicht geschrieben hat, wofür er das braucht, muss er selber 
entscheiden wie die Abwägung zwischen Berechnungsaufwand und 
'Zufälligkeit' ausfällt.

Naturereignisse wie Uhrzeit, Temperatur, Windgeschwindigkeit, Helligkeit 
digitalisieren und dann für die Bildung der Zufallszahlen 
weiterverwenden.

Ich brauch die Lottozahlen für die kommende Ziehung, hat da wer was?

DraconiX schrieb:
> y = rand() % Bereich;

STOP! Das erzeugt keine gleichverteilten Zufallszahlen!


Die erste Frage sollte sein: Wofür brauchst du die Zahlen?
- Elektronischer Würfel?
- Krypto-Anwendung?

Md M. schrieb:
> Dimpel schrieb:
>> Ich brauch die Lottozahlen für die kommende Ziehung, hat da wer was?
>
> Findest du in der Zahl Pi irgendwo hinterm Komma.
Mal so ein bisschen abseits vom Thema, ist das eigentlich bewiesen? Es 
könnte ja sein, dass Pi irgendwann zum Beispiel nur noch aus 
10100100010000 und so weiter besteht. Dann wäre es immer noch 
irrational, würde aber nicht alle Informationen enthalten.

Ich kenne das Problem. Die Vorschläge zu Rauschen, Wetterereignissen, 
etc. nutzen ja nicht viel, da eine Funktion y = f(x) gefragt ist, d.h. 
reproduzierbar gleiche Ausgabe bei gleicher Eingabe. Wobei die Ausgabe, 
wenn man 1, 2, 3, 4, 5, ... reinsteckt, eben möglichst (wie man das auch 
immer definiert) "zufällig" sein soll.
Beispiel aus der Praxis: Man hat zwei getrennte Geräte und in jedem 
läuft eine Uhr und man möchte zufällige Ereignisse haben, die bei beiden 
Geräten gleichzeitig auftreten. Dann könnte man mit so einer Funktion, 
die die Zeit als Eingabe hat, solchen Zufall erzeugen.

Vorschläge wie die x. Stelle von Pi sind nicht so gut, da die Laufzeit 
eines solchen Algorithmus immer größer wird, je mehr Zeit vergeht.

Der Vorschlag mit der 3-5. Nachkommastelle des Sinus ist drollig. 
Wahrscheinlich wird das Beste in der Tat irgendeine solche oder ähnlich 
Hash-Funktion sein. Je nach Mikrocontroller müsste es halt 
ressourcenschonend sein. Das kann man sich dann mal überlegen. 
Vielleicht meldet sich der OP ja nochmal.

Marek N. schrieb:
> Such mal nach m-Folge Generator oder linear rückgekoppletes
> Schieberegister.

Wurde in diesem Thread jetzt schon öfter genannt. Wie oft denn noch? Ja 
damit kann man Pseudozufallszahlen generieren. Es kommt aber auch bei 
jedem Durchlauf das gleiche raus.

Frank N. Stein schrieb:
> und man möchte zufällige Ereignisse haben, die bei beiden
> Geräten gleichzeitig auftreten.

Genau das macht man mit Schieberegistern, die bei beiden Geräten gleich 
geschaltet sind
https://de.wikipedia.org/wiki/Linear_r%C3%BCckgekoppeltes_Schieberegister

Du setzt dann aber voraus, dass die Geräte ständig laufen.

Wenn eines aber mal ausgeschaltet ist und dann neu gestartet wird, 
sollte man höchstens die Zeit richtig stellen müssen. Der inneren 
Zustände der Schieberegister wären dann trotzdem nicht synchron. Kannst 
du folgen?

Johann, hast du eine Idee zu einer solchen Hash-Funktion, wie von dir 
beschrieben? Also möglichst ressourcenschonend (wenige Zyklen) für einen 
AVR? Am besten sollte ein uint32_t rauskommen. Ich hätte eine Verwendung 
dafür. :)

Frank N. Stein schrieb:
> Wenn eines aber mal ausgeschaltet ist und dann neu gestartet wird,
> sollte man höchstens die Zeit richtig stellen müssen.

Dann nimm halt einen MD5-Hash über die Zeit.

Nur, was machst Du, wenn die eine Uhr 2 Sekunden nachgeht?

Wenn die eine Uhr 2 Sekunden nachgeht, weil vom Anwender falsch 
gestellt: Sein Pech.

Wenn die Uhr falsch geht, weil die Quarze nicht ganz synchron laufen: 
Dann nützt auch ein anderer Pseudozufallsgenerator nix.

MD5 ist aber ganz schön heavy für einen AVR. ;)

Leider erfüllt der Vorschlag nicht das schon mehrfach angesprochene 
Kriterium. Du hast einen inneren Zustand, d.h. du benutzt nicht die Zeit 
allein.

Stefan (Gast) will:

> y = f(x)
> Wobei y dann die Pseudozufallszahl zum jeweiligen x ist.

> Gibt es eine Formel wie z.B.
> y = (3*x^(x+2)+5*x^(x+4)+7*x^(x+6))/(2*x^(x+1)+4*x^(x+3)+6*x^(x+5))
> die für jedes x eine feste "Zufallszahl" y ausspuckt?

Wie schon oben teilweise erkennbar, gibt es Unmengen von
"Rechenvorschriften" die aus einer Zahl eine andere machen können,
wo der Zusammenhang von Eingabe und Ausgabe nicht leicht erkennbar
ist. In der Sprache C kann man das als eine Function
implementieren, ist also eine Funktion.

Dabei muss man sich aber auf die Bitlänge der Zahl festlegen,
sonst ist es nicht programmierbar.

Wenn du jetzt nur aus jedem Input-Wert eine bunte LED-Ansteuerung
machen willst, bist du mit einem LFSR und NULL-Umgehung schon
gut bedient.
FERTIG.

Wenn du aus der "Zufallszahl" aber auch wieder die Eingabe-
Zahl zurückgewinnen willst, oder eine EINDEUTIGE (!) Zuordnung
von Eingabe zu "Zufallszahl" haben willst, darfs du nicht nach
Zufallszahlen fragen, sondern nach VERSCHLÜSSELUNG.

Dann wird vielleicht auch die Zahl der Schlaumeier-Beiträge
reduziert. ;-)

n(1)=1234567890;
for i=2:1001
n(i) = mod (16807*n(i-1), 2147483647);
i = i+1;
end
n = n / 2147483647;

Kein Thread mit Substring "zufall" im Betreff ist komplett ohne:
https://xkcd.com/221/

>> Findest du in der Zahl Pi irgendwo hinterm Komma.
> Mal so ein bisschen abseits vom Thema, ist das eigentlich bewiesen? Es
> könnte ja sein, dass Pi irgendwann zum Beispiel nur noch aus
> 10100100010000 und so weiter besteht. Dann wäre es immer noch
> irrational, würde aber nicht alle Informationen enthalten.

Das ist Pi garantiert in der 0b-Welt.