Tests Diehard

Un nombre m d'anniversaires est choisi dans une année de n jours, en indiquant l'espacement entre les anniversaires. Si j est le nombre de valeurs qui apparaissent plus d'une fois dans cette liste, alors j peut-être approché par la loi de Poisson de moyenne m³ ÷ (4n). L'expérience montre que n doit être assez grand, disons n ≥ 2¹⁸, pour comparer les résultats à la loi de Poisson avec cette moyenne. Ce test utilise n = 2²⁴ et m = 2⁹, de sorte que la loi sous-jacente pour j est considérée comme étant de Poisson avec λ = 2¹⁷ ÷ 2²⁶ = 2. Un échantillon de 500 valeurs est prélevé et un test d'ajustement du χ² fournit une valeur p. Le premier test utilise les bits 1-24 (en comptant à partir de la gauche) à partir des nombres entiers du fichier spécifié. Ensuite, le fichier est fermé et rouvert. Ensuite, les bits 2-25 sont utilisés pour fournir les anniversaires, puis 3-26 et ainsi de suite jusqu'aux bits 9-32. Chaque ensemble de bits fournit une valeur p et les neuf valeurs p fournissent un échantillon pour réaliser un test de modèle de points par test de Kolmogorov-Smirnov en utilisant les valeurs de la fonction K (Ktest).

Le test du chevauchement à cinq permutations: c'est le test OPERM5. Il examine une séquence d'un million d'entiers aléatoires de 32 bits. Chaque ensemble de cinq entiers consécutifs peut se trouver dans l'un des 120 états, pour les 5! ordres possibles de cinq nombres. Ainsi, les 5^e, 6^e, 7^e... nombres fournissent chacun un état. Comme plusieurs milliers de transitions d'états sont observées, des comptes cumulatifs sont faits du nombre d'occurrences de chaque état. Ensuite, la forme quadratique dans l'inverse faible de la matrice de covariance 120×120 donne un test équivalent au test du rapport de vraisemblance selon lequel les 120 nombres de cellules proviennent de la loi normale spécifiée (asymptotiquement) avec la matrice de covariance 120×120 spécifiée (avec le rang 99). Cette version utilise 1 000 000 entiers, deux fois. Ce test peut présenter des biais systématiques se traduisant par des valeurs p constamment faibles.

La plupart des tests Diehard renvoient une valeur p, qui devrait être uniforme sur [0,1] si le fichier d'entrée contient des bits aléatoires vraiment indépendants. Ces p-valeurs sont obtenues par p = F(X), où F est la loi supposée de la variable aléatoire de l'échantillon X - souvent normale. Mais ce F supposé n'est qu'une approximation asymptotique, pour laquelle l'ajustement sera le plus mauvais dans les queues. Vous ne devriez donc pas être surpris par des valeurs p occasionnelles proches de 0 ou 1, comme 0,0012 ou 0,9983. Lorsqu'un flux binaire est vraiment grand, vous obtiendrez des p de 0 ou 1 à six endroits ou plus. Comme il existe de nombreux tests, il n'est pas improbable qu'un p < 0,025 ou un p > 0,975 signifie que le RNG a « échoué le test au niveau 0,05 ». Nous nous attendons à ce qu'un certain nombre de ces événements se produisent parmi les centaines d'événements produits par Diehard, même à condition que le générateur de nombres aléatoires soit parfait.

On choisit les 31 bits les plus à gauche de 31 nombres entiers générés aléatoirement par le GNR et on forme ainsi une matrice binaire de 31 par 31 dont on détermine le rang. On comptabilise les rangs obtenus sur 40 000 matrices générées par le GNR (les rangs possibles vont de 0 à 31 mais il est rare d'obtenir un rang inférieur à 28 pour une matrice générée), on compte la fréquence des rangs obtenus et on opère un test du χ² sur ces résultats. On peut procéder de la même façon avec des matrices de 32 par 32 avec cette fois-ci les matrices générées avec un rang inférieur à 29 qui sont peu probables.

OPSO vient de l'anglais Overlapping-pairs-sparse-occupancy qui veut dire «cumul de paires éparpillées». Se base sur l'analyse de mots de 2 lettres provenant d'un alphabet particulier de 1024 lettres. Chacune de ces lettres est déterminée par 10 bits (d'où les 1024 lettres possibles car 2¹⁰ = 1024) d'un entier de 32 bit donné par notre générateur congruentiel.

Et parmi tous les mots qu'il est possible de former avec un tel alphabet, notre test va compter le nombre de mots qui n'apparaissent pas. Cela se déroule comme suit:

Le générateur à tester va générer une séquence de 2²¹ entrées (lettres); cette séquence va donc contenir des mots de 2 lettres les uns à la suite des autres et notre test OPSO va compter le nombre de mots manquants dans la séquence (on rappelle qu'il y a 1024×1024 = 1 048 576 mots de 2 lettres possibles).

Le nombre de mots manquant devrait être en moyenne de 141 909 avec un écart type de 290 pour que le GNR donne effectivement des nombres aléatoires.

Le fichier testé est vu comme un flux binaire. On les appelle ${\displaystyle b_{1}}$, ${\displaystyle b_{2}}$… On considère un alphabet de deux «lettres», 0 et 1, et on imagine le flux binaire comme une succession de «mots» de 20 lettres se chevauchant.

Ainsi, le premier mot est ${\displaystyle b_{1}b_{2}\dots b_{20}}$, le second mot est ${\displaystyle b_{2}b_{3}\dots b_{21}}$, et ainsi de suite. Le test de flux binaire compte le nombre de mots de 20 lettres (20 bits) manquant dans une chaîne de ${\displaystyle 2^{21}}$ caractères contenant des mots de 20 caractères se chevauchant.

Il y a ${\displaystyle 2^{20}}$ mots de 20 lettres possibles. Pour une chaîne de caractère vraiment aléatoire de ${\displaystyle 2^{21}+19}$ bits, le nombre de mots manquants ${\displaystyle X}$ devrait être très proche d'une loi normale de moyenne 141 909 et d'écart type 428. Par conséquent, la variable aléatoire ${\displaystyle Y=(X-141909)/428}$ devrait suivre une loi normale centrée réduite. Le test est répété 20 fois.

Dans un carré de côté 100, on place de manière aléatoire une "voiture" (un cercle de rayon 1). Ensuite, on essaie d'en garer une deuxième, puis une troisième, et ainsi de suite, en veillant à bien placer au hasard chacun de ces points. Si une tentative de garer une voiture cause un "accident" (superposer un point sur un autre), on retente de placer ce point autre part dans le carré. Chaque tentative mène donc soit à un échec soit à une voiture garée correctement. Si on représente deux nombres n et k, respectivement le nombre de tentatives et le nombre de voitures garées correctement, on obtient une courbe qui devrait être similaire à celle que donnée par un générateur de nombres aléatoires parfait. La théorie pour le comportement d'une telle courbe aléatoire étant hors de notre compréhension La théorie pour le comportement d'une telle courbe aléatoire étant hors de notre compréhension, et la représentation graphique n'étant pas possible dans la batterie de test Diehard, on utilise une caractérisation simple de cette expérience aléatoire: k, le nombre de voitures garées correctement après n = 12000 essais.

La simulation montre que k devrait être en moyenne égal à 3523 avec un écart type sigma = 21.9, et se trouve très proche d'une loi normale. De ce fait, (k-3523) ÷ 21.9 devrait être une loi normale, centrée et réduite. Une fois convertie en variable uniforme, elle peut fournir des données d'input à un KSTEST basé sur un échantillon de 10.

On effectue 100 fois l'opération suivante :

• choisir ${\displaystyle n=8000}$ points aléatoires dans un carré de côté 10 000 ;
• trouver ${\displaystyle d}$, la distance minimale entre les ${\displaystyle (n^{2}-n)/2}$ paires de points (soit 31 996 000 si on considère toujours ${\displaystyle n=8000}$).

Si tous les points ainsi générés sont totalement indépendants, alors ${\displaystyle d^{2}}$, le carré de la distance minimale calculée précédemment, devrait être très proche d'une loi exponentielle de médiane 0.995. De ce fait, ${\displaystyle 1-\exp(-d^{2}/0.995)}$ devrait être uniforme sur ${\displaystyle [0,1)}$ et un KSTEST sur les 100 valeurs obtenues sert de test d'uniformité pour les points aléatoires dans le carré. Les nombres du test valant 0 modulo 5 sont retenues mais le KSTEST est basé sur l'ensemble complet des 100 générations des 8 000 points aléatoires dans un carré de 10 000 × 10 000.

On prend 4 000 points aléatoires dans un cube de côté 1 000. À chaque point, on centre une sphère assez large pour atteindre le prochain point le plus proche. Ensuite, le volume de la plus petite de ces sphères est (très proche de) exponentiellement avec une moyenne de ${\displaystyle 120\pi /3}$. Ainsi le rayon au carré est exponentiel avec une moyenne de 30. La moyenne est obtenue par simulation étendue. Le test des sphères 3D génère 4 000 de ces sphères 20 fois. Chaque rayon minimal au carré mène à une variable uniforme par moyenne de ${\displaystyle 1-\exp(-r^{3}/30)}$. Ensuite un test de Kolmogorov-Smirnov est réalisé sur les 20 valeurs de p.

On prend des nombres entiers aléatoires, on les transforme en décimaux pour obtenir des uniformes ${\displaystyle [0,1)}$. On commence avec ${\displaystyle k=2^{31}=2147483648}$, le test trouve ${\displaystyle j}$, le nombre d’itérations nécessaires pour réduire ${\displaystyle k}$ à 1 en utilisant la réduction ${\displaystyle k=\lceil k\cdot U\rceil }$, avec ${\displaystyle U}$ donné par entier décimal du fichier qui est testé. De tels ${\displaystyle j}$ sont trouvés 100000 fois, ensuite les comptes du nombre de fois où ${\displaystyle j}$ était ≤ 6, 7, …, 47, ≥ 48 sont utilisés pour donner un test du χ² pour la fréquence des cellules.

Dans ce test, on joue 200 000 parties de craps. On compte ensuite le nombre de victoires et le nombre de lancers nécessaires pour terminer chaque partie. Le nombre de victoires devrait être très proche d'une loi normale de moyenne ${\displaystyle 200000p}$ et de variance ${\displaystyle 200000p(1-p)}$, avec ${\displaystyle p=244/495}$. Le nombre de lancers nécessaires pour compléter/gagner une partie peut varier de 1 à l'infini, mais tous les comptages supérieurs à 21 sont regroupés dans les comptes de parties à 21 lancers. Un test du khi carré est effectué sur les comptes de nombres de lancers. Chaque entier de 32 bits du fichier de test donne une valeur pour le lancer d'un dé, qui est une décimale comprise entre [0 et 1), que l'on multiplie par 6, et on prend ensuite 1 + la partie entière de la valeur calculée.