Normalerweise erzeugt man Pseudozufallszahlen und keine echten Zufallszahlen, obwohl beide mit unterschiedlichen Raten möglich sind.
Es gibt zwei allgemeine Kategorien, abhängig davon, ob die Sequenz für kryptografische Zwecke verwendet wird. Der Hauptunterschied besteht darin, ob die Kenntnis einer Zahl in der Sequenz die Vorhersage des nächsten ermöglicht. Allzweck-RNGs machen sich keine Gedanken darüber, ob die Kenntnis des Algorithmus es einem Beobachter ermöglichen würde, die Sequenz zu duplizieren, und sie laufen viel schneller.
Ein typischer Allzweck-RNG-Algorithmus ist der Mersenne Twister . Es gibt viele öffentliche Implementierungen verschiedener Algorithmen. Siehe hier für eins.
Wenn der MT zu viel Speicher benötigt, ist ein halbwegs brauchbarer Fallback der lineare Kongruenzgenerator . (Das MT wurde erst 1997 erfunden.) Dieser Generator hat bestimmte Probleme, aber er benötigt fast keinen Speicher, fast keinen Code und ist extrem schnell. Implementierungen gibt es überall, und es wurde ausführlich in Knuths Seminumerischen Algorithmen behandelt.
Um einen RNG zu säen, benötigen Sie eine Entropiequelle, siehe Ссылка (Hinweis: SO wird verwirrt über die () 's in dieser Verbindung.) Dies wird in der Regel durch das Timing von Ereignissen, die die CPU beobachten kann, wie Tastenanschläge, (ich denke, das wird nicht für Sie arbeiten) Interrupts und Paketankünfte abgeleitet. Eine Echtzeituhr ist oft eine akzeptable Quelle, wenn sie ihren eigenen Zustand beibehält, da Neustarts selten in irgendeiner Art und Weise zeitlich aufeinander abgestimmt sind.
Wenn Sie Zugriff auf einen ADC haben, können Sie das niedrigstwertige Bit daraus lesen und es als Startwert für einen Pseudo-Zufallszahlengenerator verwenden, wie andere es geschrieben haben. Offensichtlich müssen Sie mehr als ein Bit vom ADC lesen, so dass mehrere Lesevorgänge erforderlich sind, was eine Weile dauern kann. Sie müssen dies jedoch nur einmal beim Start durchführen und dann schneller PRNG verwenden, um neue Zufallszahlen zu generieren.
Viele eingebettete Geräte haben im ADC eingebaut, zum Beispiel die ATMega-Familie von Atmel.
Wenn die Hardware eine Taste für den Benutzer hat, ist es ein einfacher Trick, zu zählen, wie lange die Taste gedrückt wird. Mit einem schnell genug kurzen Zähler erhalten Sie eine "zufällige" Nummer.
Pseudozufallszahlengeneratoren, die am schnellsten und am wenigsten anspruchsvoll sind w.r.t. Der Befehlssatz (nur shift und xor, keine Multiplikation oder Division) sind kleinere Varianten der Mersenne-Twister-Idee (als verallgemeinertes lineares Rückkopplungsschieberegister bezeichnet). Mersenne Twister selbst benötigt zu viel Speicher für Mikrocontroller.
Das Problem mit diesen Generatoren ist, dass sie lange Sequenzen nahe Null erzeugen können, wenn Sie Pech haben. Mit einer angemessenen Größe des Zustandsraums und der Initialisierung von einem anderen PNRG ist dies jedoch unwahrscheinlich.
Sie sind auch nicht sicher für Kryptographie oder Glücksspiel, ein intelligenter Gegner kann zukünftige Zustände vorhersagen, nachdem er die Ausgabe beobachtet hat. Dies liegt daran, dass sie linear sind.
Ich habe einmal einen solchen Generator für einen kleinen Nicht-Standard-Prozessor mit einem Zustandsraum von ungefähr 50 24-Bit-Wörtern entworfen. Ich habe Varianten mit der Diehard Testsuite getestet, bis ich eine gute gefunden habe. Die Anwendung erzeugte zufällige Variationen für einen Hardwaretest.
Lesen des Timers und xoring / nanding / etc mit einer Reihe von Bits geben dem Benutzer ein halb zufälliges Ergebnis, da das Timing zwischen den Ereignissen wahrscheinlich so weit auseinander liegen wird, dass der Benutzer es nicht wirklich sagen kann Korrelation mit dem Timer.
Wenn Sie einen potentialfreien Kontakt belassen können, könnte es hilfreich sein, Zufallszahlen mit linearem Rückkopplungsschieberegister zu erzeugen. Ich bin mir nicht sicher, ob das der richtige Weg ist, aber sehen Sie sich bitte meinen Code an:
%Vor%BEARBEITEN: Ich habe herausgefunden, dass meine Antwort schlecht sein kann. Weitere Details dazu, warum sollten Sie keinen schwimmenden digitalen Pin verwenden: Ссылка
Tags und Links random microcontroller