Liste der Zufallszahlengeneratoren - List of random number generators
Zufallszahlengeneratoren sind in vielen Arten von technischen Anwendungen wichtig, einschließlich Physik , Ingenieurwesen oder mathematischen Computerstudien (zB Monte-Carlo- Simulationen), Kryptographie und Glücksspiel (auf Spieleservern ).
Diese Liste enthält viele gängige Typen, unabhängig von der Qualität.
Pseudozufallszahlengeneratoren (PRNGs)
Wenn Sie einen Pseudozufallszahlengenerator verwenden , denken Sie an John von Neumanns Diktum "Jeder, der arithmetische Methoden zur Erzeugung von Zufallszahlen in Betracht zieht, ist natürlich in einem Zustand der Sünde."
Die folgenden Algorithmen sind Pseudozufallszahlengeneratoren.
Generator | Datum | Erste Befürworter | Verweise | Anmerkungen |
---|---|---|---|---|
Mittelquadratmethode | 1946 | J. von Neumann | In seiner ursprünglichen Form ist es von schlechter Qualität und nur von historischem Interesse. | |
Lehmer-Generator | 1951 | DH Lehmer | Eines der frühesten und einflussreichsten Designs. | |
Linearer Kongruentialgenerator (LCG) | 1958 | WIR Thomson; A. Rotenberg | Eine Verallgemeinerung des Lehmer-Generators und historisch der einflussreichste und untersuchte Generator. | |
Verzögerter Fibonacci-Generator (LFG) | 1958 | GJ Mitchell und DP Moore | ||
Lineares Feedback-Schieberegister (LFSR) | 1965 | RC Tausworthe | Ein sehr einflussreiches Design. Auch Tausworthe-Generatoren genannt. | |
Wichmann–Hügelgenerator | 1982 | BA Wichmann und DI Hill | Eine Kombination aus drei kleinen LCGs, geeignet für 16-Bit-CPUs . In vielen Programmen weit verbreitet, wird zB in Excel 2003 und späteren Versionen für die Excel-Funktion RAND verwendet und war bis Version 2.2 der Standardgenerator in der Sprache Python. | |
Regel 30 | 1983 | S. Wolfram | Basierend auf zellularen Automaten. | |
Inversiver Kongruentialgenerator (ICG) | 1986 | J. Eichenauer und J. Lehn | ||
Park-Miller-Generator | 1988 | SK Park und KW Miller | Eine spezifische Implementierung eines Lehmer-Generators, weit verbreitet, weil in den Sprachen C und C++ als Funktion `minstd' integriert. | |
EICHEL-Generator | (entdeckt 1984) 1989 | RS Wikramaratna | Die A dditive Co ngruential R Andom N umber - Generator.
Einfach zu implementieren, schnell, aber nicht allgemein bekannt. Besteht bei entsprechenden Initialisierungen alle aktuellen empirischen Testsuiten und ist formal nachweislich konvergierend. Einfach erweiterbar für beliebige Periodenlängen und verbesserte statistische Leistung über höhere Dimensionen und mit höherer Genauigkeit. |
|
MIXMAX-Generator | 1991 | GK Savvidy und NG Ter-Arutyunyan-Savvidy | Es ist ein Mitglied der Klasse der linearen kongruenten Matrixgeneratoren, einer Verallgemeinerung von LCG. Das Grundprinzip der MIXMAX-Generatorenfamilie beruht auf Ergebnissen der Ergodik und der klassischen Mechanik. | |
Add-with-Carry (AWC) | 1991 | G. Marsaglia und A. Zaman | Eine Modifikation von Lagged-Fibonacci-Generatoren. | |
Subtrahieren mit Leihen (SWB) | 1991 | G. Marsaglia und A. Zaman | Eine Modifikation von Lagged-Fibonacci-Generatoren. Ein SWB-Generator ist die Basis für den RANLUX-Generator, der zB für Teilchenphysik-Simulationen weit verbreitet ist. | |
Maximal periodische Kehrwerte | 1992 | RAJ Matthews | Eine Methode mit Wurzeln in der Zahlentheorie, die jedoch nie in praktischen Anwendungen verwendet wurde. | |
KUSS | 1993 | G. Marsaglia | Vorbildgerechtes Beispiel eines Kombigenerators. | |
Multiplizieren mit Übertrag (MWC) | 1994 | G. Marsaglia; C. Koç | ||
Komplementär-Multiplizieren-mit-Übertragen (CMWC) | 1997 | R. Couture und P. L'Ecuyer | ||
Mersenne-Twister (MT) | 1998 | M. Matsumoto und T. Nishimura | Eng verwandt mit LFSRs. In seiner MT19937-Implementierung ist es wahrscheinlich das am häufigsten verwendete moderne PRNG. Standardgenerator in R und Python ab Version 2.3. | |
Xorshift | 2003 | G. Marsaglia | Es ist ein sehr schneller Untertyp von LFSR-Generatoren. Marsaglia schlug als Verbesserung auch den Xorwow-Generator vor, bei dem die Ausgabe eines Xorshift-Generators mit einer Weyl-Sequenz addiert wird . Der xorwow-Generator ist der Standardgenerator in der CURAND-Bibliothek der nVidia CUDA- Anwendungsprogrammierschnittstelle für Grafikprozessoren. | |
Gut gleichverteilte langperiodische lineare (WELL) | 2006 | F. Panneton, P. L'Ecuyer und M. Matsumoto | Ein LFSR, das eng mit Mersenne Twister verwandt ist und darauf abzielt, einige seiner Mängel zu beheben. | |
Ein kleines nicht-kryptografisches PRNG (JSF) | 2007 | Bob Jenkins | ||
Erweitertes Randomisierungssystem (ARS) | 2011 | J. Salmon, M. Moraes, R. Dror und D. Shaw | Eine vereinfachte Version der AES-Blockchiffre , die zu einer sehr schnellen Leistung auf Systemen führt, die AES-NI unterstützen . | |
Dreifry | 2011 | J. Salmon, M. Moraes, R. Dror und D. Shaw | Eine vereinfachte Version der Threefish-Blockchiffre, geeignet für GPU-Implementierungen. | |
Philox | 2011 | J. Salmon, M. Moraes, R. Dror und D. Shaw | Eine Vereinfachung und Modifikation der Blockchiffre Threefish mit dem Hinzufügen einer S-Box . | |
SplitMix | 2014 | GL Steele, D. Lea und CH Flood | Basierend auf der endgültigen Mischfunktion von MurmurHash3. In Java Development Kit 8 und höher enthalten. | |
Permutierter Kongruentialgenerator (PCG) | 2014 | ICH O'Neill | Eine Modifikation von LCG. | |
Zufallszyklus-Bitgenerator (RCB) | 2016 | R. Kochmann | RCB wird als ein Bitmustergenerator beschrieben, der gemacht wurde, um einige der Unzulänglichkeiten mit Mersenne Twister und kurze Perioden-/Bitlängenbeschränkung von Schiebe-/Modulogeneratoren zu überwinden. | |
Mittleres Quadrat Weyl-Sequenz RNG | 2017 | B. Widynski | Als Variation von John von Neumanns ursprünglicher Mittelquadratmethode ist dieser Generator möglicherweise der schnellste RNG, der alle statistischen Tests besteht. | |
Xoroshiro128+ | 2018 | D. Blackman, S. Vigna | Eine Modifikation von Marsaglias Xorshift-Generatoren, einem der schnellsten Generatoren auf modernen 64-Bit- CPUs. Zu den verwandten Generatoren gehören xoroshiro128**, xoshiro256+ und xoshiro256**. | |
64-Bit-MELG | 2018 | S. Harase, T. Kimoto | Eine Implementierung von maximal gleichverteilten 64-Bit- F 2 -Lineargeneratoren mit Mersenne-Primärperiode. | |
Quadrate RNG | 2020 | B. Widynski | Eine zählerbasierte Version von Middle Square Weyl Sequence RNG . Ähnlich wie Philox im Design, aber deutlich schneller. |
Kryptografische Algorithmen
Als sehr hochwertige Pseudozufallszahlengeneratoren können Chiffrieralgorithmen und kryptografische Hashes verwendet werden. Im Allgemeinen sind sie jedoch erheblich langsamer (typischerweise um den Faktor 2-10) als schnelle, nicht-kryptografische Zufallszahlengeneratoren.
Diese beinhalten:
- Stromchiffren . Beliebte Wahlen sind Salsa20 oder ChaCha (oft mit einer auf 8 reduzierten Rundenzahl aus Geschwindigkeitsgründen), ISAAC , HC-128 und RC4 .
- Blockchiffren im Zählermodus . Übliche Optionen sind AES (das auf Systemen, die es in Hardware unterstützen, sehr schnell ist ), TwoFish , Serpent und Camellia .
- Kryptografische Hash-Funktionen
Einige wenige kryptographisch sichere Pseudozufallszahlengeneratoren verlassen sich nicht auf Verschlüsselungsalgorithmen, sondern versuchen, die Schwierigkeit, ihre Ausgabe von einem "echten" Zufallsstrom zu unterscheiden, mathematisch mit einem rechentechnisch schwierigen Problem zu verknüpfen. Diese Ansätze sind theoretisch wichtig, aber für die meisten Anwendungen zu langsam, um praktisch zu sein. Sie beinhalten:
- Blum-Micali-Algorithmus (1984)
- Blum Blum Shub (1986)
- Naor-Reingold-Pseudozufallsfunktion (1997)
Zufallszahlengeneratoren, die externe Entropie verwenden
Diese Ansätze kombinieren einen Pseudozufallszahlengenerator (oft in Form einer Block- oder Stromchiffre) mit einer externen Zufallsquelle (z. B. Mausbewegungen, Verzögerung zwischen Tastaturdrücken usw.).
-
/dev/random
- Unix-ähnliche Systeme - CryptGenRandom - Microsoft Windows
- Fortuna
- RDRAND- Anweisungen ( von Intel Intel Secure Key genannt ), die seit 2012 in Intel x86-CPUs verfügbar sind. Sie verwenden den in die CPU integrierten AES-Generator und setzen ihn regelmäßig neu ein.
- Echter Zufallszahlengenerator mit Corona-Entladung.
- Schafgarbe
Zufallszahlenserver
Die folgende (nicht erschöpfende) Liste von Websites behauptet, Zufallszahlen bereitzustellen, die aus einer wirklich zufälligen Quelle generiert wurden, wobei viele zusätzliche Randomisierungsdienste anbieten:
- Australische Nationaluniversität
- HotBits
- Humboldt-Universität zu Berlin (Anmeldung erforderlich)
- random.org
- csrng.net
Bekannte PRNG-APIs
-
/dev/random
auf Unix-ähnlichen Systemen - Zufällige Klasse im .NET Framework
- Zufallsklasse in der Programmiersprache Java
- Zufallsmodul in den Haskell 98-Spezifikationen
- Randomisierungsdienste in den Sprachen Objective-C und Swift
- SecureRandom-Klasse in der Programmiersprache Java
- Web Crypto API für Webbrowser
Siehe auch
- Würfelware
- Diehard tests - Statistische Testsuite für Zufallszahlengeneratoren.
- TestU01 - Statistische Testsuite für Zufallszahlengeneratoren.
- Hardware-Zufallszahlengenerator
- Angriff auf Zufallszahlengenerator
- Zufall
Verweise
Externe Links
- SP800-90-Serie zur Generierung von Zufallszahlen , NIST
- Zufallszahlengenerierung im GNU Scientific Library Reference Manual
- Routinen zur Generierung von Zufallszahlen in der NAG Numerical Library
- Chris Lomonts Überblick über PRNGs, einschließlich einer guten Implementierung des WELL512-Algorithmus
- Quellcode zum Lesen von Daten von einem TrueRNG V2-Hardware-TRNG