Vous recherchez un PRNG de qualité décente avec seulement 32 bits d’état

J’essaie d’implémenter une version de qualité tolérable de l’interface rand_r , qui présente la condition regrettable que son état entier soit stocké dans un seul object de type unsigned , ce qui signifie exactement 32 bits. De plus, j’ai besoin que sa plage de sortie soit [0,2³¹-1] . La solution standard utilise un LCG et supprime le bit faible (qui a la période la plus courte), mais cela laisse encore de très mauvaises périodes pour les bits suivants.

Ma pensée initiale était d’utiliser deux ou trois itérations de la GCL pour générer les bits haut / bas ou haut / moyen / bas de la sortie. Cependant, une telle approche ne préserve pas la dissortingbution non biaisée; au lieu que chaque valeur de sortie ait une fréquence égale, beaucoup se produisent plusieurs fois, et certaines ne se produisent jamais du tout.

Comme il n’y a que 32 bits d’état, la période du PRNG est délimitée par 2³² et, pour être non polarisée, le PRNG doit fournir chaque valeur exactement deux fois si elle a une période complète ou une fois si elle a la période 2³¹. Des périodes plus courtes ne peuvent être non biaisées.

Existe-t-il un algorithme PRNG connu qui réponde à ces critères?

Une bonne possibilité (mais probablement pas la plus rapide) offrant une qualité très élevée serait d’utiliser un chiffrement par bloc de 32 bits en mode CTR . Fondamentalement, votre état RNG serait simplement un compteur 32 bits incrémenté d’un pour chaque appel RNG, et le résultat serait le chiffrement de la valeur de ce compteur en utilisant le chiffrement de bloc avec une clé fixe choisie arbitrairement. Pour plus d’aléatoire, vous pouvez même fournir une fonction (non standard) permettant à l’utilisateur de définir une clé personnalisée.

Il n’ya pas beaucoup de chiffrements de blocs 32 bits couramment utilisés, puisqu’une taille de bloc aussi courte pose des problèmes pour l’utilisation cryptographique. (En gros, le paradoxe de l’ anniversaire permet de distinguer la sortie d’un tel chiffre d’une fonction aléatoire avec une probabilité non négligeable après seulement environ 2 16 = 65536 sorties et après 2 32 sorties, le caractère non aléatoire devient évidemment certain.) certains chiffrements avec une taille de bloc ajustable, tels que XXTEA ou HPC , vous permettront de descendre à 32 bits et devraient convenir à vos besoins.

( Edit: My bad, XXTEA n’a que 64 bits. Toutefois, comme suggéré par CodesInChaos dans les commentaires, Skip32 pourrait être une autre option. Vous pouvez également créer votre propre chiffrement Feistel 32 bits.)

La construction en mode CTR garantit au RNG une période complète de 2 32 sorties, tandis que la revendication de sécurité standard des chiffrements de blocs (non cassés) est essentiellement qu’il n’est pas possible, d’un sharepoint vue calcul, de distinguer leur sortie d’une permutation aléatoire de l’ensemble. des entiers 32 bits. (Bien entendu, comme indiqué ci-dessus, une telle permutation se distingue encore facilement d’une fonction aléatoire prenant des valeurs sur 32 bits.)

L’utilisation du mode CTR fournit également des fonctionnalités supplémentaires que vous jugerez utiles (même si elles ne font pas partie de l’API officielle contre laquelle vous développez), telles que la possibilité de rechercher rapidement n’importe quel point du stream de sortie RNG en ajoutant ou en supprimant soustrayant de l’état.

D’autre part, vous ne voulez probablement pas suivre la pratique habituelle d’ensemencement du GNR en définissant simplement l’état interne sur la valeur de départ, car les stream de sortie générés à partir des graines voisines seraient très similaires (en gros, même stream décalé de la différence des graines). Une façon d’éviter ce problème consiste à append une étape de chiffrement supplémentaire au processus d’amorçage, c’est-à-dire de chiffrer la valeur de départ avec le chiffrement et de définir la valeur du compteur interne égale au résultat.

En élaborant sur mon commentaire …

Un chiffrement par bloc en mode compteur donne à un générateur approximativement la forme suivante (sauf en utilisant des types de données beaucoup plus gros):

 uint32_t state = 0; uint32_t rand() { state = next(state); return temper(state); } 

Comme la sécurité cryptographique n’a pas été spécifiée (et qu’elle serait plus ou moins futile en 32 bits), une fonction de tempérage plus simple et ad-hoc devrait faire l’affaire.

Une approche est celle où la fonction next() est simple (par exemple, return state + 1; ) et où l’ temper() est complexe (comme dans le chiffrement par bloc).

Une approche plus équilibrée consiste à implémenter LCG dans next() , car nous soaps qu’il visite également tous les états possibles, mais dans un ordre aléatoire (ish), et à trouver une implémentation de temper() qui effectue juste assez de travail pour couvrir le rest. problèmes avec LCG.

Mersenne Twister inclut une telle fonction de revenu dans sa sortie. Cela pourrait convenir. En outre, cette question demande des opérations qui remplissent l’exigence.

J’ai un favori, qui consiste à inverser le mot, puis à le multiplier par un nombre constant (impair). Cela peut s’avérer trop complexe si l’inversion de bits n’est pas une opération native sur votre architecture.

Une LFSR Galois à période maximale de 32 bits pourrait vous convenir. Essayer:

 r = (r >> 1) ^ (-(r & 1) & 0x80200003); 

Le seul problème avec les LFSR est que vous ne pouvez pas produire la valeur 0. Celle-ci a donc une plage de 1 à 2 ^ 32-1. Vous voudrez peut-être peaufiner la sortie ou vous en tenir à un bon LCG.

En plus d’utiliser un Lehmer MCG , vous pouvez en utiliser un couple:

Les variantes 32 bits de Xorshift ont une période garantie de 2 32 -1 en utilisant un état 32 bits :

 uint32_t state; uint32_t xorshift32(void) { state ^= state << 13; state ^= state >> 17; state ^= state << 5; return state; } 

C’est la recommandation 32 bits originale de 2003 (voir document). Selon votre définition de "qualité décente", cela devrait aller. Cependant, il échoue les tests de rang binary de Diehard et 5/10 tests de SmallCrush.

Version alternative avec un meilleur mélange et des constantes (passe SmallCrush et Crush) :

 uint32_t xorshift32a(void) { int s = __builtin_bswap32(state * 1597334677); state ^= state << 25; state ^= state >> 7; state ^= state << 2; return state + s; } 

Basé sur des recherches ici et ici .


Il y a aussi Mulberry32 qui a une période de exactement 2 32 :

 uint32_t mulberry32(void) { uint32_t z = state += 0x6D2B79F5; z = (z ^ z >> 15) * (1 | z); z ^= z + (z ^ z >> 7) * (61 | z); return z ^ z >> 14; } 

C'est probablement votre meilleure option. C'est assez bon / rapide. L'auteur déclare "Il réussit les 13 tests de gjrand sans échec et une valeur de p totale de 0,984 (où 1 est parfait et 0,1 ou moins est un échec) sur 4 Go de données générées. C'est un quart de la période complète". Cela semble être une amélioration par rapport à SplitMix32.


"SplitMix32", extrait de xxHash / MurmurHash3 (séquence de Weyl) :

 uint32_t splitmix32(void) { uint32_t z = state += 0x9e3779b9; z ^= z >> 15; // 16 for murmur3 z *= 0x85ebca6b; z ^= z >> 13; z *= 0xc2b2ae3d; // 0xc2b2ae35 for murmur3 return z ^= z >> 16; } 

A également une période complète de 2 32 . La qualité peut être discutable ici, mais son grand frère 64 bits a beaucoup de fans (passe BigCrush). La structure générale mérite donc d’être examinée.