it-swarm-eu.dev

Wie funktionieren Zufallszahlengeneratoren?

Ich habe nur über die Funktion php Rand() nachgedacht und darüber nachgedacht, wie ich sie neu erstellen könnte, und bin völlig verblüfft aufgetaucht.

Wie funktionieren Zufallszahlengeneratoren?

24
Korvin Szanto

Zufallszahlengeneratoren (RNGs) erzeugen wirklich Pseudozufallszahlen, da es unmöglich ist, tatsächlich eine WIRKLICHE Zufallszahl zu erzeugen. Die einzigen wirklich wirklich zufälligen Dinge sind höhere Gewalt wie Blitze.

Dieser Wikipedia-Artikel kann Ihnen möglicherweise bei der Erklärung helfen: http://en.wikipedia.org/wiki/Random_number_generators


Soweit ich weiß, gibt es im Grunde zwei Teile eines RNG: den Samen und dann die Zufallszahl, die aus diesem Samen ausgewählt wurde. Wenn Sie das RNG setzen, geben Sie ihm ein Äquivalent zu einem Startpunkt. Dieser Startpunkt enthält dann eine Reihe von Zahlen, die "innerhalb" des Programms liegen. In PHP können Sie srand () verwenden, um die Seeds zu "mischen", sodass Sie fast immer eine andere Antwort erhalten. Sie können dann Rand (min, max) verwenden, um in den Startwert zu gehen und eine Zahl zwischen min und max einschließlich zu wählen.


WARNUNG, MÖGLICHE KÄSEANALOGIE VORAUS!

Stellen Sie sich jeden Samen als Eiskiste vor und dann die Zufallszahlen als Eiswürfel. Angenommen, Sie haben 1000 Eiskisten und jede Truhe enthält 1000 Eiswürfel. Auf dem Jahrmarkt wählen sie eine Eiskiste aus, die sie für Getränke verwenden möchten, und sie können nur einen Eiswürfel verwenden. Sie benötigen jedoch nur Eiswürfel, die größer als 1 Kubikzoll sind. Also wählen sie zufällig eine Truhe zwischen diesen 1000 Truhen und dann zufällig einen Eiswürfel in dieser Truhe. Wenn es für die gewünschte Größe funktioniert, verwenden sie es. Wenn nicht, legen sie es mit den anderen zurück in die Brust. Wenn sie es ein bisschen lustiger machen wollen, wechseln sie vorher die Truhe, um es völlig zu vergessen, wenn Sie so wollen!

Wie PHP wählt tatsächlich physisch den Startwert und die Zufallszahl aus, ich habe nicht genug Wissen dafür (worüber Sie sich wahrscheinlich am meisten gewundert haben!). Ich würde nicht Versuchen Sie, die Rand () - Funktion zu wiederholen. Für die meisten webbasierten Anwendungen, die Sie erstellen, sollte Rand () für jede benötigte Zufallszahl ausreichen.

Schauen Sie sich auch lineare Kongruenzgeneratoren an. Dies ist möglicherweise eher das, wonach Sie suchen, wenn Sie schmutzige Details wünschen: http://en.wikipedia.org/wiki/Linear_congruential_generator

Hoffe das hilft!

7
Mr. Starburst

Sie sind normalerweise nicht wirklich zufällig, werden aber als pseudozufällig bezeichnet, da sie eine Zahlenfolge erzeugen, die zufällig erscheint. Dies geschieht mit einigen interessanten mathematischen Formeln. Einer der häufigsten ist der Linear Congruential Generator .

Pseudozufallszahlen haben eine nützliche Eigenschaft, die echte Zufallszahlen nicht haben: Wenn Sie zu Beginn denselben Startwert verwenden, erhalten Sie eine identische Sequenz zurück. Dies kann zum Testen sehr praktisch sein.

18
Mark Ransom

Fragen Sie nach Pseudozufall oder Zufall? Andere antworteten über Pseudozufall, lassen Sie mich über Random sprechen.

Es gab (gibt?) Tatsächliche hardwarebasierte Zufallszahlengeneratoren im Verkauf. Sie basierten auf einem Chip mit einem kleinen Funkgerät, das weißes Rauschen der Weltraumstrahlung misst, oder einer kleinen radioaktiven Probe und Messperioden zwischen ihrem Zerfall. Das Problem bei ihnen war die Bandbreite - die Menge an Entropie, die sie erzeugen konnten, war nicht sehr hoch, so dass sie für Keime von Pseudozufallsalgorithmen verwendet wurden. Sie wurden in Bankensystemen, Hochsicherheitsanlagen und dergleichen eingesetzt.

OTOH, wenn Sie einen Entwickler eingebetteter Systeme treffen, werden diese darüber lachen. Für übliche Zwecke beim Programmieren eines Mikrocontrollers erzeugt das Lesen von niedrigen 4 Bits eines 16-Bit-Analog-Digital-Wandlers mit einem schwebenden (nicht verbundenen) Pin ein vollkommen gutes Zufallsrauschen bei mehr als ausreichender Bandbreite (je kürzer die Abfrageperiode, desto mehr " laut "das Auslesen) und einfacher als das Schreiben der eigentlichen RNG-Routine. Und wenn man bedenkt, dass ADCs häufig in Silizium von Mikrocontrollern implementiert, häufig implementiert und häufig mit 8 Kanälen implementiert sind, von denen Sie vielleicht 5 für Ihre Anwendung benötigen, ist dies praktisch kostenlos.

Und selbst wenn Sie keinen ADC haben, erzeugen einige Elemente, die an einen digitalen GPIO-Pin angeschlossen sind, ein ziemlich gutes Rauschen. In Embedded ist Rauschen allgegenwärtig (und wird ständig bekämpft), so dass es sehr einfach ist, eine echte Zufälligkeit zu erzielen.

4
SF.

Es gibt viele Möglichkeiten, eine "zufällige" Folge von Zahlen zu emulieren. Ihre erste Station sollte sicher sein, über lineare Kongruenzgeneratoren zu lesen. So funktionieren die meisten grundlegenden Zufallszahlengeneratoren, und ich wette, so funktioniert die Rand () - Funktion von PHP.

Die interessantere nächste Frage ist, wie es sich selbst aussät. Zeit? IP Adresse? usw.

2
Sean Owen

Erstens liefern praktisch alle Rand() - Funktionen keine echte Zufälligkeit, sondern sogenannte Pseudozufallszahlen.

Wie funktionieren Pseudozufallszahlengeneratoren? Grundsätzlich funktioniert die Verschlüsselung genauso: Sie haben eine Funktion (einen Hash), die eine Eingabe akzeptiert und eine Ausgabe auf so komplexe Weise erzeugt, dass es unmöglich ist, die Eingabe anhand der Ausgabe zu erraten oder umgekehrt. Das heißt, jede Chiffre kann verwendet werden, um einen ziemlich guten Pseudozufallsgenerator zu erstellen. Während Sie im Prinzip jeden Pseudozufallsgenerator für die Verschlüsselung verwenden können, sind die meisten Pseudozufallszahlengeneratoren in erster Linie auf Geschwindigkeit und nicht auf kryptografische Sicherheit ausgelegt, sodass Hacker keine Kopfschmerzen bekommen.

Für einen Pseudozufallsgenerator wird die Hashing-Funktion auf einen verborgenen internen Zustand des Generators angewendet, und seine Ausgabe wird verwendet, um a) diesen internen Zustand zu modifizieren und b) die Ausgabe der Rand() zu berechnen Funktion. Der nächste Aufruf von Rand() verwendet diesen geänderten internen Zustand und erzeugt somit ein anderes Ergebnis. Je besser die Hash-Funktion ist, desto weniger leicht sind die Ergebnisse von echten Zufallszahlen zu unterscheiden.


Tatsächlich haben Computer heutzutage Zugriff auf echte Zufallszahlen: Sie entstehen durch Jitter beim Timing von Interrupts, die von externen Geräten erzeugt werden. Linux verwendet diese Werte geringer Unsicherheit, um ständig einen "Entropiepool" zu rühren, der nur wenige Kilobyte internen Zustands umfasst. Kryptografische Hashes, die auf diesem Entropiepool basieren, werden über das /dev/random und /dev/urandom Geräte. Der Zugriff auf einige wirklich sehr gute Zufallszahlen ist also so einfach wie das Öffnen eines dieser beiden Geräte und das Lesen einiger Bytes von ihnen.