resolution conflit

[hdrcouchot.git] / 14Secrypt.tex

diff --git a/14Secrypt.tex b/14Secrypt.tex
index a60e4ff0274f75ae9999f2164ef5b108d8fdccfe..435e7392f7351f0ff443b0be53ee991e63900206 100644 (file)
--- a/14Secrypt.tex
+++ b/14Secrypt.tex
@@ -21,7 +21,7 @@ arête sortante et une arête entrante.
 % 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 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}
+\section{Programmation logique par contraintes sur des domaines finis}\label{sec:plc}

 Tout d'abord, soit ${\mathsf{N}}$ le nombre d'éléments. 
 Pour éviter d'avoir à gérer des fractions, on peut considérer que 
 les matrices (d'incidence) à générer ont des lignes et des colonnes dont les 
 Tout d'abord, soit ${\mathsf{N}}$ le nombre d'éléments. 
 Pour éviter d'avoir à gérer des fractions, on peut considérer que 
 les matrices (d'incidence) à générer ont des lignes et des colonnes dont les 


@@ -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,57 +182,80 @@ 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}
 
 
 
 

-\section{Graphes 
-  $\textsc{giu}(f)$ 
-  $\textsc{gig}(f)$ 
-  fortement connexes et doublement stochastiques}
-% Secrypt 14
+% section{Graphes 
+%   $\textsc{giu}(f)$ 
+%   $\textsc{gig}(f)$ 
+%   fortement connexes et doublement stochastiques}\label{sec:gen:dblstc}
+% %
+%Secrypt 14

 
 
 
 
 
 
 
 

-\subsection{Suppression des cycles hamiltoniens}
+\section{Suppression des cycles hamiltoniens}

 \label{sec:hamiltonian}
 
 \label{sec:hamiltonian}
 

-Dans un premier temps, nous montrons en section~\ref{sub:removing:theory} que la
+Dans un premier temps, nous montrons %en section~\ref{sub:removing:theory} 
+que la

 suppression  d'un  cycle  hamiltonien   produit  bien  des  matrices  doublement
 stochastiques.   Nous  établissons  ensuite  le  lien avec  les  codes  de  Gray
 équilibrés.
 
 suppression  d'un  cycle  hamiltonien   produit  bien  des  matrices  doublement
 stochastiques.   Nous  établissons  ensuite  le  lien avec  les  codes  de  Gray
 équilibrés.
 

-\subsubsection{Aspects théoriques}
-\label{sub:removing:theory}
+%\subsubsection{Aspects théoriques}
+%\label{sub:removing:theory}

 
 Nous donnons  deux résultats complémentaires, reliant la  suppression d'un cycle
 hamiltonien  du $n$-cube,  les matrices  doublement stochastiques  et  la forte
 
 Nous donnons  deux résultats complémentaires, reliant la  suppression d'un cycle
 hamiltonien  du $n$-cube,  les matrices  doublement stochastiques  et  la forte


@@ -293,15 +316,15 @@ 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
 code  de  Gray est  \emph{cyclique}  si  le premier  élément  et  le dernier  ne
 différent que par un seul bit.
 
 $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
 code  de  Gray est  \emph{cyclique}  si  le premier  élément  et  le dernier  ne
 différent que par un seul bit.
 

-\subsection{Lien avec les codes de Gray cycliques (totalement) équilibrés}
+\section{Lien avec les codes de Gray cycliques (totalement) équilibrés}

 \label{sub:gray}
 
 La borne  inférieure du  nombre de codes  de Gray  ($\left(\frac{n*\log2}{e \log
 \label{sub:gray}
 
 La borne  inférieure du  nombre de codes  de Gray  ($\left(\frac{n*\log2}{e \log


@@ -354,7 +377,7 @@ vérifiant $\sum_{i=1}^nNT_n(i) = 2^n$.
   ce code est totalement équilibré.
 \end{xpl}
 
   ce code est totalement équilibré.
 \end{xpl}
 

-\subsection{Génération de codes de Gray équilibrés par induction}
+\section{Génération de codes de Gray équilibrés par induction}

 \label{sec:induction}
 
 Dans  leur  article de  2004~\cite{ZanSup04},  Zanten  et  Suparta proposent  un
 \label{sec:induction}
 
 Dans  leur  article de  2004~\cite{ZanSup04},  Zanten  et  Suparta proposent  un


@@ -524,11 +547,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. 


@@ -538,9 +574,9 @@ chaque itération qu'un seul élément de $[n]$.
 On pourrait penser à un algorithme basé sur les itérations généralisées, 
 c'est-à-dire qui modifierait une partie des éléments de $[n]$ à chaque 
 itération.
 On pourrait penser à un algorithme basé sur les itérations généralisées, 
 c'est-à-dire qui modifierait une partie des éléments de $[n]$ à chaque 
 itération.

-C'est l'algorithme~\ref{CI Algorithm:prng:g}.
+C'est l'algorithme~\ref{CI Algorithm:prng:g} donné ci-après.

 
 

-\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 +603,277 @@ 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}{2^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:prng:g} 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{sec:plc}.
+  Dans le $3$-cube, le 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 $\textsc{gig}(f^*)$
+    \label{fig:iteration:f*}]{
+      \begin{minipage}{0.55\linewidth}
+        \centering
+        \includegraphics[width=\columnwidth]{images/iter_f}%
+      \end{minipage}
+    }%
+    \subfigure[Matrice de Markov associée au $\textsc{gig}(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:hamiltonian}.
+Pour  chaque nombre $n=3$,  $4$, $5$ et $6$,
+tous  les cycles  hamiltoniens non isomorphes  ont été générés.   Pour les
+valeur de $n=7$ et $8$,  seules $10^{5}$ cycles ont été évalués.  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 unaire. Ceci représente un rapport de 
+  $\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 nécessaires pour atteinte une déviation faible;
+\item $2^n-2^{n-1}$ dans le cas généralisé,
+  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 généralisé, chaque itération a une complexité 
+plus élevée puisqu'il est nécessaire d'invoquer un générateur
+produisant un nombre pseudo-aléatoire dans $[2^{n}]$ tandis qu'il suffit 
+que celui-ci soit dans $[n]$ dans le cas unaire.
+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).
+
+Dans le cas généralisé, si l'on effectue $b$ itérations, 
+à chacune d'elles, 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 $b*n$ appels pour $n$ bits et
+donc $b$ appels pour 1 bit généré en moyenne.
+Dans le cas unaire, si l'on effectue $b'$ itérations, 
+à chacune d'elle, la stratégie génère un nombre entre
+$1$ et $n$. 
+Elle fait donc $\ln(n)/\ln(2)$ appels à ce générateur binaire en moyenne. 
+La démarche fait donc au total $b'*\ln(n)/\ln(2)$ appels pour $n$ bits et
+donc $b'*\ln(n)/(n*\ln(2))$ 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 le 
+cas des itérations généralisées et est toujours plus faible
+que celui des itérations unaires.
+
+
+
+\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}
+
+
+
+
+\section{Tests statistiques}
+
+La qualité des séquences aléatoires produites par 
+le générateur des itérations unaires ainsi que 
+celles issues des itérations généralisées a été évaluée à travers la suite 
+de tests statistiques développée 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}
+
+%