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:

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:

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.).

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:

Bekannte PRNG-APIs

Siehe auch

Verweise

Externe Links