Comment déterminer la probabilité de collision des semences dans un PRNG?

Question

Je veux utiliser un PRNG pour générer des modèles aléatoires. Je fournirais au PRNG une valeur de hachage en tant que graine. Idéalement, la taille des graines serait de 64 bits ou 128 bits et je m'attendrais à aucune collision si les graines sont uniques.

Les PRNG rencontrent-ils des «collisions», où deux graines différentes produisent exactement la même séquence de nombres aléatoires?

Par exemple, si l'on initialise un prng avec Tous les nombres possibles 32 bits, 64 bits ou 128 bits, on pourrait s'attendre à des collisions zéro car toutes les graines seraient différentes.

Lorsque vous envisagez un générateur congruentiel linéaire, la graine est divisée en multiplicateur. Puisqu'un LCG Lehmer utilise un multiplicateur de 2³¹-1, fournir un hachage aléatoire 32 bits provoquerait des collisions, car il divise tous les nombres 32 bits possibles en 2³¹-1 nombres. Ainsi, une graine de 1, 2³²-1 et 2³¹ sont équivalents et produisent la même séquence de nombres. C'est un problème car je m'attends à la résistance de collision de hachages de 64 ou 128 bits dans le PRNG.

Pour les algorithmes plus compliqués, il n'est pas aussi simple de déterminer ces cas. Mon langage de choix est JavaScript, qui n'a pas de PRNG à tête de série intégré. Il existe bien sûr de nombreuses options pour y remédier au sens des bibliothèques ou des fonctions autonomes.

Le PRNG le meilleur / le plus rapide disponible pour JavaScript semble être Alea. Il a une implémentation JS et C et est basé sur les marsaglia MWC algorithme. L'implémentation JS prend un graine de chaîne variable, il n'est donc pas clair combien de graines uniques sont possibles. Alea est décrit comme ayant une durée de période de 2¹¹⁶, qui, si je comprends bien, signifierait qu'il utilise jusqu'à 116 bits d'une graine fournie (par exemple, un hachage de 128 bits).

Fondamentalement, ce que je demande, c'est, Comment pourrais-je déterminer si les graines entrent en collision dans un PRNG? Est-il basé sur la durée de période décrite?

Une bonne illustration du problème est de comparer Le petit PRNG de Jenkin (2007) avec xoshiro128 + (2018). Ils sont assez similaires. Ils utilisent tous les deux de l'arithmétique 32 bits, stockent l'état dans un réseau de 128 bits composé de quatre UInt32 et renvoient un Uint32 en conséquence. La principale différence est que Jenkins utilise uniquement une graine 32 bits qui est répétée en b, c, d. Tandis que dans xoshiro128 +, tout l'état initial est la graine. Ainsi, je peux fournir un hachage de 128 bits à ce dernier en tant que graine et bénéficier toujours de la qualité du générateur (sans modifier l'algorithme). C'est essentiellement ce que je veux dire - être capable de fournir une très grande graine.

En tant que solution de contournement de ce problème potentiel, j'ai pensé à simplement utiliser la fonction de hachage elle-même et à exécuter d'autres itérations de la fonction de mélange pour obtenir de nouveaux bits pseudo-aléatoires (de la même manière que l'obtention d'un nouveau numéro dans un PRNG). Il est déterministe et apparaît suffisamment aléatoire, mais il semble peu probable que les sorties de fonction de hachage passent des "tests de hasard statistique" tels que Putain ou Big -crush car il n'a pas été conçu comme un PRNG.

En outre, il n'y a pas d'idées cryptographiques ici. La fonction de hachage que j'utiliserais serait Murmurhash3 ou similaire - tout ce qui est assez bon pour passer la suite de tests Smhasher et produit des hachages 64 bits ou 128 bits.