Mersenne Twister (MT19937) - "offizielle" Tests/Zertifizierung?
-
Gibt es irgendwelche "offiziellen" (vielleicht staatlichen?) oder zumindest "anerkannten" Institute, die den MT19937 "getestet" haben?
Vielleicht irgendsowas wie NIST oder ...?
-
Getestet fuer welche Verwendung/Gesichtspunkt?
-
Ja, die DieHard-Tests gelten als inoffizielle Standardtests für Pseudozufallszahlen. Der Mersenne-Twister schneidet in allen Tests ziemlich gut ab.
Das bedeutet aber NICHT, dass der Mersenne-Twister für Kryptographie geeignet wäre. Er ist bloß sehr gut geeignet für alles wo man Zufallszahlen braucht, die Mathematik hinter dem Generator aber nicht entscheidend ist solange er nur gute Zufallszahlen liefert. MT ist daher sehr gut für beispielsweise Computersimulationen geeignet (weil er auch einigermaßen schnell ist).
Lotteriezahlen würde ich aber nicht mit einem MT ziehen und Kryptografie erst recht nicht - da sind nämlich noch zusätzliche Eigenschaften der internen Arbeitsweise des Generators wichtig.
-
Es geht nicht um Cryptographie, dafür aber um Spiele (Poker, Liner, Roulette).
Lotteriezahlen würde ich aber nicht mit einem MT ziehen
Hmja. Was wäre denn besser?
Aber ... eigentlich ganz egal. Ich suche im Moment gar keinen neuen (besser passenden) Generator.
Die Implementierung mit MT19937 steht bereits. Eine Zertifizierungsstelle möchte jetzt aber irgendwelche Zertifikate/... sehen zum MT19937.Auf einen anderen Generator wechseln wir sicher nur, wenn es unbedingt nötig ist.
Ja, die DieHard-Tests gelten als inoffizielle Standardtests für Pseudozufallszahlen. Der Mersenne-Twister schneidet in allen Tests ziemlich gut ab.
Das weiss ich bereits vom hören-sagen. Frage: gibt's dazu irgendwelche Dokumente/Papers von Stellen denen man das auch glaubt?
Wenn ich der Zertifizierungsstelle nur sage "ist so", bzw. Links auf Homepages von irgendwelchen Leuten gebe, die da schreiben dass der MT19937 toll ist, dann wird die das genau gar nicht interessieren.
p.S.: sind Probleme/Nachteile bekannt wenn man den MT19937 mit Scaling durch Modulo betreibt (statt Division)?
-
hustbaer schrieb:
Es geht nicht um Cryptographie, dafür aber um Spiele (Poker, Liner, Roulette).
Lotteriezahlen würde ich aber nicht mit einem MT ziehen
Hmja. Was wäre denn besser?
MT ist für Spiele ziemlich passend, eventuell auch schon Overkill. Mit den Lotteriezahlen meine ich aber alles, wo es um Geld geht: Es ist nämlich möglich, den inneren Zustand eines MT aus den bisherigen Zahlen zu rekonstruieren. Das heißt ein hinreichend motivierter Schummler könnte dann die Folgeereignisse vorhersagen und immer gewinnen. Deshalb sollte man dem inneren Zustand des MT in diesem Fall regelmäßig eine "Infusion" mit echten Zufallszahlen verpassen.
Aber ... eigentlich ganz egal. Ich suche im Moment gar keinen neuen (besser passenden) Generator.
Die Implementierung mit MT19937 steht bereits. Eine Zertifizierungsstelle möchte jetzt aber irgendwelche Zertifikate/... sehen zum MT19937.Auf einen anderen Generator wechseln wir sicher nur, wenn es unbedingt nötig ist.
Ja, die DieHard-Tests gelten als inoffizielle Standardtests für Pseudozufallszahlen. Der Mersenne-Twister schneidet in allen Tests ziemlich gut ab.
Das weiss ich bereits vom hören-sagen. Frage: gibt's dazu irgendwelche Dokumente/Papers von Stellen denen man das auch glaubt?
Wenn ich der Zertifizierungsstelle nur sage "ist so", bzw. Links auf Homepages von irgendwelchen Leuten gebe, die da schreiben dass der MT19937 toll ist, dann wird die das genau gar nicht interessieren.
Also geht's bei dir schon um Geld? Dann würde ich den MT wie schon gesagt regelmäßig mit ein paar echten Zufallszahlen seeden. Der MT dient dann nur noch dazu, mit diesem Seed (der irgendwie verteilt ist) eine saubere Gleichverteilung zu erzeugen.
Die Mathematik der DieHard-Tests ist ja auf der Seite beschrieben. Brauchst du also nur eine offizielle Teststatistik? Mach sie doch selbst! Die Diehard-Tests brauchen nicht so lange, das kannst du an einem Nachmittag durchlaufen lassen.
p.S.: sind Probleme/Nachteile bekannt wenn man den MT19937 mit Scaling durch Modulo betreibt (statt Division)?
Soweit ich weiß hat der MT keine besonderen Schwächen an keiner Stelle gegenüber anderen PRNG (sonst würde er bei Diehard durchfallen). Es gelten natürlich die üblichen Schwächen von diskreten Zufallszahlengeneratoren beim Skalieren. Sofern dieser minimale Bias bei dir etwas ausmacht. Wobei ich nicht verstehe, wie die Verwendung der Division statt Modulo dabei helfen soll, kannst du das mal erläutern?
-
hustbaer schrieb:
p.S.: sind Probleme/Nachteile bekannt wenn man den MT19937 mit Scaling durch Modulo betreibt (statt Division)?
Meinst du hier mit Scaling das Problem, eine Zufallszahl aus [0,Nmax-1] auf [0,Mmax-1] mit Mmax < Nmax abzubilden? Unabhängig von Verfahren kann da Mist passieren, falls man das mit Modulo macht ( zahl = rand() % Mmax ). Das kann man im allgemeinen nur Lösen,falls man gezogene Zahlen wieder verwirft.
-
hustbaer schrieb:
p.S.: sind Probleme/Nachteile bekannt wenn man den MT19937 mit Scaling durch Modulo betreibt (statt Division)?
Ja, das erzeugt ein statistisches Problem. Je nachdem welchen Modulowert du verwendest, kann es sein, dass Zahlen häufiger vorkommen als anderes. Beispiel: dein RNG erzeugt zahlen zwischen 0 und 31 und du rechnest Modulo 20. dann werden die Zahlen 0-11 doppelt so häufig erzeugt (weil 11 mod 20=11 und 31 mod 20=11) wie andere Zahlen (12 nur durch 12 mod 20).
Ich glaube im Magazin gabs mal nen Artikel wo das erklärt wurde.
*such* da: Zufälle gibt's?! - Funktionen rund um rand, Random und den Zufall
Also geht's bei dir schon um Geld? Dann würde ich den MT wie schon gesagt regelmäßig mit ein paar echten Zufallszahlen seeden. Der MT dient dann nur noch dazu, mit diesem Seed (der irgendwie verteilt ist) eine saubere Gleichverteilung zu erzeugen.
kommt drauf an. In einer Webapplikation die viele Lotterien basierend auf Userinput zieht(mehrere Pokertische parallel zum Beispiel), kriegt man schon so genug Zufall rein - einfach dadurch dass sich die Spieler immer gegenseitig stören. Auch ist ein MT schwer abhörbar. Es braucht zuerst eine zusammenhängende Menge von 624 Datenworten. Noch schwieriger wirds, wenn der output vom MT auf einen kleineren Zahlenbereich skaliert wird. Da diese Skalierung nichtlinear und nicht invertierbar ist, hat man ein irres Problem, den inneren Zustand des MT zu berechnen. Wenn man sogar statt zu skalieren, die Zufallszahlen außerhalb des Intervalls einfach wegwirft, dann kommt man nicht an den inneren Zustand ran. der Abhörer kann ja nicht wissen, ob seine zahl regulär oder erst nach x-Versuchen gezogen wurde.
-
Wenn man sogar statt zu skalieren, die Zufallszahlen außerhalb des Intervalls einfach wegwirft, dann kommt man nicht an den inneren Zustand ran. der Abhörer kann ja nicht wissen, ob seine zahl regulär oder erst nach x-Versuchen gezogen wurde.
Das würde ich (wie oben schon erwähnt) auch dringend empfehlen, da man sonst gar keine saubere Gleichverteilung hinbekommt.
-
@SeppJ:
Das mit dem Sequenz beobachten -> inneren Zustand herleiten -> Zahlen voraussagen ist mir bekannt. Ich denke dass es in unserem Fall kein Problem darstellt (es gibt keine Möglichkeit an einen zusammenhängenden Stream aus mehreren Zahlen zu kommen, schon garnicht >= 600 wie es beim MT19937 nötig wäre).Die Mathematik der DieHard-Tests ist ja auf der Seite beschrieben. Brauchst du also nur eine offizielle Teststatistik? Mach sie doch selbst! Die Diehard-Tests brauchen nicht so lange, das kannst du an einem Nachmittag durchlaufen lassen.
Ich weiss nicht genau was wir brauchen
(Sprachbarriere + ich nicht selbst mit den Leuten von der Prüfstelle gesprochen -> alles sehr vage)Gefragt wurde ich nach einem "Zertifikat" für den Generaor (nicht meine Wortwahl).
Was ich denke was gut wäre, wäre wenn eine Institution wie z.B. NIST ein Paper veröffentlich hätte, wo drinsteht "Wir, NIST, haben uns den Generator angesehen/getestet, und festgestellt dass er folgende Eigenschaften hat laber laber laber".
Das könnten wir dann mal herzeigen, und gucken, ob es reicht. Wenn nicht müssen wir halt sehen - vielleicht müssen wir und das Ding selbst zertifizieren lassen. In dem Fall gehe ich aber davon aus, dass wir sowieso noch Änderungen machen würden. Und vermutlich die Implementierung des Generators selbst schreiben (derzeit: Boost.Random).@Mups/otze:
Meinst du hier mit Scaling das Problem, eine Zufallszahl aus [0,Nmax-1] auf [0,Mmax-1] mit Mmax < Nmax abzubilden?
Genau das meine ich mit Scaling.
Unabhängig von Verfahren kann da Mist passieren, falls man das mit Modulo macht ( zahl = rand() % Mmax ). Das kann man im allgemeinen nur Lösen,falls man gezogene Zahlen wieder verwirft.
Unser Scaling arbeitet derzeit so, dass immer gilt
Nmax > Mmax * 5*10^5.
Unabhängig davon ob nun mit Modulo oder Division gearbeitet wird, ist der max. Fehler in der Gleichverteilung der dadurch entstehen kann also sehr klein. Für uns vollkommen akzeptabel klein.Was ich meine ist: bei einigen Generatoren ist bekannt, dass sie "mistige" Werte liefern, wenn man mit Modulo skaliert, aber ganz brauchbare, wenn man mit Division skaliert (solange Nmax >> Mmax). Zum Bleistift LC Generatoren.
Da es in der FAQ auf der Mersenne Twister Homepage auch mit Division beschrieben steht, dachte ich, ich frag nochmal nach.
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/efaq.html
(Genau genommen steht da man soll die Float-Variante nehmen und dann multiplizieren, aber das kommt sich hübsch aufs gleiche raus wie wenn man nen Integer zieht und dann dividiert)
-
hustbaer schrieb:
Da es in der FAQ auf der Mersenne Twister Homepage auch mit Division beschrieben steht, dachte ich, ich frag nochmal nach.
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/efaq.html
(Genau genommen steht da man soll die Float-Variante nehmen und dann multiplizieren, aber das kommt sich hübsch aufs gleiche raus wie wenn man nen Integer zieht und dann dividiert)Das ist vollkommen äquivalent zu dem modulo-Verfahren, für das die erwähnten Eigenschaften auch gelten. D.h. für Zweierpotenzen ist das Verfahren exakt und für hinreichend kleine Intervalle wird der Bias unglaublich klein. Die Zahl 216 ist dabei schon extrem konservativ. Da ist der Fehler von der Größenordnung 10^-7 (was zufällig auch die Genauigkeit eines floats ist, daher kommen die wohl auf die 216).
