% Soit $e_i$ le $i^{\textrm{ème}}$ vecteur de la base canonique de $\R^{2^{n}}$. 
% Chacun des éléments $v_j$, $1 \le j \le 2^n$, 
% du vecteur $e_i M_f^t$ représente la probabilité 
% d'être dans la configuration $j$ après $t$ étapes du processus de Markov 
% associé à $\Gamma(f)$ en partant de la configuration $i$.   
% Le nombre \linebreak $\min \{
%  t \mid t \in \Nats, \vectornorm{e_i M_f^t - \pi} < 10^{-4}
% \}$ représente le plus petit nombre d'itérations où la distance de 
% ce vecteur au vecteur $\pi=(\frac{1}{2^n},\ldots,\frac{1}{2^n})$
% -- autrement dit, où la déviation par rapport à la distribution uniforme --
%  est inférieure 
% à $10^{-4}$. En prenant le max pour tous les $e_i$, on obtient une valeur pour
%  $b$. Ainsi, on a 
% $$
% b = \max\limits_{i \in \llbracket 1, 2^n \rrbracket} 
% \{
% \min \{
%  t \mid t \in \Nats, \vectornorm{e_i M_f^t - \pi} < 10^{-4}
% \}
% \}. 
% $$

\begin{table}[table:functions]{Fonctions avec matrices DSCC et le plus faible temps de mélange.}
  \begin{center}
    \begin{scriptsize}
      \begin{tabular}{|c|l|c|c|}
        \hline
        fonction  & $f(x)$, $f(x)$ pour $x \in [0,1,2,\hdots,2^n-1]$                 & $b$ & $b'$ \\ 
        \hline
        $f^{*4}$  & [13,10,9,14,3,11,1,12,15,4,7,5,2,6,0,8]                          & 15  & 32   \\
        \hline
        $f^{*5}$  & [29, 22, 25, 30, 19, 27, 24, 16, 21, 6, 5, 28, 23, 26, 1,        & 13  & 43   \\
                  & 17, 31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 7, 20, 11, 18, 0, 4]     &     &      \\
        \hline
        $f^{*6}$  & [55, 60, 45, 44, 58, 62, 61, 48, 53, 50, 52, 36, 59, 34, 33,     & 9   & 50   \\
                  & 49, 15, 42, 47, 46, 35, 10, 57, 56, 7, 54, 39, 37, 51, 2, 1,     &     &      \\
                  & 40, 63, 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22,      &     &      \\
                  & 16, 24, 13, 12, 29, 8, 43, 14, 41, 0, 5, 38, 4, 6, 11, 3, 9, 32] &     &      \\
         \hline
         $f^{*7}$ & [111, 94, 93, 116, 122, 114, 125, 88, 87, 126, 119, 84, 123,     & 8   & 57   \\
                  & 98, 81, 120, 109, 106, 105, 110, 99, 107, 104, 108, 101, 70,     &     &      \\ 
                  & 117, 96, 67, 102, 113, 64, 79, 30, 95, 124, 83, 91, 121, 24,     &     &      \\ 
                  & 23, 118, 69, 20, 115, 90, 17, 112, 77, 14, 73, 78, 74, 10, 72,   &     &      \\ 
                  & 76, 103, 6, 71, 100, 75, 82, 97, 0, 127, 54, 57, 62, 51, 59,     &     &      \\ 
                  & 56, 48, 53, 38, 37, 60, 55, 58, 33, 49, 63, 44, 47, 40, 42,      &     &      \\ 
                  & 46, 45, 41, 35, 34, 39, 52, 43, 50, 32, 36, 29, 28, 61, 92,      &     &      \\ 
                  & 26, 18, 89, 25, 19, 86, 85, 4, 27, 2, 16, 80, 31, 12, 15, 8,     &     &      \\ 
                  & 3, 11, 13, 9, 5, 22, 21, 68, 7, 66, 65, 1]                       &     &      \\
        \hline
        $f^{*8}$  &[223, 190, 249, 254, 187, 251, 233, 232, 183, 230, 247, 180,&        7 & 63    \\
                 & 227, 178, 240, 248, 237, 236, 253, 172, 203, 170, 201, 168, &&\\
                 & 229, 166, 165, 244, 163, 242, 241, 192, 215, 220, 205, 216, &&\\
                 & 218, 222, 221, 208, 213, 210, 212, 214, 219, 211, 217, 209, &&\\
                 & 239, 202, 207, 140, 139, 234, 193, 204, 135, 196, 199, 132, &&\\
                 & 194, 130, 225, 200, 159, 62, 185, 252, 59, 250, 169, 56, 191,&&\\
                 & 246, 245, 52, 243, 50, 176, 48, 173, 238, 189, 44, 235, 42, &&\\
                 & 137, 184, 231, 38, 37, 228, 35, 226, 177, 224, 151, 156, 141,&&\\
                 & 152, 154, 158, 157, 144, 149, 146, 148, 150, 155, 147, 153, &&\\
                 & 145, 175, 206, 143, 136, 11, 142, 129, 8, 7, 198, 197, 4, 195, &&\\
                 & 2, 161, 160, 255, 124, 109, 108, 122, 126, 125, 112, 117, 114, &&\\
                 & 116, 100, 123, 98, 97, 113, 79, 106, 111, 110, 99, 74, 121, 120,&&\\
                 & 71, 118, 103, 101, 115, 66, 65, 104, 127, 90, 89, 94, 83, 91, 81,&&\\
                 & 92, 95, 84, 87, 85, 82, 86, 80, 88, 77, 76, 93, 72, 107, 78, 105, &&\\
                 & 64, 69, 102, 68, 70, 75, 67, 73, 96, 55, 58, 45, 188, 51, 186, 61, &&\\
                 & 40, 119, 182, 181, 53, 179, 54, 33, 49, 15, 174, 47, 60, 171, && \\
                 & 46, 57, 32, 167, 6, 36, 164, 43, 162, 1, 0, 63, 26, 25, 30, 19,&&\\
                 & 27, 17, 28, 31, 20, 23, 21, 18, 22, 16, 24, 13, 10, 29, 14, 3, &&\\
                 &138, 41, 12, 39, 134, 133, 5, 131, 34, 9, 128]&&\\
        \hline
      \end{tabular}
    \end{scriptsize}
  \end{center}
\end{table}

Le  tableau~\ref{table:functions} reprend  les  fonctions qui  ont été  générées
selon  la méthode détaillée  dans~\cite{chgw14oip} correspondant  à ce  qui est
présenté en  section~\ref{section:genmat}.  Pour  chaque nombre $n=3$,  $4$, $5$
,$6$, tous  les cycles  hamiltoniens non isomorphes  ont été générés.   Pour les
valeur de $n=7$ et $8$,  seules $10^{5}$ configurations ont été évaluées.  Parmi
toutes  les fonctions  obtenues en  enlevant du  $n$-cube ces  cycles,  n'ont été
retenues que celles  qui minimisaient le temps de mélange relatif  à une valeur de
$\epsilon$ fixée à $10^{-8}$.  Ce  nombre d'itérations est stocké dans la troisième
colonne sous la variable $b$.  La variable $b'$ reprend le temps de mélange pour
l'algorithme $\chi_{\textit{14Secrypt}}$~\cite{chgw14oip}.

Un premier  résultat est  que ce nouvel  algorithme réduit grandement  le nombre
d'itérations  suffisant pour  obtenir une  faible  déviation par  rapport à  une
distribution uniforme.  On constate de  plus que ce nombre semble décroître avec
le nombre d'éléments alors qu'il augmentait dans l'approche précédente.

La qualité des séquences aléatoires a été évaluée à travers la suite 
de tests statistiques développée pour les générateurs de nombres 
pseudo-aléatoires par le 
\emph{National Institute of Standards and Technology} (NIST).
 Pour les 15 tests, le seuil $\alpha$ est fixé à $1\%$:
 une  valeur  
 qui est plus grande que $1\%$  signifie 
 que la chaîne est considérée comme aléatoire avec une confiance de $99\%$.
 Le tableau~\ref{fig:TEST} donne une vision synthétique de toutes 
 les expérimentations. 
L'expérience a montré notamment que toutes ces fonctions
passent avec succès cette batterie de tests. 

%%%%%%%%% Relancer pour n=6, n=7, n=8
%%%%%%%%% Recalculer le MT
%%%%%%%%% Regenerer les 10^6 bits
%%%%%%%%% Evaluer sur NIST
 
\begin{table}[fig:TEST]{Test de NIST réalisé sur les fonctions $f^*$ détaillées au tableau~\ref{table:functions}.}
  \centering
  \begin{scriptsize}
    \begin{tabular}{|*{5}{c|}}
      \hline
Test                          & $f^{*4}$      & $f^{*5}$      & $f^{*6}$      & $f^{*7}$      \\ \hline
Fréquence (Monobit)           & 0.025 (0.99)  & 0.066 (1.0)   & 0.319 (0.99)  & 0.001 (1.0)   \\ \hline  
Fréquence / bloc              & 0.401 (0.99)  & 0.867 (1.0)   & 0.045 (0.99)  & 0.085 (0.99)  \\ \hline
Somme Cumulé*                 & 0.219 (0.995) & 0.633 (1.0)   & 0.635 (1.0)   & 0.386 (0.99)  \\ \hline 
Exécution                     & 0.964 (0.98)  & 0.699 (0.99)  & 0.181 (0.99)  & 0.911 (0.98)  \\ \hline 
Longue exécution dans un bloc & 0.137 (0.99)  & 0.964 (1.0)   & 0.145 (0.99)  & 0.162 (0.98)  \\ \hline 
Rang                          & 0.616 (0.99)  & 0.678 (1.0)   & 0.004 (1.0)   & 0.816 (1.0)   \\ \hline 
Fourier rapide                & 0.048 (0.99)  & 0.637 (0.97)  & 0.366 (0.99)  & 0.162 (0.99)  \\ \hline 
Patron sans superposition*    & 0.479 (0.988) & 0.465 (0.989) & 0.535 (0.989) & 0.499 (0.989) \\ \hline 
Patron avec superposition     & 0.897 (1.0)   & 0.657 (0.97)  & 0.897 (0.98)  & 0.236 (0.99)  \\ \hline 
Statistiques universelles     & 0.991 (0.98)  & 0.657 (0.98)  & 0.102 (0.98)  & 0.719 (0.98)  \\ \hline 
Entropie approchée (m=10)     & 0.455 (1.0)   & 0.964 (1.0)   & 0.162 (1.0)   & 0.897 (0.98)  \\ \hline 
Suite aléatoire *             & 0.372 (0.993) & 0.494 (0.986) & 0.243 (0.992) & 0.258 (0.993) \\ \hline 
Suite aléatoire variante *    & 0.496 (0.989) & 0.498 (0.992) & 0.308 (0.983) & 0.310 (0.999) \\ \hline 
Série* (m=10)                 & 0.595 (0.995) & 0.289 (0.975) & 0.660 (0.995) & 0.544 (0.99)  \\ \hline 
Complexité linaire            & 0.816 (1.0)   & 0.897 (0.98)  & 0.080 (0.98)  & 0.798 (1.0)   \\ \hline
    \end{tabular}
  \end{scriptsize}
\end{table}

Enfin,  nous avons  également débuté  une campagne  de tests  complémentaires de
notre  générateur  aléatoire, utilisant  les  trois  \emph{crush tests}  (small,
normal  et big)  proposés dans  la bibliothèque  TestU01~\cite{LEcuyerS07}.  Les
premiers résultats que nous obtenons sont très encourageants puisque la fonction
$f^{*4}$ passe avec succès tous les tests du small crush.

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "main"
%%% End: 
