X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/46fc71ad146f83c82660e358a1a1bc2ccc0f00e6..591062c8359275f37c6528d0fb3909479f6e4a6e:/14Secrypt.tex

diff --git a/14Secrypt.tex b/14Secrypt.tex
index e160bc3..0465fcf 100644
--- a/14Secrypt.tex
+++ b/14Secrypt.tex
@@ -13,13 +13,13 @@ graphe d'itÃ©rations, ce qui revient Ã  supprimer en chaque n{\oe}ud de ce graph
 arÃªte sortante et une arÃªte entrante.
 
 
-This aim of this section is to show 
-that finding DSSC matrices from a hypercube
-is a typical finite domain satisfaction 
-problem, classically denoted as 
-Constraint Logic Programming on Finite Domains (CLPFD). 
-This part is addressed in the first section. Next, we analyse the first
-results to provide a generation of DSSC matrices with small mixing times. 
+% This aim of this section is to show 
+% that finding DSSC matrices from a hypercube
+% is a typical finite domain satisfaction 
+% problem, classically denoted as 
+% Constraint Logic Programming on Finite Domains (CLPFD). 
+% This part is addressed in the first section. Next, we analyse the first
+% results to provide a generation of DSSC matrices with small mixing times. 
 
 \section{Programmation logique par contraintes sur des domaines finis}
 Tout d'abord, soit ${\mathsf{N}}$ le nombre d'Ã©lÃ©ments. 
@@ -94,7 +94,7 @@ C'est Ã©videmment une relation d'Ã©quivalence.
 
 
 
-\subsection{Analyse de l'approche}
+\subsection{Analyse de l'approche}\label{sub:prng:ana}
 ExÃ©cutÃ©e sur un ordinateur personnelle, PROLOG trouve 
 en moins d'une seconde les
 49 solutions pour  $n=2$, 
@@ -114,7 +114,7 @@ comparÃ© les fonctions non Ã©quivalentes selon leur proportion
 
 
 
-\begin{xpl}
+\begin{xpl}\label{xpl:mixing:3}
 Le tableau~\ref{table:mixing:3} fournit les 5 fonctions boolÃ©ennes 
 qui ont les temps de mÃ©lange les plus petits pour $\varepsilon=10^{-5}$. 
 \begin{table}[ht]
@@ -126,13 +126,13 @@ $$
 \hline
 f^a &  (x_2 \oplus x_3, x_1 \oplus \overline{x_3},\overline{x_3})  &  16   \\
 \hline
-f^*  &  (x_2 \oplus x_3, \overline{x_1}\overline{x_3} + x_1\overline{x_2},
-\overline{x_1}\overline{x_3} + x_1x_2)  &  17   \\
+f^*  &  (x_2 \oplus x_3, \overline{x_1}.\overline{x_3} + x_1\overline{x_2},
+\overline{x_1}.\overline{x_3} + x_1x_2)  &  17   \\
 \hline
-f^b  &  (\overline{x_1}(x_2+x_3) + x_2x_3,\overline{x_1}(\overline{x_2}+\overline{x_3}) + \overline{x_2}\overline{x_3}, &  \\
+f^b  &  (\overline{x_1}(x_2+x_3) + x_2x_3,\overline{x_1}(\overline{x_2}+\overline{x_3}) + \overline{x_2}.\overline{x_3}, &  \\
 & \qquad \overline{x_3}(\overline{x_1}+x_2) + \overline{x_1}x_2)  &  26   \\
 \hline
-f^c  &  (\overline{x_1}(x_2+x_3) + x_2x_3,\overline{x_1}(\overline{x_2}+\overline{x_3}) + \overline{x_2}\overline{x_3}, & \\
+f^c  &  (\overline{x_1}(x_2+x_3) + x_2x_3,\overline{x_1}(\overline{x_2}+\overline{x_3}) + \overline{x_2}.\overline{x_3}, & \\
 & \overline{x_3}(\overline{x_1}+x_2) + \overline{x_1}x_2)  &  29   \\
 \hline
 f^d  &  (x_1\oplus x_2,x_3(\overline{x_1}+\overline{x_2}),\overline{x_3})  &  30   \\
@@ -182,32 +182,53 @@ On s'intÃ©resse  par la suite Ã  la gÃ©nÃ©ration de ce genre de cycles.
       \begin{minipage}{0.35\linewidth}
         \begin{scriptsize}
           \begin{center}
-            $ \dfrac{1}{4} \left(
-              \begin{array}{cccccccc}
-                1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
+
+\[
+M=\dfrac{1}{3} \left(
+\begin{array}{llllllll}
+1&1&1&0&0&0&0&0 \\
+1&1&0&0&0&1&0&0 \\
+0&0&1&1&0&0&1&0 \\
+0&1&1&1&0&0&0&0 \\
+1&0&0&0&1&0&1&0 \\
+0&0&0&0&1&1&0&1 \\
+0&0&0&0&1&0&1&1 \\
+0&0&0&1&0&1&0&1 
+\end{array}
+\right)
+\]
+
+
+
+            % $ \dfrac{1}{4} \left(
+            %   \begin{array}{cccccccc}
+            %     1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
               
-                1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\
+            %     1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\
               
-                0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\
+            %     0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\
               
-                1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
+            %     1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
               
-                1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\
+            %     1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\
               
-                0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
+            %     0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
               
-                0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
+            %     0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
               
-                0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\
+            %     0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\
               
-              \end{array}            \right) $
+            %   \end{array}            \right) $
+
+
+
           \end{center}
         \end{scriptsize}
       \end{minipage}
     }%
     \caption{ReprÃ©sentations de $f^*(x_1,x_2,x_3)=
-      (x_2 \oplus x_3, \overline{x_1}\overline{x_3} + x_1\overline{x_2},
-      \overline{x_1}\overline{x_3} + x_1x_2)$.}\label{fig1}
+      (x_2 \oplus x_3, \overline{x_1}.\overline{x_3} + x_1\overline{x_2},
+      \overline{x_1}.\overline{x_3} + x_1x_2)$.}\label{fig1}
   \end{center}
 \end{figure}
 
@@ -217,7 +238,7 @@ On s'intÃ©resse  par la suite Ã  la gÃ©nÃ©ration de ce genre de cycles.
 \section{Graphes 
   $\textsc{giu}(f)$ 
   $\textsc{gig}(f)$ 
-  fortement connexes et doublement stochastiques}
+  fortement connexes et doublement stochastiques}\label{sec:gen:dblstc}
 % Secrypt 14
 
 
@@ -293,8 +314,8 @@ depuis n'importe quel n{\oe}ud. Le graphe des itÃ©rations $\textsf{giu}$ qui
 
 
 
-Les preuves, relativement directes, sont  laissÃ©es en exercices au lecteur.  Par
-contre, ce qui  est moins aisÃ© est la gÃ©nÃ©ration de  cycles hamiltoniens dans le
+%Les preuves, relativement directes, sont  laissÃ©es en exercices au lecteur.  
+La gÃ©nÃ©ration de  cycles hamiltoniens dans le
 $n$-cube,  ce qui  revient Ã   trouver des  \emph{codes de  Gray  cycliques}.  On
 rappelle que  les codes de  Gray sont des  sÃ©quences de mots binaires  de taille
 fixe ($n$),  dont les Ã©lÃ©ments successifs ne  diffÃ©rent que par un  seul bit. Un
@@ -524,11 +545,24 @@ $\ov{h}(\ov{h}(X))\neq X$, alors
 $E[\ts]\leq 8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1)$. 
 \end{theorem}
 
-Sans entrer dans les dÃ©tails de la preuve, on remarque que le calcul 
-de cette borne ne tient pas en compte le fait qu'on prÃ©fÃ¨re enlever des 
+Sans entrer dans les dÃ©tails de la preuve, on remarque tout d'abord 
+que le calcul 
+de cette borne n'intÃ¨gre pas le fait qu'on prÃ©fÃ¨re enlever des 
 chemins hamiltoniens Ã©quilibrÃ©s. 
 En intÃ©grant cette contrainte, la borne supÃ©rieure pourrait Ãªtre rÃ©duite.
 
+On remarque ensuite que la chaÃ®ne de Markov proposÃ©e ne suit pas exactement
+l'algorithme~\ref{CI Algorithm}. En effet dans la section prÃ©sente, 
+la probabilitÃ© de rester dans une configuration donnÃ©e 
+est fixÃ©e Ã  $frac{1}{2}+\frac{1}{2n}$.
+Dans l'algorithme initial, celle-ci est de ${1}{n}$.
+Cette version, qui reste davantage sur place que l'algorithme original,
+a Ã©tÃ© introduite pour simplifier le calcul de la borne sup 
+du temps d'arrÃªt.   
+
+
+
+
 \section{Et les itÃ©rations gÃ©nÃ©ralisÃ©es?}
 Le chaptire prÃ©cÃ©dent a prÃ©sentÃ© un algorithme de 
 PRNG construit Ã  partir d'itÃ©rations unaires. 
@@ -567,6 +601,258 @@ Par exemple, pour $n=3$, l'ensemble $\textit{Set}(6)$ vaudraitt $\{3,2\}$.
 On remarque aussi que l'argument de la fonction  $\textit{Random}$
 passe de $n$ Ã  $2^n$.
 
-Dans ce qui suit, on va Ã©tudier cet algorithme comparativement Ã  
+On a le thÃ©orÃ¨me suivant qui Ã©tend le thÃ©orÃ¨me~\ref{thm:prng:u} aux itÃ©rations
+gÃ©nÃ©ralisÃ©es.
+
+\begin{theorem}\label{thm:prng:g}
+  Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\textsc{gig}(f)$ son 
+  graphe des itÃ©rations gÃ©nÃ©ralisÃ©es, $\check{M}$ la matrice d'adjacence
+  correspondante Ã  ce graphe 
+  et $M$ une matrice  $2^n\times 2^n$  
+  dÃ©finie par 
+  $M = \dfrac{1}{n} \check{M}$.
+  Si $\textsc{gig}(f)$ est fortement connexe, alors 
+  la sortie du gÃ©nÃ©rateur de nombres pseudo alÃ©atoires dÃ©taillÃ© par 
+  l'algorithme~\ref{CI Algorithm} suit une loi qui 
+  tend vers la distribution uniforme si 
+  et seulement si  $M$ est une matrice doublement stochastique.
+\end{theorem}
+
+La preuve de ce thÃ©orÃ¨me est la mÃªme que celle du thÃ©orÃ¨me~\ref{thm:prng:u}.
+Elle n'est donc pas rappelÃ©e.
+
+\begin{xpl}
+
+  On reprend l'exemple donnÃ© Ã  la section~\ref{sub:prng:ana}:
+  Dans le $3$-cube   cycle hamiltonien dÃ©fini par la sÃ©quence
+  $000,100,101,001,011,111,110,010,000$ a Ã©tÃ© supprimÃ© engendrant 
+  la fonction $f^*$ dÃ©finie par 
+  $$f^*(x_1,x_2,x_3)=
+  (x_2 \oplus x_3, \overline{x_1}.\overline{x_3} + x_1\overline{x_2},
+\overline{x_1}.\overline{x_3} + x_1x_2).
+$$ 
+
+Le graphe  $\textsc{gig}(f^*)$  est reprÃ©sentÃ© Ã  la 
+Figure~\ref{fig:iteration:f*}.
+La matrice de Markov $M$ correspondante est donnÃ©e Ã  
+la figure~\ref{fig:markov:f*}.
+
+\begin{figure}[ht]
+  \begin{center}
+    \subfigure[Graphe des itÃ©rations chaotiques de $f^*$.
+    \label{fig:iteration:f*}]{
+      \begin{minipage}{0.55\linewidth}
+        \centering
+        \includegraphics[width=\columnwidth]{images/iter_f}%
+      \end{minipage}
+    }%
+    \subfigure[Matrice de Markov du graphe d'itÃ©rations chaotiques de 
+    $f^*$\label{fig:markov:f*}]{%
+      \begin{minipage}{0.35\linewidth}
+        \begin{scriptsize}
+          \begin{center}
+            $ \dfrac{1}{4} \left(
+              \begin{array}{cccccccc}
+                1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
+              
+                1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\
+              
+                0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\
+              
+                1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
+              
+                1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\
+              
+                0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
+              
+                0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
+              
+                0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\
+              
+              \end{array}            \right) $
+          \end{center}
+        \end{scriptsize}
+      \end{minipage}
+    }%
+    \caption{ReprÃ©sentations de $f^*(x_1,x_2,x_3)=
+      (x_2 \oplus x_3, \overline{x_1}\overline{x_3} + x_1\overline{x_2},
+      \overline{x_1}\overline{x_3} + x_1x_2)$.}\label{fig1}
+  \end{center}
+\end{figure}
+\end{xpl}
+
+
+
+\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]                          & 17  & 38   \\
+        \hline
+        $f^{*5}$  & [29, 22, 25, 30, 19, 27, 24, 16, 21, 6, 5, 28, 23, 26, 1,        & 13  & 48   \\
+                  & 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,     & 11   & 55   \\
+                  & 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,     & 10   & 63   \\
+                  & 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,&        9 & 72    \\
+                 & 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  une synthÃ¨se de 
+fonctions qui  ont Ã©tÃ©  gÃ©nÃ©rÃ©es selon  la mÃ©thode dÃ©taillÃ©e  
+Ã  la  section~\ref{sec:gen:dblstc}.
+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 (\textit{i.e.}, ce temps de mÃ©lange) 
+est stockÃ© dans la troisiÃ¨me
+colonne sous la variable $b$.  
+La variable $b'$ reprend le temps de mÃ©lange pour
 l'algorithme~\ref{CI Algorithm}.
 
+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 dÃ©croit avec
+le nombre d'Ã©lÃ©ments alors qu'il augmente dans l'approche initiale oÃ¹ 
+l'on marche.
+
+Cela s'explique assez simplement. Depuis une configuration initiale, le nombre 
+de configurations qu'on ne peut pas atteindre en une itÃ©ration est de 
+\begin{itemize}
+\item $2^n-n$ en marchant, ce qui reprÃ©sente $\dfrac{2^n-n}{2^n} = 1-\dfrac{n}{2^n}$ 
+  de toutes les configurations; plus $n$ est grand, 
+  plus ce nombre est proche de $1$, et plus grand devient le nombre 
+  d'itÃ©rations suffisantes pour atteinte une dÃ©viation faible;
+\item $2^n-2^{n-1}$ en sautant, soit la moitiÃ© de toutes les configurations 
+  quel que soit $n$; seul 1 bit reste constant tandis que tous les autres peuvent changer. Plus $n$ grandit, plus la proportion de bits constants diminue.
+\end{itemize}
+
+Cependant, dans le cas oÃ¹ l'on saute, chaque itÃ©ration a une complexitÃ© 
+plus Ã©levÃ©e puisqu'il est nÃ©cessaire d'invoquer un gÃ©nÃ©rateur 
+de nombres pseudo-alÃ©atoires entre 1 et $2^{n}$ tandis qu'il suffit 
+d'avoir un gÃ©nÃ©rateur entre 1 et $n$ dans le premier cas.
+
+Pour comparer les deux approches, on considÃ¨re que le gÃ©nÃ©rateur alÃ©atoire embarquÃ© est binaire, \textit{i.e.} ne gÃ©nÃ¨re qu'un bit (0 ou 1).
+
+Lorsqu'on marche et qu'on effectue $i$ itÃ©rations, 
+Ã  chaque itÃ©ration, la stratÃ©gie gÃ©nÃ¨re un nombre entre
+$1$ et $n$. 
+Elle fait donc $\ln(n)/\ln(2)$ appels Ã  ce gÃ©nÃ©rateur en moyenne. 
+La dÃ©marche fait donc au total $i*\ln(n)/\ln(2)$ appels pour $n$ bits et
+donc $i*\ln(n)/(n*\ln(2))$ appels pour 1 bit gÃ©nÃ©rÃ© en moyenne.
+Lorsqu'on saute et qu'on effectue $i'$ itÃ©rations, 
+Ã  chaque itÃ©ration, la stratÃ©gie gÃ©nÃ¨re un nombre entre
+$1$ et $2^n$. Elle fait donc $n$ appels Ã  ce gÃ©nÃ©rateur.
+On fait donc au total $i'*n$ appels pour $n$ bits et
+donc $i'$ appels pour 1 bit gÃ©nÃ©rÃ© en moyenne.
+Le tableau~\ref{table:marchevssaute} donne des instances de 
+ces valeurs pour $n \in\{4,5,6,7,8\}$ et les fonctions  
+donnÃ©es au tableau~\ref{table:fonctions}.
+On constate que le nombre d'appels par bit gÃ©nÃ©rÃ© dÃ©croit avec $n$ dans la 
+seconde dÃ©marche et est toujours plus faible que celui de la premiÃ¨re.   
+
+
+
+\begin{table}
+$$
+\begin{array}{|l|l|l|l|l|l|}
+\hline
+\textrm{Algorithme} & 4 & 5 & 6 & 7 & 8 \\ 
+\hline
+\textrm{marchant}         &  19.0 & 22.2905097109  & 23.6954895899 & 25.2661942985 & 27.0\\  
+\hline
+\textrm{sautant}          &  17   & 13             & 11            & 10 & 9\\
+\hline
+\end{array}
+$$
+\caption{Nombre moyen 
+  d'appels Ã  un gÃ©nÃ©rateurs binaire par bit gÃ©nÃ©rÃ©}\label{table:marchevssaute}
+\end{table}
+
+
+
+
+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~\label{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}
+
+%
