Gibt es "gute" PRNG, die Werte ohne versteckten Zustand erzeugen?

Question

Ich brauche einen guten Pseudozufallszahlengenerator, der wie eine reine Funktion aus seiner vorherigen Ausgabe ohne Verstecken des Zustands berechnet werden kann. Unter „gut“ Ich meine:

1. muss ich in der Lage sein Generator in einer solchen Art und Weise parametrisieren, dass es für 2^n Iterationen mit beliebigen Parametern (oder mit einigen großen Teilmenge davon) laufen alle oder fast alle Werte abdecken sollte zwischen 0 und 2^n - 1, wobei n die Anzahl der Bits im Ausgabewert ist.

2. Combined Generatorleistung von n + p Bits müssen alle abdecken oder fast alle Werte zwischen 0 und 2^(n + p) - 1 wenn ich laufe es für 2^n Iterationen für jede mögliche Kombination der Parameter, wo p die Anzahl der Bits in Parameter ist.

beispielsweise LCG kann wie eine reine Funktion berechnet werden, und es kann erste Bedingung erfüllen, aber es kann nicht die zweite erfüllen. Sagen wir, wir haben 32-Bit-LCG, m = 2^32 und es ist konstant, unsere p = 64 (zwei 32-Bit-Parameter a und c), n + p = 96, so müssen wir Daten von drei Ints von Ausgabe zu peek, um zweite Bedingung zu erfüllen. Bedauerlicherweise kann die Bedingung nicht erfüllt werden, da die Abfolge von ungeraden und geraden Eingängen in der Ausgabe streng alterniert. Um dies zu überwinden, muss ein versteckter Zustand eingeführt werden, aber das macht die Funktion nicht rein und bricht die erste Bedingung (lange versteckte Periode).

EDIT: Streng genommen, möchte ich Familie von p Bits und mit vollen Zustand von n Bits parametrisiert Funktionen, die jeweils alle möglichen Binärketten von p + n Bits in einer einzigartigen „randomish“ Art und Weise zu erzeugen, nicht nur kontinuierlich (p + n) erhöht wird - Bit int. Parametrisierung erforderlich, um diesen einzigartigen Weg zu wählen.

Will ich zu viel?

Answer 1

Versuchen
Alles, was Sie brauchen, ist Liste der primitiven Polynome.
Periode der Generierung endlichen Feldes auf diese Weise, erzeugt Feld der Größe 2^n-1. Aber Sie können diesen Vorgang verallgemeinern, um alles mit der Periode von k^n-1 zu erzeugen.

Ich habe nicht gesehen, dies umgesetzt, aber alles, was Sie implementieren müssen, ist Zahlen, die durch kleine Anzahl s Verschiebung> n, wobei ggT (s, 2^n-1) == 1. gcd steht für größten gemeinsamen Teiler

Answer 2

Sie können jede Blockchiffre mit einem festen Schlüssel verwenden. Um die nächste Nummer zu generieren, entschlüsseln Sie die aktuelle, inkrementieren Sie sie und verschlüsseln Sie sie erneut. Da Blockchiffren 1: 1 sind, durchlaufen sie notwendigerweise jede Zahl in der Ausgabedomäne, bevor sie wiederholt werden.