nist.tex

   1 % Soit $e_i$ le $i^{\textrm{ème}}$ vecteur de la base canonique de $\R^{2^{n}}$.
   2 % Chacun des éléments $v_j$, $1 \le j \le 2^n$,
   3 % du vecteur $e_i M_f^t$ représente la probabilité
   4 % d'être dans la configuration $j$ après $t$ étapes du processus de Markov
   5 % associé à $\Gamma(f)$ en partant de la configuration $i$.
   6 % Le nombre \linebreak $\min \{
   7 %  t \mid t \in \Nats, \vectornorm{e_i M_f^t - \pi} < 10^{-4}
   8 % \}$ représente le plus petit nombre d'itérations où la distance de
   9 % ce vecteur au vecteur $\pi=(\frac{1}{2^n},\ldots,\frac{1}{2^n})$
  10 % -- autrement dit, où la déviation par rapport à la distribution uniforme --
  11 %  est inférieure
  12 % à $10^{-4}$. En prenant le max pour tous les $e_i$, on obtient une valeur pour
  13 %  $b$. Ainsi, on a
  14 % $$
  15 % b = \max\limits_{i \in \llbracket 1, 2^n \rrbracket}
  16 % \{
  17 % \min \{
  18 %  t \mid t \in \Nats, \vectornorm{e_i M_f^t - \pi} < 10^{-4}
  19 % \}
  20 % \}.
  21 % $$
  22
  23 \begin{table}[table:functions]{Fonctions avec matrices DSCC et le plus faible temps de mélange.}
  24   \begin{center}
  25     \begin{scriptsize}
  26       \begin{tabular}{|c|l|c|c|}
  27         \hline
  28         fonction  & $f(x)$, $f(x)$ pour $x \in [0,1,2,\hdots,2^n-1]$                 & $b$ & $b'$ \\
  29         \hline
  30         $f^{*4}$  & [13,10,9,14,3,11,1,12,15,4,7,5,2,6,0,8]                          & 15  & 32   \\
  31         \hline
  32         $f^{*5}$  & [29, 22, 25, 30, 19, 27, 24, 16, 21, 6, 5, 28, 23, 26, 1,        & 13  & 43   \\
  33                   & 17, 31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 7, 20, 11, 18, 0, 4]     &     &      \\
  34         \hline
  35         $f^{*6}$  & [55, 60, 45, 44, 58, 62, 61, 48, 53, 50, 52, 36, 59, 34, 33,     & 9   & 50   \\
  36                   & 49, 15, 42, 47, 46, 35, 10, 57, 56, 7, 54, 39, 37, 51, 2, 1,     &     &      \\
  37                   & 40, 63, 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22,      &     &      \\
  38                   & 16, 24, 13, 12, 29, 8, 43, 14, 41, 0, 5, 38, 4, 6, 11, 3, 9, 32] &     &      \\
  39          \hline
  40          $f^{*7}$ & [111, 94, 93, 116, 122, 114, 125, 88, 87, 126, 119, 84, 123,     & 8   & 57   \\
  41                   & 98, 81, 120, 109, 106, 105, 110, 99, 107, 104, 108, 101, 70,     &     &      \\
  42                   & 117, 96, 67, 102, 113, 64, 79, 30, 95, 124, 83, 91, 121, 24,     &     &      \\
  43                   & 23, 118, 69, 20, 115, 90, 17, 112, 77, 14, 73, 78, 74, 10, 72,   &     &      \\
  44                   & 76, 103, 6, 71, 100, 75, 82, 97, 0, 127, 54, 57, 62, 51, 59,     &     &      \\
  45                   & 56, 48, 53, 38, 37, 60, 55, 58, 33, 49, 63, 44, 47, 40, 42,      &     &      \\
  46                   & 46, 45, 41, 35, 34, 39, 52, 43, 50, 32, 36, 29, 28, 61, 92,      &     &      \\
  47                   & 26, 18, 89, 25, 19, 86, 85, 4, 27, 2, 16, 80, 31, 12, 15, 8,     &     &      \\
  48                   & 3, 11, 13, 9, 5, 22, 21, 68, 7, 66, 65, 1]                       &     &      \\
  49         \hline
  50         $f^{*8}$  &[223, 190, 249, 254, 187, 251, 233, 232, 183, 230, 247, 180,&        7 & 63    \\
  51                  & 227, 178, 240, 248, 237, 236, 253, 172, 203, 170, 201, 168, &&\\
  52                  & 229, 166, 165, 244, 163, 242, 241, 192, 215, 220, 205, 216, &&\\
  53                  & 218, 222, 221, 208, 213, 210, 212, 214, 219, 211, 217, 209, &&\\
  54                  & 239, 202, 207, 140, 139, 234, 193, 204, 135, 196, 199, 132, &&\\
  55                  & 194, 130, 225, 200, 159, 62, 185, 252, 59, 250, 169, 56, 191,&&\\
  56                  & 246, 245, 52, 243, 50, 176, 48, 173, 238, 189, 44, 235, 42, &&\\
  57                  & 137, 184, 231, 38, 37, 228, 35, 226, 177, 224, 151, 156, 141,&&\\
  58                  & 152, 154, 158, 157, 144, 149, 146, 148, 150, 155, 147, 153, &&\\
  59                  & 145, 175, 206, 143, 136, 11, 142, 129, 8, 7, 198, 197, 4, 195, &&\\
  60                  & 2, 161, 160, 255, 124, 109, 108, 122, 126, 125, 112, 117, 114, &&\\
  61                  & 116, 100, 123, 98, 97, 113, 79, 106, 111, 110, 99, 74, 121, 120,&&\\
  62                  & 71, 118, 103, 101, 115, 66, 65, 104, 127, 90, 89, 94, 83, 91, 81,&&\\
  63                  & 92, 95, 84, 87, 85, 82, 86, 80, 88, 77, 76, 93, 72, 107, 78, 105, &&\\
  64                  & 64, 69, 102, 68, 70, 75, 67, 73, 96, 55, 58, 45, 188, 51, 186, 61, &&\\
  65                  & 40, 119, 182, 181, 53, 179, 54, 33, 49, 15, 174, 47, 60, 171, && \\
  66                  & 46, 57, 32, 167, 6, 36, 164, 43, 162, 1, 0, 63, 26, 25, 30, 19,&&\\
  67                  & 27, 17, 28, 31, 20, 23, 21, 18, 22, 16, 24, 13, 10, 29, 14, 3, &&\\
  68                  &138, 41, 12, 39, 134, 133, 5, 131, 34, 9, 128]&&\\
  69         \hline
  70       \end{tabular}
  71     \end{scriptsize}
  72   \end{center}
  73 \end{table}
  74
  75 Le  tableau~\ref{table:functions} reprend  les  fonctions qui  ont été  générées
  76 selon  la méthode détaillée  dans~\cite{chgw14oip} correspondant  à ce  qui est
  77 présenté en  section~\ref{section:genmat}.  Pour  chaque nombre $n=3$,  $4$, $5$
  78 ,$6$, tous  les cycles  hamiltoniens non isomorphes  ont été générés.   Pour les
  79 valeur de $n=7$ et $8$,  seules $10^{5}$ configurations ont été évaluées.  Parmi
  80 toutes  les fonctions  obtenues en  enlevant du  $n$-cube ces  cycles,  n'ont été
  81 retenues que celles  qui minimisaient le temps de mélange relatif  à une valeur de
  82 $\epsilon$ fixée à $10^{-8}$.  Ce  nombre d'itérations est stocké dans la troisième
  83 colonne sous la variable $b$.  La variable $b'$ reprend le temps de mélange pour
  84 l'algorithme $\chi_{\textit{14Secrypt}}$~\cite{chgw14oip}.
  85
  86 Un premier  résultat est  que ce nouvel  algorithme réduit grandement  le nombre
  87 d'itérations  suffisant pour  obtenir une  faible  déviation par  rapport à  une
  88 distribution uniforme.  On constate de  plus que ce nombre semble décroître avec
  89 le nombre d'éléments alors qu'il augmentait dans l'approche précédente.
  90
  91 La qualité des séquences aléatoires a été évaluée à travers la suite
  92 de tests statistiques développée pour les générateurs de nombres
  93 pseudo-aléatoires par le
  94 \emph{National Institute of Standards and Technology} (NIST).
  95  Pour les 15 tests, le seuil $\alpha$ est fixé à $1\%$:
  96  une  valeur
  97  qui est plus grande que $1\%$  signifie
  98  que la chaîne est considérée comme aléatoire avec une confiance de $99\%$.
  99  Le tableau~\ref{fig:TEST} donne une vision synthétique de toutes
 100  les expérimentations.
 101 L'expérience a montré notamment que toutes ces fonctions
 102 passent avec succès cette batterie de tests.
 103
 104 %%%%%%%%% Relancer pour n=6, n=7, n=8
 105 %%%%%%%%% Recalculer le MT
 106 %%%%%%%%% Regenerer les 10^6 bits
 107 %%%%%%%%% Evaluer sur NIST
 108
 109 \begin{table}[fig:TEST]{Test de NIST réalisé sur les fonctions $f^*$ détaillées au tableau~\ref{table:functions}.}
 110   \centering
 111   \begin{scriptsize}
 112     \begin{tabular}{|*{5}{c|}}
 113       \hline
 114 Test                          & $f^{*4}$      & $f^{*5}$      & $f^{*6}$      & $f^{*7}$      \\ \hline
 115 Fréquence (Monobit)           & 0.025 (0.99)  & 0.066 (1.0)   & 0.319 (0.99)  & 0.001 (1.0)   \\ \hline
 116 Fréquence / bloc              & 0.401 (0.99)  & 0.867 (1.0)   & 0.045 (0.99)  & 0.085 (0.99)  \\ \hline
 117 Somme Cumulé*                 & 0.219 (0.995) & 0.633 (1.0)   & 0.635 (1.0)   & 0.386 (0.99)  \\ \hline
 118 Exécution                     & 0.964 (0.98)  & 0.699 (0.99)  & 0.181 (0.99)  & 0.911 (0.98)  \\ \hline
 119 Longue exécution dans un bloc & 0.137 (0.99)  & 0.964 (1.0)   & 0.145 (0.99)  & 0.162 (0.98)  \\ \hline
 120 Rang                          & 0.616 (0.99)  & 0.678 (1.0)   & 0.004 (1.0)   & 0.816 (1.0)   \\ \hline
 121 Fourier rapide                & 0.048 (0.99)  & 0.637 (0.97)  & 0.366 (0.99)  & 0.162 (0.99)  \\ \hline
 122 Patron sans superposition*    & 0.479 (0.988) & 0.465 (0.989) & 0.535 (0.989) & 0.499 (0.989) \\ \hline
 123 Patron avec superposition     & 0.897 (1.0)   & 0.657 (0.97)  & 0.897 (0.98)  & 0.236 (0.99)  \\ \hline
 124 Statistiques universelles     & 0.991 (0.98)  & 0.657 (0.98)  & 0.102 (0.98)  & 0.719 (0.98)  \\ \hline
 125 Entropie approchée (m=10)     & 0.455 (1.0)   & 0.964 (1.0)   & 0.162 (1.0)   & 0.897 (0.98)  \\ \hline
 126 Suite aléatoire *             & 0.372 (0.993) & 0.494 (0.986) & 0.243 (0.992) & 0.258 (0.993) \\ \hline
 127 Suite aléatoire variante *    & 0.496 (0.989) & 0.498 (0.992) & 0.308 (0.983) & 0.310 (0.999) \\ \hline
 128 Série* (m=10)                 & 0.595 (0.995) & 0.289 (0.975) & 0.660 (0.995) & 0.544 (0.99)  \\ \hline
 129 Complexité linaire            & 0.816 (1.0)   & 0.897 (0.98)  & 0.080 (0.98)  & 0.798 (1.0)   \\ \hline
 130     \end{tabular}
 131   \end{scriptsize}
 132 \end{table}
 133
 134 Enfin,  nous avons  également débuté  une campagne  de tests  complémentaires de
 135 notre  générateur  aléatoire, utilisant  les  trois  \emph{crush tests}  (small,
 136 normal  et big)  proposés dans  la bibliothèque  TestU01~\cite{LEcuyerS07}.  Les
 137 premiers résultats que nous obtenons sont très encourageants puisque la fonction
 138 $f^{*4}$ passe avec succès tous les tests du small crush.
 139
 140 %%% Local Variables:
 141 %%% mode: latex
 142 %%% TeX-master: "main"
 143 %%% End: