Zufallszahlen und deterministische Simulation



    Als ich in jüngerer Zeit einem Kollegen bei der Lösung der Frage nach der Wiederholbarkeit mehrerer Tests half, kam ich erneut auf die Aufgabe, ein Gerät zu simulieren, das Zufallszahlenfolgen generiert. In diesem Artikel werde ich darüber sprechen, welche Schwierigkeiten entdeckt wurden, welcher Lösungsansatz gewählt wurde und wie ich überprüft habe, ob die neue Lösung besser ist als die vorherige. Ich stelle sofort fest, dass die Frage der Erstellung und Überprüfung von Zufallssequenzen sehr heikel ist und fast keine Lösung als endgültig angesehen werden kann. Ich würde mich über Kommentare und Korrekturen freuen.

    Zunächst werde ich kurz auf den Themenbereich Hardware und Pseudozufallsgeneratoren eingehen, auf deren Eigenschaften und Anforderungen. Dann werde ich mich meinem Spezialfall zuwenden - dem Bereich der Softwaresimulation von Computersystemen und einem spezifischen Problem, das gelöst werden musste.


    Manchmal ist es am zuverlässigsten, eine Zufallszahl aus einem Verzeichnis abzurufen. Bildquelle : www.flickr.com/photos/nothingpersonal/337684768


    Einführung: RNG, PRNG, RNG, DRNG


    Die Aufgabe, mit einem Computer eine „zufällige“ Folge von Zahlen zu erhalten, ist überraschend komplex. Intuitiv kann dies durch die Tatsache gerechtfertigt werden, dass die Philosophie digitaler Systeme und die Architektur moderner Computer darauf abzielen, absolute Genauigkeit zu erreichen und auch einen Hauch von Unsicherheit als Ergebnis der Arbeit zu beseitigen. Die gespeicherten und übertragenen Daten werden durch Prüfsummen überprüft, Stromkreise werden dupliziert. Der Unfall ist ausgeschlossen. Wie kann ich ihn zurückgeben? Und warum?

    Tatsächlich erfordern viele praktische Probleme Algorithmen, die ausreichend lange Zufallsfolgen zur Lösung verwenden. Simulation, genetische Algorithmen, numerische Integrations- und Lösungssysteme für lineare Gleichungen (Monte-Carlo-Methoden), Computerspiele und moderne Kryptographie. In jedem Fall hat man ein eigenes Verständnis davon, welche Sequenzen bereits als zufällig angesehen werden können und welche noch nicht. Die verwendeten Zufallszahlengeneratoren unterscheiden sich ebenfalls (RNG, English RNG - Zufallszahlengenerator).

    Es scheint, dass die Natur genug Chaos schafft, wo die Menschheit mithalten kann. Es reicht aus, ein Digitalisiergerät für einen bestimmten Prozess (thermisches Rauschen, Blitz in der Sonne, Werfen einer Münze) zu erstellen, es an einen Computer anzuschließen und das Ding ist im Hut.

    Die praktische Verwendung von "sauberen" Hardware-RNGs wird jedoch durch die folgenden Faktoren eingeschränkt. Erstens ist die Geschwindigkeit, mit der Zahlen generiert werden, möglicherweise nicht hoch genug, und Anwendungen können sie so schnell verarbeiten, dass selbst moderne Schnittstellen wie PCI-Express in die Augäpfel geladen werden. Zweitens sind die statistischen Eigenschaften einer solchen Sequenz möglicherweise nicht die besten - die Verteilung stimmt nicht oder ändert sich mit der Zeit, die Breite der Zahlen ist geringer als erforderlich, die Tendenz, häufiger Nullen als Einheiten zu erzeugen (englische Abweichung) usw. Drittens kann der Preis für ein solches qualitativ hochwertiges Gerät recht hoch sein, was seinen Anwendungsbereich auf Bereiche mit den strengsten Anforderungen an die Zufälligkeit einschränkt. Schließlich sind der Stromverbrauch und die Größe des RNG möglicherweise nicht für mobile Geräte geeignet.

    Aus diesem Grunde oft kombinierte Ansatz verwendet: der Anfangswert (seed) aus der Zufallsquelle entnommen, und die ganze Sequenz erzeugte daraus nonrandom Funktion:

    (a 1 , s 1 ) = f (Samen)
    (a 2 , s 2 ) = f (s 1 )
    (a 3 , s 3 ) = f (s 2 )
    ...

    Hier ist a 1 , a 2 , ... die ausgegebene Pseudozufallssequenz und s 1 , s 2, ... ist der interne Zustand des Generators. Das resultierende Konstrukt wird als Pseudozufallszahlengenerator (PRNG - Pseudozufallszahlengenerator) bezeichnet.
    Die Qualität der Folge hängt offensichtlich von der Wahl der Funktion f () und manchmal auch vom Wert des Startwerts ab (zum Beispiel ergibt f (x) = a * x mod m eine Folge von Nullen bei Startwert = 0). Die Geschichte kennt viele Verwendungen von schlechten Funktionen. Ich werde nur zwei Beispiele geben.
    1. a i + 1 = 65539 * a i mod 2 31 , Startwert - ungerade. Dies ist das klassische RANDU , das von 1960 bis 1970 unter UNIX weit verbreitet war. Schlägt auch bei den einfachsten Tests fehl (wir werden später darüber sprechen).
    2. Donald Knuth [5] beschreibt seinen Versuch von 1959, ein Super-PRNG mit einem Algorithmus von 13 Schritten zu erstellen, von denen einer komplizierter als der andere ist. In der Praxis stellte sich heraus, dass die Sequenz sofort zu einer Zahl konvergierte, die dann in sich selbst umgewandelt wurde.


    Zufallsquellen in Computerplattformen


    Zurück zum Hardware-RNG. Sie sind seit einiger Zeit in der IBM PC-Architektur vorhanden und werden sowohl in Intel-Komponenten als auch in anderen Anbietern angeboten. Einige Beispiele unten.
    • Ende des 20. Jahrhunderts wurde ein Hardware-RNG in den Intel 82802 Firmware Hub eingebaut. Es funktionierte einwandfrei, aber es gab Beschwerden hinsichtlich des Energieverbrauchs, der Geschwindigkeit der Erzeugung und der Kompatibilität mit der immer kleiner werdenden Größe des Prozesses.
    • Aus diesem Grund wurde ein neues RNG entwickelt, das sich direkt im Kern der CPU befindet. Es wurde in den Ivy Bridge-Mikroarchitekturprozessoren als RDRAND-Anweisung dargestellt [4]. Später wurde es auch für den RDSEED-Unterricht verwendet. Die Unterschiede zwischen den beiden Teams werden hier geschrieben . Ein paar Artikel über Habré über RDRAND: habrahabr.ru/post/128666 habrahabr.ru/post/145188
    • Auf modernen Plattformen befindet sich ein eigenes RNG im TPM-Modul (English Trusted Platform Module) und kann sowohl für die Anforderungen der Kryptographie als auch für andere Zwecke verwendet werden. Details zur Arbeitsgeschwindigkeit und zur Qualität der ausgegebenen Nummern sind in [8] beschrieben.
    • VIA bietet auch ein Hardware-RNG als Teil seiner VIA C3-Prozessoren an [6].


    Allgemeine Anforderungen für RNG


    Da ich an Softwaremodellen von Geräten arbeite, ergibt sich das Problem, das in ihnen vorhandene RNG zu modellieren. Modell d.h. Letztendlich sollte die Funktion, die den Generator in C implementiert, die Anforderungen für physikalische RNGs erfüllen. Ist dies nicht der Fall, sollten die Unterschiede durch die Merkmale des Modellierungsprozesses verstanden und erklärt werden - Sie können diese Frage nicht dem Zufall überlassen. Letztendlich ist jedes Modell nur eine Annäherung an die Realität, es ist wichtig, dass es für die praktischen Bedürfnisse gut genug ist und seine Grenzen verwirklicht werden.
    • Ein Unfall. Das vageste Kriterium, und wir werden darauf zurückkommen. Es ist jedoch bereits klar, dass es sinnvoll ist, sich der Auswahl einer Funktion zu nähern und sie mit Tests zu testen.
    • Verteilung. Wir gehen davon aus, dass die geforderte Verteilung U [0 ist; 2 N –1], wobei N = 64 ist. Moderne Generatoren produzieren genau so viele Bits.
    • Tolle Zeit. Jede Sequenz aus dem PRNG wird aufgrund der begrenzten Anzahl unterschiedlicher interner Zustände in einer Schleife ausgeführt. Dies wird nicht auffallen, wenn ihre Periode sehr lang ist. Unser Ziel ist ein Wert in der Größenordnung von 2 63 oder höher.
    • Erzeugungsrate. RDRAND kann zig Millionen Zahlen pro Sekunde produzieren. Die Simulation arbeitet normalerweise viel langsamer als echtes Eisen. Wir werden der hohen Generierungsgeschwindigkeit nicht nachjagen, Sie sollten jedoch nach Möglichkeit keine zu komplexen Funktionen auswählen - Sie möchten keinen Engpass verursachen.
    • Vorhersehbarkeit. Dieser Aspekt ist wichtig für kryptografische Anwendungen. Unser Modell wird für solche Bedürfnisse nicht verwendet. Darüber hinaus sind kryptografisch starke Software-PRNGs normalerweise sehr langsam.

    Für die Simulation gibt es noch eine weitere Anforderung.
    • Wiederholbarkeit. Der Status der Simulation kann zu jedem Zeitpunkt ihres Betriebs auf der Festplatte am Speicherpunkt (englischer Prüfpunkt) gespeichert, auf eine andere Maschine übertragen und dort wiederhergestellt werden. Darüber hinaus muss die Möglichkeit einer Umkehrung des Zeitablaufs befürwortet werden , und der Verlauf aller Prozesse, einschließlich der aus den PRNG-Nummern hervorgehenden, muss wiederholt werden. Dies bedeutet, dass die Simulation den Wert des internen Zustands des Generators speichern muss.


    Probleme mit rand ()


    Der allererste und im Allgemeinen unbrauchbare Generator sah ungefähr so ​​aus:

    // Seed initialisieren
    int seed = ...;
    Srand (Samen);
    uint64 bad_rand () {
    	return rand ();
    }
    


    Es gibt nicht einmal einen Hinweis auf Wiederholbarkeit - obwohl der Startpunkt zu Beginn der Arbeit klar festgelegt ist und die Reihenfolge immer gleich ist, wird die Simulation beim Zurücksetzen auf den vorherigen Status nicht wiederholt, da der Status des Generators während der Arbeit nicht gesteuert wird. Zusätzlich hat bad_rand () andere Probleme, die den unten beschriebenen ähnlich sind. Wir werden in Zukunft nicht mehr darauf zurückkommen.
    Dann wurde der Code zum Erzeugen einer 64-Bit-Zufallszahl folgendermaßen umgeschrieben:

    uint64 unix_rand (uint64 * state) {
    	srand (* state);
    	uint32 r1 = rand ();
    	Srand (r1);
    	uint32 r2 = rand ();
    	* state = r2;
    	uint64 Ergebnis = ((uint64) r2 << 32) | r1;
    	Ergebnis zurückgeben;
    }
    


    Da der Standard rand () von Libc ein int zurückgibt, das im schlimmsten Fall 32 Bit breit ist, wurden zwei aufeinanderfolgende Aufrufe und eine Kombination davon zu einer 64-Bit-Zahl verwendet. Da rand () den Wert seines internen Zustands nicht zurückgibt, mussten wir ihn jedes Mal mit srand () setzen.
    Dieser Ansatz war aus mehreren Gründen immer noch schlecht.
    1. Abhängigkeit der höchsten Hälfte der Bits vom jüngsten. Als Keim für die höchsten 32 Bits wirken die niedrigeren, d.h. Teile der Zahl sind durch eine funktionale Abhängigkeit verbunden, die erkannt werden kann, d.h. Zufälligkeit zeigen.
    2. RAND_MAX auf meinem System war 2 31 -1. Das heißt eigentlich produziert rand () nur 31 bits! Und in der letzten Zahl ändern sich nur 62 Bits, die 31. und 63. sind immer Nullen.
    3. Der schwerwiegendste Fehler ist die Unsicherheit der rand () -Funktion. Im Allgemeinen kann nicht gesagt werden, ob RAND_MAX auf allen Systemen gleich ist. Sie können nicht einmal sagen, dass die Implementierung von rand () unter Windows und Linux identisch sein wird. Sie hängt nicht von der Bittiefe des Betriebssystems, der Libc-Version, des Compilers oder anderen Faktoren ab. Dieselbe Simulation, die auf verschiedenen Hostsystemen ausgeführt wird, führt zu unterschiedlichen Ergebnissen. Ein Albtraum zum Debuggen!


    Neue Lösung


    Schließlich haben wir den Code in das folgende Formular gebracht:

    const uint64 a1 = ...;
    const uint64 c1 = ...;
    const uint64 a2 = ...;
    const uint64 c2 = ...;
    uint64 two_lcg_rnd (uint64 * state1, uint64 * state2) {
    	uint64 r1 = a1 * * state1 + c1;	
    	uint64 r2 = a2 * * state2 + c2;
    	* state1 = r1;
    	* state2 = r2;
    	uint64 result = (r2 & 0xffffffff000000ull) | (r1 >> 32);
    	Ergebnis zurückgeben;
    }
    


    • Wir haben zwei lineare Kongruenzgeneratoren (engl. LCG) der Form f (x) = a * x + c mod 2 64 verwendet . Die Stärken und Schwächen dieser Art von LCG sind gut bekannt, und Berechnungen in ganzen Zahlen, die modulo eine Zweierpotenz sind, sind schnell.
    • Die Konstanten a1, a2, c1, c2 werden so gewählt, dass die LCG-Perioden groß sind. Interessenten finden ihre Bedeutungen leicht im Internet.
    • Damit die Generatoren unabhängig sind, werden a1! = A2, c1! = C2 und zwei unabhängige Variablen als interner Zustand verwendet. Diese Vorsichtsmaßnahmen garantieren jedoch keine Unabhängigkeit. Eine empirische Überprüfung ist erforderlich.
    • Jedes der zurückgegebenen 64-Bit-LCGs verwendet nur die höchstwertigen 32 Bit. Die unteren Bits von LCG haben eine deutlich kürzere Periode, sodass sie verworfen werden.


    Die Verwendung unserer eigenen Funktion für das PRNG erspart uns den schwer fassbaren Fehler - Nichtdeterminismus der Simulation. Aber wie zufällig ist das Problem?

    Empirische Verifikation


    Das Prinzip der empirischen Analyse G (P) MF ist die Berechnung der Eingabesequenz von Statistiken, die die Wahrheit einer Hypothese über die Art ihres Verhaltens bestimmt. Sie können zum Beispiel die Gleichverteilung von Paaren (Tripel, Vierer ...) benachbarter Zahlen, das Fehlen von Perioden mit monotonem Wachstum und Rückgang usw. überprüfen. Für ein echtes RNG sollte keine dieser Hypothesen mit ausreichender Sicherheit bestätigt werden. Je mehr unterschiedliche Statistiken ein bestimmter PRNG durchläuft, desto höher ist seine Qualität. Wenn Sie daran interessiert sind, die Qualität des RNG aus verschiedenen populären Programmen zu vergleichen, empfehle ich, [1] zu lesen.

    Es gibt verschiedene Pakete für die RNG-Forschung, darunter Dieharder [2] und NIST SP 800-22 [7]. Ich habe das TestU01-Paket [1] verwendet. Es wurden drei Testgruppen vordefiniert, die sich in der Anzahl der eingecheckten Statistiken unterscheiden: SmallCrush, Crush und BigCrush. Jeder der darin enthaltenen Untertests gibt den p-Wert der Zahl aus dem Halbintervall [0,1] an. Um die Teilprüfung zu bestehen, muss sie gleichzeitig weit von Null und von der Einheit entfernt sein.

    Ich habe das mittelgroße Crush-Set verwendet, das in all meinen Experimenten eine halbe bis zwei Stunden dauerte. Ich habe die Programme auf einem solchen System gestartet:
    CPU: Intel Core (TM) i5-4300U CPU bei 1,90 GHz
    uname -a: CYGWIN_NT-6.3 Hostname 1.7.31 (0.272 / 5/3) 2014-07-25 11:26 x86_64 Cygwin

    Für den zweiten Generator basierend auf rand () sind die Ergebnisse bedauerlich: 139 von 144 Tests sind fehlgeschlagen:
    Versteckter Text
    ========= Zusammenfassende Ergebnisse von Crush =========
     Version: TestU01 1.2.3
     Generator: unix_rand
     Anzahl der Statistiken: 144
     Gesamt-CPU-Zeit: 00: 46: 32.40
     Die folgenden Tests ergaben p-Werte außerhalb von [0,001, 0,9990]:
     (eps bedeutet einen Wert <1.0e-300):
     (eps1 bedeutet einen Wert <1.0e-15):
           P-Wert testen
     ----------------------------------------------
      1 SerialOver, t = 2 eps
      2 SerialOver, t = 4 eps
      3 CollisionOver, t = 2 eps
      4 CollisionOver, t = 2 eps
      5 CollisionOver, t = 4 eps
      6 CollisionOver, t = 4 eps
      7 CollisionOver, t = 8 eps
      8 CollisionOver, t = 8 eps
      9 CollisionOver, t = 20 eps
     10 CollisionOver, t = 20 eps
     11 BirthdaySpacings, t = 2 eps
     12 BirthdaySpacings, t = 3 eps
     13 BirthdaySpacings, t = 4 eps
     14 BirthdaySpacings, t = 7 eps
     15 BirthdaySpacings, t = 7 eps
     16 BirthdaySpacings, t = 8 eps
     17 BirthdaySpacings, t = 8 eps
     18 ClosePairs NP, t = 2 3.2e-157
     18 ClosePairs mNP, t = 2 3.2e-157
     18 ClosePairs mNP1, t = 2 eps
     18 ClosePairs mNP2, t = 2 eps
     18 ClosePairs NJumps, t = 2 eps
     19 ClosePairs NP, t = 3 3.2e-157
     19 ClosePairs mNP, t = 3 3.2e-157
     19 ClosePairs mNP1, t = 3 eps
     19 ClosePairs mNP2, t = 3 eps
     19 ClosePairs NJumps, t = 3 eps
     19 ClosePairs mNP2S, t = 3 eps
     20 ClosePairs NP, t = 7 1.8e-79
     20 ClosePairs mNP, t = 7 1.8e-79
     20 ClosePairs mNP1, t = 7 eps
     20 ClosePairs mNP2, t = 7 eps
     20 ClosePairs NJumps, t = 7 eps
     20 ClosePairs mNP2S, t = 7 eps
     21 ClosePairsBitMatch, t = 2 6.9e-65
     22 ClosePairsBitMatch, t = 4 7.5e-143
     23 SimpPoker, d = 16 eps
     24 SimpPoker, d = 16 eps
     25 SimpPoker, d = 64 eps
     26 SimpPoker, d = 64 eps
     27 CouponCollector, d = 4 eps
     28 CouponCollector, d = 4 eps
     29 CouponCollector, d = 16 eps
     30 CouponCollector, d = 16 eps
     31 Lücke, r = 0 eps
     32 Lücke, r = 27 eps
     33 Lücke, r = 0 eps
     34 Lücke, r = 22 eps
     35 Lauf von U01, r = 0 eps
     36 Lauf von U01, r = 15 eps
     37 Permutation, r = 0 eps
     38 Permutation, r = 15 eps
     39 CollisionPermut, r = 0 eps
     40 CollisionPermut, r = 15 eps
     41 MaxOft, t = 5 eps
     41 MaxOft AD, t = 5 3.2e-157
     42 MaxOft, t = 10 eps
     42 MaxOft AD, t = 10 1,8e-79
     43 MaxOft, t = 20 eps
     43 MaxOft AD, t = 20 1 - eps1
     44 MaxOft, t = 30 eps
     44 MaxOft AD, t = 30 1 - eps1
     45 SampleProd, t = 10 1 - eps1
     46 SampleProd, t = 30 1 - eps1
     47 SampleMean eps
     48 SampleCorr 1 - eps1
     49 AppearanceSpacings, r = 0 1 - eps1
     50 AppearanceSpacings, r = 20 1 - eps1
     51 WeightDistrib, r = 0 eps
     52 WeightDistrib, r = 8 eps
     53 WeightDistrib, r = 16 eps
     54 WeightDistrib, r = 24 eps
     55 SumCollector eps
     56 MatrixRank, 60 x 60 eps
     57 MatrixRank, 60 x 60 eps
     58 MatrixRank, 300 x 300 eps
     60 MatrixRank, 1200 x 1200 eps
     62 Savir2 eps
     63 GCD, r = 0 eps
     64 GCD, r = 10 eps
     65 RandomWalk1 H (L = 90) eps
     65 RandomWalk1 M (L = 90) eps
     65 RandomWalk1 J (L = 90) eps
     65 RandomWalk1 R (L = 90) eps
     65 RandomWalk1 C (L = 90) eps
     66 RandomWalk1 H (L = 90) eps
     66 RandomWalk1 M (L = 90) eps
     66 RandomWalk1 J (L = 90) eps
     66 RandomWalk1 R (L = 90) eps
     66 RandomWalk1 C (L = 90) eps
     67 RandomWalk1 H (L = 1000) eps
     67 RandomWalk1 M (L = 1000) eps
     67 RandomWalk1 J (L = 1000) eps
     67 RandomWalk1 R (L = 1000) eps
     67 RandomWalk1 C (L = 1000) eps
     68 RandomWalk1 H (L = 1000) eps
     68 RandomWalk1 M (L = 1000) eps
     68 RandomWalk1 J (L = 1000) eps
     68 RandomWalk1 R (L = 1000) eps
     68 RandomWalk1 C (L = 1000) eps
     69 RandomWalk1 H (L = 10000) eps
     69 RandomWalk1 M (L = 10000) eps
     69 RandomWalk1 J (L = 10000) eps
     69 RandomWalk1 R (L = 10000) eps
     69 RandomWalk1 C (L = 10000) eps
     70 RandomWalk1 H (L = 10000) eps
     70 RandomWalk1 M (L = 10000) eps
     70 RandomWalk1 J (L = 10000) eps
     70 RandomWalk1 R (L = 10000) eps
     70 RandomWalk1 C (L = 10000) eps
     71 LinearComp, r = 0 1 - eps1
     71 LinearComp, r = 0 1 - eps1
     73 LempelZiv 1 - eps1
     74 Fourier3, r = 0 eps
     75 Fourier3, r = 20 eps
     76 LongestHeadRun, r = 0 eps
     76 LongestHeadRun, r = 0 1 - eps1
     77 LongestHeadRun, r = 20 eps
     77 LongestHeadRun, r = 20 1 - eps1
     78 PeriodsInStrings, r = 0 eps
     79 PeriodsInStrings, r = 15 eps
     80 HammingWeight2, r = 0 eps
     82 HammingCorr, L = 30 eps
     83 HammingCorr, L = 300 eps
     84 HammingCorr, L = 1200 eps
     85 HammingIndep, L = 30 eps
     86 HammingIndep, L = 30 eps
     87 HammingIndep, L = 300 eps
     88 HammingIndep, L = 300 eps
     89 HammingIndep, L = 1200 eps
     90 HammingIndep, L = 1200 eps
     91 Bitlauf, r = 0 eps
     91 Bitlauf, r = 0 eps
     92 Bitlauf, r = 20 eps
     92 Bitfolge, r = 20 1 - eps1
     93 AutoCor, d = 1 1 - eps1
     94 AutoCor, d = 1 eps
     95 AutoCor, d = 30 1 - eps1
     96 AutoCor, d = 10 1 - 5,2e-10
     ----------------------------------------------
     Alle anderen Tests wurden bestanden
    




    Für einen neuen Generator, der auf zwei unabhängigen Flüssiggasgeneratoren basiert, ist das Bild besser:
    Versteckter Text
    ========= Zusammenfassende Ergebnisse von Crush =========
     Version: TestU01 1.2.3
     Generator: two_lcg_rnd
     Anzahl der Statistiken: 144
     Gesamt-CPU-Zeit: 00: 46: 13.21
     Die folgenden Tests ergaben p-Werte außerhalb von [0,001, 0,9990]:
     (eps bedeutet einen Wert <1.0e-300):
     (eps1 bedeutet einen Wert <1.0e-15):
           P-Wert testen
     ----------------------------------------------
      1 SerialOver, t = 2 eps
      2 SerialOver, t = 4 eps
      8 CollisionOver, t = 8 1 - 8.0e-13
     13 BirthdaySpacings, t = 4 1.2e-82
     15 BirthdaySpacings, t = 7 eps
     16 BirthdaySpacings, t = 8 eps
     17 BirthdaySpacings, t = 8 eps
     ----------------------------------------------
     Alle anderen Tests wurden bestanden
    



    Nur 7 von 144 Tests sind fehlgeschlagen. Nicht schlecht, obwohl ich aus kryptografischen Gründen davon abraten werde, diesen PRNG zu verwenden. Ich stelle fest, dass die einzelnen "Hälften" dieses Generators auch nicht die gleichen Arten von Untertests bestanden haben.

    Aus Neugier führte ich TestU01 (den längsten BigCrush) für die Sequenz aus, die von der RDRAND-Anweisung auf derselben CPU ausgegeben wurde:
    Versteckter Text
    ========= Zusammenfassende Ergebnisse von BigCrush =========
     Version: TestU01 1.2.3
     Generator: rdrand
     Anzahl der Statistiken: 160
     Gesamt-CPU-Zeit: 15: 58: 06.92
     Die folgenden Tests ergaben p-Werte außerhalb von [0,001, 0,9990]:
     (eps bedeutet einen Wert <1.0e-300):
     (eps1 bedeutet einen Wert <1.0e-15):
           P-Wert testen
     ----------------------------------------------
      1 SerialOver, r = 0 eps
      2 SerialOver, r = 22 eps
     76 RandomWalk1 J (L = 1000, r = 0) 1,7e-4
     ----------------------------------------------
     Alle anderen Tests wurden bestanden
    


    Nachdem wir die Antwort auf die Frage gefunden haben, warum TestU01 selbst auf einem „echten“ Zufallsgenerator mehrere Fehler verursacht, überlassen wir es den zukünftigen Forschern, obwohl ich eine Hypothese zu diesem Thema habe.

    Fazit


    Das Thema, Pseudozufallszahlen zu generieren und auf Zufälligkeit zu prüfen, ist unglaublich aufregend. Allen Interessierten empfehle ich, das entsprechende Kapitel aus dem zweiten Band von D. Knut [5] zu lesen, sofern Sie dies noch nicht getan haben. Das Problem der Verwendung von RNG für die Anforderungen der Simulation und nicht nur für Computersysteme wird in [9] erörtert.

    Literatur


    1. Pierre L'Ecuyer und Richard Simard. 2007. TestU01: AC-Bibliothek zum empirischen Testen von Zufallszahlengeneratoren. ACM Trans. Mathe. Softw. 33, 4, Artikel 22 (August 2007). DOI = 10.1145 / 1268776.1268777 simul.iro.umontreal.ca/testu01/tu01.html
    2. Robert G. Brown, Dirk Eddelbüttel, David Bauer. Dieharder: Eine Zufallszahlen-Testsuite Version 3.31.1 www.phy.duke.edu/~rgb/General/dieharder.php
    3. Intel Corporation. Intel 810 Chipset Design Guide, Juni 1999. download.intel.com/design/chipsets/designex/29065701.pdf
    4. Der Random Number Der Digital Intel Generator (DRNG) Software Implementation Guide Review - software.intel.com/en-us/articles/intel-digital-random-number-generator-drng-software-implementation-guide
    5. Donald Knut. Die Kunst des Programmierens. Band 2. Die resultierenden Algorithmen. Dritte Ausgabe - 2011 - Williams. ISBN 978-5-8459-0081-4,
    6. Kryptographie-Forschung, Inc. Bewertungszusammenfassung: VIA C3 Nehemiah Zufallszahlengenerator - 2003 - www.cryptography.com/public/pdf/VIA_rngsum.pdf
    7. Nationales Institut für Standards und Technologie. Eine statistische Testsuite für Zufalls- und Pseudozufallszahlengeneratoren für kryptografische Anwendungen - 2010 csrc.nist.gov/publications/nistpubs/800-22-rev1a/SP800-22rev1a.pdf
    8. Alin Suciu, Tudor Carean. Benchmarking des True Random Number Generators von TPM-Chips. arxiv.org/ftp/arxiv/papers/1008/1008.2223.pdf
    9. Handbuch der Simulation. Prinzipien, Methodik, Fortschritte, Anwendungen und Praxis / Ed. J. Banks. - John Wiley & Sons, Inc., 1998 - ISBN 0-471-13403-1. - URL: books.google.com/books?id=dMZ1Zj3TBgAC





    Jetzt auch beliebt: