Sie staatenlos Zufallszahlengeneratoren existieren?

Question

Gibt es einen Unterschied zwischen mehreren Zahlen Erzeugen eines einzigen Zufallszahlengenerator (RNG) im Vergleich zu einer Anzahl pro Generator erzeugen und zu verwerfen? Sind beide Implementierungen Zahlen zu erzeugen, die ebenso zufällig sind? Gibt es einen Unterschied zwischen den normalen RNGs und den sicheren RNGs für das?

Ich habe eine Web-Anwendung, die eine Liste von Zufallszahlen im Namen von Kunden generieren sollte. Das heißt, sollten die Zahlen erscheinen auf jedem einzelnen Client-Sicht zufällig sein. Bedeutet das, ich einen separaten Zufall RNG pro Client-Sitzung beibehalten müssen? Oder kann ich über alle Sitzungen einen einzigen RNG teilen? Oder kann ich eine RNG auf einem Pro-Anfrage und erstellen und verwerfen?

UPDATE : Diese Frage bezieht sich auf die Ist eine Teilmenge von einer zufälligen Reihenfolge auch zufällig?

Answer 1

Ein Zufallszahlengenerator hat einen Zustand - das ist eigentlich ein notwendiges Merkmal. Die nächste „random“ Nummer ist eine Funktion der früheren Nummer und der Samen / state. Die Puristen nennen sie Pseudo-Zufallszahlengeneratoren. Die Zahlen werden statistische Tests auf Zufälligkeit passieren, sind aber nicht - eigentlich -. Zufällige

Die Sequenz von Zufallswerten ist endlich und wiederholt sich.

Denken Sie an einem Zufallszahlengenerator als eine Sammlung von Zahlen schlurfend und sie dann aus in zufälliger Reihenfolge zu tun. Das Saatgut wird auf „shuffle“ die Zahlen verwendet. Sobald die Samen festgelegt ist, ist die Folge von Zahlen festen und sehr schwer vorherzusagen. Einige Samen wiederholt früher als andere.

Die meisten Generatoren haben Zeit, die lang genug ist, dass niemand bemerken wird es zu wiederholen. Ein 48-Bit-Zufallszahlengenerator wird mehrere hundert Milliarden Zufallszahl erzeugen, bevor sie wiederholt - mit (AFAIK) jedem 32-Bit-Startwert.

Ein Generator wird nur erzeugen zufällige ähnliche Werte, wenn Sie es einen einzigen Samen geben und lassen Sie es Werte speien. Wenn Sie Samen zu ändern, dann mit dem neuen Startwert erzeugten Zahlen nicht zufällig erscheinen, wenn im Vergleich zu den vorherigen Samen erzeugten Werten - ist alle Wetten ab, wenn Sie Samen ändern. Also nicht.

Ein vernünftiger Ansatz ist einen Generator und „Deal“ zu haben, die Zahlen um zu Ihren verschiedenen Kunden. Verwirren Sie nicht mit dem Erstellen und Verwerfen Generatoren. Verwirren Sie nicht mit wechselnden Samen.

Vor allem nie versuchen, Ihren eigenen Zufallszahlengenerator zu schreiben. Die Einbau-Generatoren in den meisten Sprachbibliotheken sind wirklich gut. Vor allem modernen diejenigen, die mehr als 32 Bits verwendet werden.

Einige Linux-Distributionen haben ein /dev/random und /dev/urandom Gerät. Sie können diese einmal gelesen Ihre Anwendung Zufallszahlengenerator auf Saatgut. Diese haben mehr oder weniger zufällige Werte, aber sie arbeiten durch „Sammeln von Rauschen“ aus zufälligen Systemereignissen. Verwenden Sie sie sparsam, so gibt es viele zufällige Ereignisse zwischen den Anwendungen.

Answer 2

Ich würde empfehlen, einen einzigen Generator mehrfach verwenden. Soweit ich weiß, sind alle Generatoren haben einen Zustand. Wenn Sie einen Generator Samen, setzen Sie seinen Zustand auf etwas bezogen auf das Saatgut. Wenn Sie neue zu halten Laichen, ist es wahrscheinlich, dass die Samen werden Sie nicht so zufällig auswählen, wie die Zahlen unter Verwendung von nur einem Generator erzeugt wird.

Dies gilt vor allem bei den meisten Generatoren ich verwendet habe, die die aktuelle Zeit in Millisekunden als Keim verwendet werden.

Answer 3

Hardware-basierte, true [1], Zufallszahlengeneratoren sind möglich, aber nicht trivial und hat oft niedrigen mittlere Raten. Availablity kann auch ein Problem sein [2]. für „Schrotrauschen“ oder „radioaktiven Zerfall“ in Kombination mit googeln „Zufallszahlengenerator“ sollte einige Hits zurück.

Diese Systeme müssen nicht Zustand zu halten. Wahrscheinlich nicht, was Sie suchen.

Wie bereits von anderen erwähnt, Software-Systeme sind nur pseudo-zufällige und muss Status halten.

Ein Kompromiss ist eine Hardware-basierte RNG zu verwenden, um einen Entropie-Pool (gespeicherten Zustand) zu schaffen, die ein PRNG Saatgut zur Verfügung gestellt wird. Dies wird ganz explizit in der Linux-Implementierung von / dev / random getan [3] und / dev / urandom [4].

Diese

ist einige Argument darüber, wie zufällig die Standard-Eingänge in das Verzeichnis / dev / random Entropiepool wirklich sind.

---

Fußnoten:

1. Modulo irgendwelche Probleme mit unserem Verständnis der Physik
2. , weil Sie für einen zufälligen Prozess warten
3. / dev / random Funktionen direkten Zugriff auf die aus verschiedenen Quellen ausgesät Entropiepool glaubte wirklich, oder fast zufällig zu sein, und blockiert, wenn die Entropie erschöpft ist
4. / dev / urandom ist wie / dev / random, aber wenn der entopy erschöpft ist ein kryptographischer Hash verwendet wird, die die Entropie-Pool effektiv eine Stateful PRNG
macht

Answer 4

Wenn Sie eine RNG erstellen und eine einzelne Zufallszahl erzeugen daraus dann die RNG verwerfen, erzeugt die Zahl ist nur so zufällig wie die Samen der RNG starten verwendet.

Es wäre viel besser, einen einzigen RNG zu erstellen und viele Zahlen daraus ziehen.

Answer 5

Da die Menschen haben bereits gesagt, ist es viel besser, die PRNG einmal auf Saatgut und es wiederverwenden. Ein sicherer PRNG ist einfach eine, die für kryptographische Anwendungen geeignet ist. Die einzige Möglichkeit, jedes Mal wieder Impfen geben maßen zufällige Ergebnisse ist, wo es von einer wirklich zufälligen „realen Welt“ Quelle kommt - also spezielle Hardware. Selbst dann ist es möglich, dass die Quelle voreingenommen ist, und es wird noch theoretisch besser sein, die gleiche PRNG zu verwenden, um über.

Answer 6

Normalerweise wird ein neuer Zustand der Aussaat dauert ziemlich lange für eine ernsthafte PRNG und neu zu knüpfen jedes Mal viel nicht wirklich helfen. Der einzige Fall, die ich denken kann, wo Sie wollen vielleicht mehr als ein PRNG für verschiedene Systeme, sagen in einem Casino-Spiel Sie einen Generator für schlurfenden Karten haben und einen separaten Kommentaren durch die Computer-Steuerzeichen, auf diese Weise wirklich getan zu erzeugen gewidmet Benutzer können keine Ergebnisse erraten basierend auf Charakter Verhaltensweisen.

Eine schöne Lösung für die Aussaat zu verwenden ist diese (Random.org) liefern sie zufällig Zahlen aus dem atmosphärischen Rauschen kostenlos erzeugt. Es könnte eine bessere Quelle für die Aussaat sein als die Zeit verwendet wird.

Edit: In Ihrem Fall würde ich auf jeden Fall ein PRNG verwenden pro Kunde, wenn aus keinem anderen Grund, als für eine gute Programmierstandards. Auch immer, wenn Sie einen PRNG bei den Kunden teilen, werden Sie noch pseudo-zufällige Werte zu jeder Bereitstellung sein, von einer Qualität gleich Ihre PRNG Qualität. Also das ist ein gangbarer Weg, aber scheint wie eine schlechte Politik für die Programmierung

Answer 7

Es ist erwähnenswert, dass Haskell ist eine Sprache, die wandelbar Staat vollständig zu beseitigen versucht. Um dieses Ziel mit hart Anforderungen wie IO in Einklang zu bringen (was eine Form der Veränderbarkeit erfordert) muss verwendet werden Monaden Zustand von einer Berechnung zum nächsten fädeln. Auf diese Weise implementiert Haskell seine Pseudo-Zufallszahlengenerator. Streng genommen Erzeugung von Zufallszahlen ist ein inhärent Stateful-Operation, aber Haskell in der Lage ist, diese Tatsache zu verbergen, indem er den Zustand „Mutation“ in die bind (>>=) -Operation bewegt.

Das klingt wahrscheinlich ein wenig abstrakt, und es antwortet nicht wirklich Ihre Frage vollständig, aber ich denke, es ist immer noch anwendbar ist. Aus theoretischer Sicht ist es unmöglich, mit einem RNG zu arbeiten ohne staatliche Beteiligung. Unabhängig davon gibt es Techniken, die verwendet werden können, um diese Wechselwirkung zu mildern und es erscheint als ob der gesamte Vorgang ist eine staatenlos Natur.

Answer 8

Es ist im Allgemeinen besser, einen einzigen PRNG zu erstellen und mehrere Werte aus ihr ziehen. mehrere Instanzen schaffen heißt müssen Sie sicherstellen, dass die Samen für die Instanzen sind garantiert einzigartig, die instanzspezifische Informationen enthält, wird erforderlich.

Als Nebenwirkung, es gibt bessere „true“ Zufallszahlengeneratoren, aber sie erfordern in der Regel spezialisierte Hardware, die Dinge tut wie ableiten Zufallsdaten aus elektrischen Signalvarianz im Inneren des Computers. Es sei denn, Sie wirklich darüber besorgt sind, dann würde ich die Pseudozufallszahlengeneratoren in die Sprachbibliotheken gebaut sagen und / oder OS sind wahrscheinlich ausreichend, solange Ihr Startwert nicht leicht vorhersehbar ist.

Answer 9

Die Verwendung eines sicheren PRNG hängt von Ihrer Anwendung. Was sind die Zufallszahlen verwendet? Wenn sie etwas von wirklichem Wert (zum Beispiel etwas kryptographisch verwandt) sind, dann würden Sie nicht wollen, weniger etwas verwenden.

Sichere PRNGs sind viel langsamer und können Bibliotheken erfordern Betrieb beliebiger Genauigkeit zu tun, und Primtests, etc etc ...

Answer 10

Nun, solange sie anders ausgesät sind jedesmal, wenn sie erstellt sind, dann nein, ich glaube nicht, dass es keinen Unterschied geben würde; jedoch, wenn er auf so etwas wie die Zeit abhing, dann würden sie wahrscheinlich nicht einheitlich sein, aufgrund des vorgespannten Samen.