Y a-t-il de "bonnes" valeurs de génération PRNG sans état caché?

Question

J'ai besoin d'un bon générateur de nombres pseudo-aléatoires qui peut être calculé comme une fonction pure à partir de sa sortie précédente sans cacher d'état. Sous « bonne » Je veux dire:

1. Je dois être en mesure de paramètrer générateur de telle sorte qu'il en cours d'exécution pour 2^n itérations avec tous les paramètres (ou avec une grande partie d'entre eux) devrait couvrir la totalité ou la quasi-totalité des valeurs entre 0 et 2^n - 1, où n est le nombre de bits dans la valeur de sortie.

2. sortie du générateur combiné de n + p de bits doit couvrir la totalité ou la quasi-totalité des valeurs comprises entre 0 et 2^(n + p) - 1 si je l'exécuter pour 2^n itérations pour toutes les combinaisons possibles de ses paramètres, où p est le nombre de bits dans les paramètres.

Par exemple, LCG peut être calculé comme une fonction pure et il peut répondre à la première condition, mais il ne peut pas répondre à une seconde. Disons, nous avons LCG 32 bits, m = 2^32 et il est constant, notre p = 64 (deux paramètres 32 bits a et c), n + p = 96, donc nous devons jeter un coup d'oeil sur les données par trois ints de sortie pour répondre à la deuxième condition. Malheureusement, la condition ne peut pas être satisfaite à cause d'une séquence strictement alternée d'impairs et d'impairs en sortie. Pour surmonter cela, l'état caché doit être introduit, mais cela rend la fonction non pure et brise la première condition (longue période cachée).

EDIT: à proprement parler, je veux la famille des fonctions paramétrées par p bits, et avec la manière l'état complet de n bits générant chacun toutes les chaînes binaires possibles de p + n bits uniques « randomish », non seulement incrémenter en continu (p + n) - bit int. Paramétrisation nécessaire pour sélectionner cette façon unique.

Est-ce que je veux trop?

Answer 1

Essayez LFSR
Tout ce dont vous avez besoin est la liste des polynômes primitifs.
Période de génération de champ fini de cette manière, génère un champ de taille 2^n-1. Mais vous pouvez généraliser cette procédure pour générer quelque chose avec une période de k^n-1.

Je ne l'ai pas vu cette mise en œuvre, mais tout ce que vous devez mettre en œuvre Croître est un nombre par petit nombre s> n où GCD (s, 2^n-1) == 1. GCD est synonyme de plus grand diviseur commun

Answer 2

Vous pouvez utiliser n'importe quel chiffrement par bloc, avec une clé fixe. Pour générer le numéro suivant, déchiffrez le numéro actuel, incrémentez-le et re-cryptez-le. Comme les chiffrements de bloc sont à 1: 1, ils parcourront nécessairement tous les nombres du domaine de sortie avant de les répéter.