Pseudo-Zufallszahlengenerator

Hier mal Pseudo-Zufallszahlengenerator in bunt!

http://en.wikipedia.org/wiki/Linear_feedback_shift_register

Bis 34 Bit hilft diese Tabelle:

http://www.mikrocontroller.net/attachment/13236/Pseudozufall.png

> http://en.wikipedia.org/wiki/Mersenne_twister

2.5kB RAM fuer einen Zufallszahlengenerator sind wohl etwas viel in 
einem Mikrocontroller.

Vom Prinzip her ist er aber sehr gut geeignet, am Besten kleinere 
Varianten davon (ein paar zig Bytes) mit Diehard testen, bis man was 
brauchbares findet.

Nicht fuer Verschluesselung oder Gluecksspiel verwenden!

1

 // Create a length 624 array to store the state of the generator

2

 int[0..623] MT

3

 int index = 0

4

5

 // Initialize the generator from a seed

6

 function initializeGenerator(int seed) {

7

     MT[0] := seed

8

     for i from 1 to 623 { // loop over each other element

9

         MT[i] := last 32 bits of(1812433253 * (MT[i-1] xor (right shift by 30 bits(MT[i-1]))) + i) // 0x6c078965

10

     }

11

 }

12

13

 // Extract a tempered pseudorandom number based on the index-th value,

14

 // calling generateNumbers() every 624 numbers

15

 function extractNumber() {

16

     if index == 0 {

17

         generateNumbers()

18

     }

19

20

     int y := MT[index]

21

     y := y xor (right shift by 11 bits(y))

22

     y := y xor (left shift by 7 bits(y) and (2636928640)) // 0x9d2c5680

23

     y := y xor (left shift by 15 bits(y) and (4022730752)) // 0xefc60000

24

     y := y xor (right shift by 18 bits(y))

25

26

     index := (index + 1) mod 624

27

     return y

28

 }

29

30

 // Generate an array of 624 untempered numbers

31

 function generateNumbers() {

32

     for i from 0 to 623 {

33

         int y := 32nd bit of(MT[i]) + last 31 bits of(MT[(i+1) mod 624])

34

         MT[i] := MT[(i + 397) mod 624] xor (right shift by 1 bit(y))

35

         if (y mod 2) == 1 { // y is odd

36

             MT[i] := MT[i] xor (2567483615) // 0x9908b0df

37

         }

38

     }

39

 }

Müsste ich mal von Pseudocode nach C umschreiben.
Ist für meine Fummellei ein bischen mit Kannonen auf Spatzen geschossen, 
aber trotzdem danke :-)

>Nicht fuer Verschluesselung oder Gluecksspiel verwenden!

Warum?

> >Nicht fuer Verschluesselung oder Gluecksspiel verwenden!

> Warum?

Allgemein ist dieser RNG nicht geeignet, wenn man es mit intelligenten 
Gegenspielern zu tun hat. Es ist relativ leicht moeglich, aus den 
Ausgabewerten den Zustand zu berechnen, und dann die weitere Folge 
vorherzusagen. Bei kryptographischen Schluesseln oder z.B. Pokerkarten 
ist das unguenstig.

Mathematisch liegt das daran, dass die Berechnung im 
Zufallszahlengenerator linear ist.

Erst mal danke für die vielen netten Antworten.
Aber alles ziemlich kompliziertes Zeug!

@ Hagen Re (hagen): Welcher µC?

@ alle: Gibt's nix einfaches? anstelle

1

Z^=0x04C11DB7;

eine 64-bit Konstante

1

static unsigned long long int my_rand_64_bit()

2

{

3

        static unsigned long long int Z;

4

        if (Z == 0) Z = 0x47110815;

5

6

        if (Z & 0x8000000000000000)

7

        {

8

                Z<<=1;

9

                Z^=0x0447C11110D8B175;

10

        }

11

        else

12

        {

13

                Z<<=1;

14

        }

15

        return Z;

16

}

Würde bloß etwas lange dauern das zu testen :-)

Theorie: Könnte man - wenns ein AVR ist - nicht einfach noch nen offen 
hängenden ADC-Pin mit einbeziehen? Der schwebt in der Luft, fängt sich 
"irgendein" Potential ein => "zufälliger" Wert, den man da noch 
mitverwursten kann.

Kommt drauf an, was du willst:

ECHTEN Zufall bekommt man z.B. aus dem Rauschen von Z-Dioden.
Dabei muss die Schaltung aber sehr gut von allen äußeren Einflüssen
geschirmt werden! Also HF- und NF-dicht! Dazu gegehören Drossel-
Spulen, Durchführungskondensatoren, versilberte dicke Messinggehäuse
etc.

ZUFÄLLIG ERSCHEINENDE Signale kann man mit "Linear Feedback Shift
Registers" (LFSR) erzeugen. Die Fa. XILINX hat mal App-Notes
veröffentlicht, in denen LFSRs bis 168 Bit beschrieben werden.
(Dezimal 50-stellig: 10 hoch 33 Jahre bei 10 GHz...)

Der Vorteil ist, dass man selbst vorausberechnen kann, was an "Zufall"
herauskommt, - aber jeder, der es nachbaut, auch!

Verknüpft man mehrere LFSRs miteinander wird es für andere schon
deutlich schwieriger, dies nachzuvollziehen!

Also muss die Verknüpfung gut "abgeschirmt" werden...

Gruß Ralli

Hallo Mark,

>Man könnte das thermische Rauschen eines analogen Bauteils per
>A/D-Wandler auslesen. Ist bestimmt super um echte Zufallszahlen zu
>bekommen.

Damit ist es leider nicht getan. Es geht ja nicht nur darum eine Zahl zu 
erzeugen, von der du vorher nicht weißt, wie sie aussieht, sondern auch 
darum, daß die Zufallszahlen in dem gewünschten Bereich gleichverteilt 
sind. Und das ist bei einer solchen Anordnung eher nicht der Fall, weil 
beispielsweise die Zufallszahl die dem Ruhepegel der Eingangsspannung 
entspricht, viel häufiger vorkommt, als die zu Rauschspitzen gehörenden 
Zufallszahlen.

Man könnte versuchen, daß Wandlungsergebnis so zu interpretieren, daß 
Rauschspitzen, die über dem Ruhepegel liegen eine logische "1" ergeben 
sollen, und Rauschspitzen unter dem Ruhepegel eine logisch "0". Man 
würde dann bei jedem Lesen des ADC ein Zufallsbit erzeugen.

Damit ist es aber leider auch noch nicht getan, da durch einen eventuell 
leichten Versatz des Ruhepegels gegenüber der exakten zugehörigen 
Schaltschwelle im ADC die Nullen und Einsen wieder nicht ganz 
gleichverteilt sind.

Vor einiger Zeit habe ich mal einen Zufallsgenerator wie im Anhang 
aufgebaut. Hier wird das thermische Widerstandsrauschen verstärkt, 
bandbreitenbegrenzt und dann auf einen Schmitt-Trigger gegeben. Die 
Bandbreitenbegrenzung ist sinnvoll, damit tieffrequentes Rauschen nicht 
dominiert und die Schaltung bei Übersteuerung nicht für längere Zeit 
lahmlegt. Mit den beiden Hochpässen erzwinge ich, daß der Komparator 
schnell genung hin- und herschaltet.

Ein nachfolgendes Flip-Flop sorgt für eine Vergleichmäßigung der 
0-1-Verteilung.

Die endliche Slew Rate am Ausgang des MCP601 verhindert, daß der 
Schmitt-Trigger zu schnell umschaltet und das erste Flipflop eventuell 
metastabil wird.

Natürlich ist der Aufbau der Schaltung einigermaßen kritisch. Die 
Signalmasse dieser Schaltung muß vollkommen isoliert sein und darf nur 
an den gezeichneten Anschlüssen mit dem Rest der Schaltung verbunden 
werden. Abschirmung der Schaltung ist ein Muß!

Zwischen dem Auslesen der Zufallsbits sollten übrigens möglichst lange 
Zeitspannen liegen, mindestens 10msec, besser daber deutlich mehr.

Kai Klaas