avant les expé

[hdrcouchot.git] / 14Secrypt.tex

diff --git a/14Secrypt.tex b/14Secrypt.tex
index e160bc33e869112c0452ba24ea228dbba8911b62..f74f8fea820211eba3188e552810deb144fbde3b 100644 (file)
--- 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.
 
 
 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. 
 
 \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$, 
 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]
 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
 \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
 \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
 & \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   \\
 & \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}
       \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)=
           \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}
 
   \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)$ 
 \section{Graphes 
   $\textsc{giu}(f)$ 
   $\textsc{gig}(f)$ 

-  fortement connexes et doublement stochastiques}
+  fortement connexes et doublement stochastiques}\label{sec:gen:dblstc}

 % Secrypt 14
 
 
 % 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
 $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}
 
 $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.
 
 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. 
 \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. 


@@ -540,7 +574,7 @@ c'est-à-dire qui modifierait une partie des éléments de $[n]$ à chaque
 itération.
 C'est l'algorithme~\ref{CI Algorithm:prng:g}.
 
 itération.
 C'est l'algorithme~\ref{CI Algorithm:prng:g}.
 

-\begin{algorithm}[h]
+\begin{algorithm}[ht]

 %\begin{scriptsize}
 \KwIn{une fonction $f$, un nombre d'itérations $b$, 
 une configuration initiale $x^0$ ($n$ bits)}
 %\begin{scriptsize}
 \KwIn{une fonction $f$, un nombre d'itérations $b$, 
 une configuration initiale $x^0$ ($n$ bits)}


@@ -567,6 +601,260 @@ 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$.
 
 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}[ht]
+  \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}
+\label{table:functions}\caption{Fonctions avec matrices DSCC et le plus faible temps de mélange.}
+\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}.
 
 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:functions}.
+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}[ht]
+$$
+\begin{array}{|l|l|l|l|l|l|}
+\hline
+\textrm{Itérations} & 4 & 5 & 6 & 7 & 8 \\ 
+\hline
+\textrm{Unaires}         &  19.0 & 22.2905097109  & 23.6954895899 & 25.2661942985 & 27.0\\  
+\hline
+\textrm{Généralisées}          &  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 
+ ces 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}[ht]
+  \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}
+\label{fig:TEST}\caption{Test de NIST réalisé sur les fonctions $f^*$ détaillées au tableau~\label{table:functions}}
+\end{table}
+
+%