oxford début

[hdrcouchot.git] / 14Secrypt.tex

diff --git a/14Secrypt.tex b/14Secrypt.tex
index f74f8fea820211eba3188e552810deb144fbde3b..597acbb2b0f592bf6d4a6adcec05ff0ed2edf5ff 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}\label{sub:prng:ana}
+%\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$, 


@@ -235,25 +235,27 @@ M=\dfrac{1}{3} \left(
 
 
 
 
 
 

-\section{Graphes 
-  $\textsc{giu}(f)$ 
-  $\textsc{gig}(f)$ 
-  fortement connexes et doublement stochastiques}\label{sec:gen:dblstc}
-% 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


@@ -322,7 +324,7 @@ fixe ($n$),  dont les éléments successifs ne  différent que par un  seul bit.
 code  de  Gray est  \emph{cyclique}  si  le premier  élément  et  le dernier  ne
 différent que par un seul bit.
 
 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


@@ -375,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


@@ -572,7 +574,7 @@ 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}[ht]
 %\begin{scriptsize}
 
 \begin{algorithm}[ht]
 %\begin{scriptsize}


@@ -610,10 +612,10 @@ généralisées.
   correspondante à ce graphe 
   et $M$ une matrice  $2^n\times 2^n$  
   définie par 
   correspondante à ce graphe 
   et $M$ une matrice  $2^n\times 2^n$  
   définie par 

-  $M = \dfrac{1}{n} \check{M}$.
+  $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 
   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 
+  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}
   tend vers la distribution uniforme si 
   et seulement si  $M$ est une matrice doublement stochastique.
 \end{theorem}


@@ -623,8 +625,8 @@ Elle n'est donc pas rappelée.
 
 \begin{xpl}
 
 
 \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
+  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)=
   $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)=


@@ -639,15 +641,15 @@ la figure~\ref{fig:markov:f*}.
 
 \begin{figure}[ht]
   \begin{center}
 
 \begin{figure}[ht]
   \begin{center}

-    \subfigure[Graphe des itérations chaotiques de $f^*$.
+    \subfigure[Graphe $\textsc{gig}(f^*)$

     \label{fig:iteration:f*}]{
       \begin{minipage}{0.55\linewidth}
         \centering
         \includegraphics[width=\columnwidth]{images/iter_f}%
       \end{minipage}
     }%
     \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*}]{%
+    \subfigure[Matrice de Markov associée au $\textsc{gig}(f^*)$
+    \label{fig:markov:f*}]{%

       \begin{minipage}{0.35\linewidth}
         \begin{scriptsize}
           \begin{center}
       \begin{minipage}{0.35\linewidth}
         \begin{scriptsize}
           \begin{center}


@@ -675,8 +677,8 @@ la figure~\ref{fig:markov:f*}.
       \end{minipage}
     }%
     \caption{Représentations de $f^*(x_1,x_2,x_3)=
       \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{xpl}
   \end{center}
 \end{figure}
 \end{xpl}


@@ -686,111 +688,134 @@ la figure~\ref{fig:markov:f*}.
 \begin{table}[ht]
   \begin{center}
     \begin{scriptsize}
 \begin{table}[ht]
   \begin{center}
     \begin{scriptsize}

-      \begin{tabular}{|c|l|c|c|}
+      \begin{tabular}{|c|c|l|c|c|}

         \hline
         \hline

-        fonction  & $f(x)$, $f(x)$ pour $x \in [0,1,2,\hdots,2^n-1]$                 & $b$ & $b'$ \\ 
+        $n$ & fonction  & $f(x)$, $f(x)$ pour $x \in [0,1,2,\hdots,2^n-1]$                 & $b$ & $b'$ \\ 

         \hline
         \hline

-        $f^{*4}$  & [13,10,9,14,3,11,1,12,15,4,7,5,2,6,0,8]                          & 17  & 38   \\
+        4 & $f^{*4}$ & [13,10,9,14,3,11,1,12,15,4,7,5,2,6,0,8]                          & \textbf{17}  & \textbf{38}   \\

         \hline
         \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]     &     &      \\
+         \multirow{4}{0.5cm}{5}& $f^{*5}$  & [29, 22, 25, 30, 19, 27, 24, 16, 21, 6, 5, 28, 23, 26, 1,        & \textbf{13}  & 48   \\
+            &   & 17, 31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 7, 20, 11, 18, 0, 4]     &     &      \\
+        \cline{2-5}
+         & $g^{*5}$  & [29, 22, 21, 30, 19, 27, 24, 28, 7, 20, 5, 4, 23, 26, 25,                                                                                        & 15  & \textbf{47}   \\
+            &   & 17, 31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 1, 6, 11, 18, 0, 16
+                                                                                           &     &      \\
+        

         \hline
         \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]                       &     &      \\
+        \multirow{8}{0.5cm}{6}& $f^{*6}$  & 
+     [55, 60, 45, 56, 58, 42, 61, 40, 53, 50, 52, 54, 59, 34, 33, & \multirow{4}{0.5cm}{\textbf{11}}& \multirow{4}{0.5cm}{55}\\
+& & 49, 39, 62, 47, 46, 11, 43, 57, 8, 37, 6, 36, 4, 51, 38, 1, & & \\
+& & 48, 63, 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, & & \\
+& & 16, 24, 13, 12, 29, 44, 10, 14, 41, 0, 15, 2, 7, 5, 35, 3, 9, 32] & &\\    
+        \cline{2-5}
+&$g^{*6}$ &     [55, 60, 45, 44, 43, 62, 61, 48, 53, 50, 52, 36, 59, 51, 33, & \multirow{4}{0.5cm}{12}&  \multirow{4}{0.5cm}{\textbf{54}}\\
+    & & 49, 15, 14, 47, 46, 35, 58, 57, 56, 7, 54, 39, 37, 3, 38, 1, & & \\
+    & &  40, 63, 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22,  & & \\
+    & &  16, 24, 13, 12, 29, 8, 10, 42, 41, 0, 5, 2, 4, 6, 11, 34, 9, 32] & & \\
+ \hline
+         \multirow{9}{0.5cm}{7}            &$f^{*7}$ & [111, 94, 93, 116, 122, 114, 125, 88, 115, 126, 85, 84, 123,     & \multirow{9}{0.5cm}{\textbf{10}}    & \multirow{9}{0.5cm}{\textbf{63}}     \\ 
+                 & & 98, 81, 120, 109, 78, 105, 110, 99, 107, 104, 108, 101, 118,     &     &      \\ 
+                 & & 117, 96, 103, 66, 113, 64, 79, 86, 95, 124, 83, 91, 121, 24,     &     &      \\ 
+                 & & 119, 22, 69, 20, 87, 18, 17, 112, 77, 76, 73, 12, 74, 106, 72,   &     &      \\ 
+                 & & 8, 7, 102, 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, 90, 89, 25, 19, 30, 23, 4, 27, 2, 16, 80, 31, 10, 15, 14,     &     &      \\ 
+                 & & 3, 11, 13, 9, 5, 70, 21, 68, 67, 6, 65, 1] & & \\

         \hline
         \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]&&\\
+         \multirow{20}{0.5cm}{8}   &        $f^{*8}$  &
+[223, 190, 249, 254, 187, 251, 233, 232, 183, 230, 247, 180,& 
+\multirow{20}{0.5cm}{9}& 
+\multirow{20}{0.5cm}{71}\\ 
+& & 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, 12, 11, 142, 129, 128, 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, 136, 39, 134, 133, 5, 131,& & \\ 
+& & 34, 9, 8]&&\\

         \hline
       \end{tabular}
     \end{scriptsize}
   \end{center}
         \hline
       \end{tabular}
     \end{scriptsize}
   \end{center}

-\label{table:functions}\caption{Fonctions avec matrices DSCC et le plus faible temps de mélange.}
+\caption{Fonctions avec matrices DSCC et le plus faible temps de mélange}\label{table:functions}

 \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  
 \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
+à 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
 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}$.  
+$\epsilon$ fixée à $10^{-8}$ et pour un mode donné.  

 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
 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
+l'algorithme~\ref{CI Algorithm}. 
+On note que pour un nombre $n$ de bits fixé et un mode donné d'itérations, 
+il peut avoir plusieurs fonctions minimisant ce temps de mélange. De plus, comme ce temps 
+de mélange est construit à partir de la matrice de Markov et que celle-ci dépend 
+du mode, une fonction peut être optimale pour un mode et  ne pas l'être pour l'autre
+(c.f. pour $n=5$).
+
+Un second  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 
 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 
+de configurations qu'on ne peut pas atteindre en une itération est de: 

 \begin{itemize}
 \begin{itemize}

-\item $2^n-n$ en marchant, ce qui représente $\dfrac{2^n-n}{2^n} = 1-\dfrac{n}{2^n}$ 
+\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 
   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 
+  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}
 
   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.
+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).

 
 

-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
+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.
 $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.
+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}.
 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.   
+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.

 
 
 
 
 
 


@@ -800,9 +825,9 @@ $$
 \hline
 \textrm{Itérations} & 4 & 5 & 6 & 7 & 8 \\ 
 \hline
 \hline
 \textrm{Itérations} & 4 & 5 & 6 & 7 & 8 \\ 
 \hline

-\textrm{Unaires}         &  19.0 & 22.2905097109  & 23.6954895899 & 25.2661942985 & 27.0\\  
+\textrm{Unaires}         &  19.0 & 22.3  & 23.7 & 25.3 & 27.0\\  

 \hline
 \hline

-\textrm{Généralisées}          &  17   & 13             & 11            & 10 & 9\\
+\textrm{Généralisées}    &  17   & 13    & 11   & 10   & 9\\

 \hline
 \end{array}
 $$
 \hline
 \end{array}
 $$


@@ -813,18 +838,43 @@ $$
 
 
 
 
 
 

-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 
+\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).
 \emph{National Institute of Standards and Technology} (NIST).

+En interne, c'est l'implantation de l'algorithme de Mersenne Twister qui
+permet de générer la stratégie aléatoire.
+
+
+
+

  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\%$.
  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. 
+
+
+Les tableau~\ref{fig:TEST:generalise} donnent
+une vision synthétique de ces expérimentations. 
+Nous avons évalué les fonctions préfixées par 
+$f$ (respecitvement $g$) avec les générateurs issus des itérations 
+généralisées (resp. unaires).
+Quelle que soit la méthode utilisée, on constate que chacun des 
+générateurs passe 
+avec succes le test de NIST. 
+
+Interpréter ces resultats en concluant que ces générateurs sont 
+tous équivalents serait erroné: la meilleur des 
+méthodes basées sur le mode des itérations
+généralisées (pour $n=8$ par exemple) 
+est au moins deux fois plus rapide que la meilleur de celles qui 
+sont basées sur les itérations unaires.
+
+
+

 
 %%%%%%%%% Relancer pour n=6, n=7, n=8
 %%%%%%%%% Recalculer le MT
 
 %%%%%%%%% Relancer pour n=6, n=7, n=8
 %%%%%%%%% Recalculer le MT


@@ -834,27 +884,106 @@ passent avec succès cette batterie de tests.
 \begin{table}[ht]
   \centering
   \begin{scriptsize}
 \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}
+
+
+\begin{tabular}{|l|r|r|r|r|}
+ \hline 
+Test & $f^{*5}$ &$f^{*6}$ &$f^{*7}$ &$f^{*8}$ \\ \hline 
+Fréquence (Monobit)& 0.401 (0.97)& 0.924 (1.0)& 0.779 (0.98)& 0.883 (0.99)\\ \hline 
+Fréquence ds un bloc& 0.574 (0.98)& 0.062 (1.0)& 0.978 (0.98)& 0.964 (0.98)\\ \hline 
+Somme Cumulé*& 0.598 (0.975)& 0.812 (1.0)& 0.576 (0.99)& 0.637 (0.99)\\ \hline 
+Exécution& 0.998 (0.99)& 0.213 (0.98)& 0.816 (0.98)& 0.494 (1.0)\\ \hline 
+Longue exécution dans un bloc& 0.085 (0.99)& 0.971 (0.99)& 0.474 (1.0)& 0.574 (0.99)\\ \hline 
+Rang& 0.994 (0.96)& 0.779 (1.0)& 0.191 (0.99)& 0.883 (0.99)\\ \hline 
+Fourier rapide& 0.798 (1.0)& 0.595 (0.99)& 0.739 (0.99)& 0.595 (1.0)\\ \hline 
+Patron sans superposition*& 0.521 (0.987)& 0.494 (0.989)& 0.530 (0.990)& 0.520 (0.989)\\ \hline 
+Patron avec superposition& 0.066 (0.99)& 0.040 (0.99)& 0.304 (1.0)& 0.249 (0.98)\\ \hline 
+Statistiques universelles& 0.851 (0.99)& 0.911 (0.99)& 0.924 (0.96)& 0.066 (1.0)\\ \hline 
+Entropie approchée (m=10)& 0.637 (0.99)& 0.102 (0.99)& 0.115 (0.99)& 0.350 (0.98)\\ \hline 
+Suite aléatoire *& 0.573 (0.981)& 0.144 (0.989)& 0.422 (1.0)& 0.314 (0.984)\\ \hline 
+Suite aléatoire variante *& 0.359 (0.968)& 0.401 (0.982)& 0.378 (0.989)& 0.329 (0.985)\\ \hline 
+Série* (m=10)& 0.469 (0.98)& 0.475 (0.995)& 0.473 (0.985)& 0.651 (0.995)\\ \hline 
+Complexité linaire& 0.129 (1.0)& 0.494 (1.0)& 0.062 (1.0)& 0.739 (1.0)\\ \hline 
+
+\end{tabular}

   \end{scriptsize}
   \end{scriptsize}

-\label{fig:TEST}\caption{Test de NIST réalisé sur les fonctions $f^*$ détaillées au tableau~\label{table:functions}}
+
+
+\caption{Test de NIST pour les fonctions 
+  du tableau~\ref{table:functions} selon les itérations généralisées}\label{fig:TEST:generalise}

 \end{table}
 
 \end{table}
 

+
+\begin{table}[ht]
+  \centering
+  \begin{scriptsize}
+\begin{tabular}{|l|r|r|r|r|}
+\hline 
+Test & $g^{*5}$& $g^{*6}$& $f^{*7}$& $f^{*8}$\\ \hline 
+Fréquence (Monobit)& 0.236 (1.0)& 0.867 (0.99)& 0.437 (0.99)& 0.911 (1.0)\\ \hline 
+Fréquence ds un bloc& 0.129 (0.98)& 0.350 (0.99)& 0.366 (0.96)& 0.657 (1.0)\\ \hline 
+Somme Cumulé*& 0.903 (0.995)& 0.931 (0.985)& 0.863 (0.995)& 0.851 (0.995)\\ \hline 
+Exécution& 0.699 (0.98)& 0.595 (0.99)& 0.181 (1.0)& 0.437 (0.99)\\ \hline 
+Longue exécution dans un bloc& 0.009 (0.99)& 0.474 (0.97)& 0.816 (1.0)& 0.051 (1.0)\\ \hline 
+Rang& 0.946 (0.96)& 0.637 (0.98)& 0.494 (1.0)& 0.946 (1.0)\\ \hline 
+Fourier rapide& 0.383 (0.99)& 0.437 (1.0)& 0.616 (0.98)& 0.924 (0.99)\\ \hline 
+Patron sans superposition*& 0.466 (0.990)& 0.540 (0.989)& 0.505 (0.990)& 0.529 (0.991)\\ \hline 
+Patron avec superposition& 0.202 (0.96)& 0.129 (0.98)& 0.851 (0.99)& 0.319 (0.98)\\ \hline 
+Statistiques universelles& 0.319 (0.97)& 0.534 (0.99)& 0.759 (1.0)& 0.657 (0.99)\\ \hline 
+Entropie approchée (m=10)& 0.075 (0.97)& 0.181 (0.99)& 0.213 (0.98)& 0.366 (0.98)\\ \hline 
+Suite aléatoire *& 0.357 (0.986)& 0.569 (0.991)& 0.539 (0.987)& 0.435 (0.992)\\ \hline 
+Suite aléatoire variante *& 0.398 (0.989)& 0.507 (0.986)& 0.668 (0.991)& 0.514 (0.994)\\ \hline 
+Série* (m=10)& 0.859 (0.995)& 0.768 (0.99)& 0.427 (0.995)& 0.637 (0.98)\\ \hline 
+Complexité linaire& 0.897 (0.99)& 0.366 (0.98)& 0.153 (1.0)& 0.437 (1.0)\\ \hline 
+
+\end{tabular}
+\end{scriptsize}
+
+
+\caption{Test de NIST pour les fonctions 
+  du tableau~\ref{table:functions} selon les itérations unaires}\label{fig:TEST:unaire}
+\end{table}
+
+
+\begin{table}[ht]
+  \centering
+  \begin{scriptsize}
+
+\begin{tabular}{|l|r|r|r|r|}
+ \hline 
+Test & 5 bits& 6 bits & 7 bits & 8bits  \\ \hline 
+Fréquence (Monobit)& 0.289 (1.0)& 0.437 (1.0)& 0.678 (1.0)& 0.153 (0.99)\\ \hline 
+Fréquence ds un bloc& 0.419 (1.0)& 0.971 (0.98)& 0.419 (0.99)& 0.275 (1.0)\\ \hline 
+Somme Cumulé*& 0.607 (0.99)& 0.224 (0.995)& 0.645 (0.995)& 0.901 (0.99)\\ \hline 
+Exécution& 0.129 (0.99)& 0.005 (0.99)& 0.935 (0.98)& 0.699 (0.98)\\ \hline 
+Longue exécution dans un bloc& 0.514 (1.0)& 0.739 (0.99)& 0.994 (1.0)& 0.834 (0.99)\\ \hline 
+Rang& 0.455 (0.97)& 0.851 (0.99)& 0.554 (1.0)& 0.964 (0.99)\\ \hline 
+Fourier rapide& 0.096 (0.98)& 0.955 (0.99)& 0.851 (0.97)& 0.037 (1.0)\\ \hline 
+Patron sans superposition*& 0.534 (0.990)& 0.524 (0.990)& 0.508 (0.987)& 0.515 (0.99)\\ \hline 
+Patron avec superposition& 0.699 (0.99)& 0.616 (0.95)& 0.071 (1.0)& 0.058 (1.0)\\ \hline 
+Statistiques universelles& 0.062 (0.99)& 0.071 (1.0)& 0.637 (1.0)& 0.494 (0.98)\\ \hline 
+Entropie approchée (m=10)& 0.897 (0.99)& 0.383 (0.99)& 0.366 (1.0)& 0.911 (0.99)\\ \hline 
+Suite aléatoire *& 0.365 (0.983)& 0.442 (0.994)& 0.579 (0.992)& 0.296 (0.993)\\ \hline 
+Suite aléatoire variante *& 0.471 (0.978)& 0.559 (0.992)& 0.519 (0.987)& 0.340 (0.995)\\ \hline 
+Série* (m=10)& 0.447 (0.985)& 0.298 (0.995)& 0.648 (1.0)& 0.352 (0.995)\\ \hline 
+Complexité linaire& 0.005 (0.98)& 0.534 (0.99)& 0.085 (0.97)& 0.996 (1.0)\\ \hline 
+
+\end{tabular}
+
+
+
+
+
+
+
+
+
+
+  \end{scriptsize}
+
+
+\caption{Test de NIST pour l'algorithme de Mersenne Twister}\label{fig:TEST:Mersenne}
+\end{table}
+
+

 %
 %