X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/54b170f26af2fb6bf6150f003918ac5992314293..02fd942d6a30fe7197b732c94450ca466b7a49f5:/14Secrypt.tex?ds=sidebyside

diff --git a/14Secrypt.tex b/14Secrypt.tex
index a60e4ff..bc59ba1 100644
--- a/14Secrypt.tex
+++ b/14Secrypt.tex
@@ -1,16 +1,29 @@
 On  a vu  dans  le chapitre prÃ©cÃ©dent  que  pour avoir
 un  gÃ©nÃ©rateur Ã   sortie
 uniforme, il est nÃ©cessaire que  la matrice d'adjacence du graphe d'itÃ©ration du
-systÃ¨me  soit doublement stochastique.   Nous prÃ©sentons  dans cette  partie une
-mÃ©thode permettant de gÃ©nÃ©rer de telles matrices.
-
-Les approches thÃ©oriques basÃ©es sur la programmation logique par contraintes sur
-domaines  finis ne  sont pas  envisageables en  pratique dÃ¨s  que la  taille des
-matrices considÃ©rÃ©es devient suffisamment grande.
-
+systÃ¨me  soit doublement stochastique.   Nous prÃ©sentons  dans cette  partie
+des mÃ©thodes effectives permettant de gÃ©nÃ©rer de telles matrices.
+La premiÃ¨re est basÃ©e sur la programmation logique par contraintes
+(Section~\ref{sec:plc}).
+Cependant celle-ci souffre de ne pas passer Ã  l'Ã©chelle et ne fournit pas 
+une solution en un temps raisonnable dÃ¨s que la fonction Ã  engendrer 
+porte sur un grand nombre de bits.
 Une approche plus pragmatique consiste  Ã  supprimer un cycle hamiltonien dans le
-graphe d'itÃ©rations, ce qui revient Ã  supprimer en chaque n{\oe}ud de ce graphe une
-arÃªte sortante et une arÃªte entrante.
+graphe d'itÃ©rations $\textsc{giu}(\neg)$ (section~\ref{sec:hamiltonian}). 
+Pour obtenir plus rapidement une distribution uniforme, l'idÃ©al serait
+de supprimer un cycle hamiltonien qui nierait autant de fois chaque bit. 
+Cette forme de cycle est dit Ã©quilibrÃ©. La section~\ref{sub:gray} Ã©tablit le
+lien avec les codes de Gray Ã©quilibrÃ©s, Ã©tudiÃ©s dans la litÃ©rature. 
+La section suivante prÃ©sente une dÃ©marche de gÃ©nÃ©ration automatique de code de Gray Ã©quilibrÃ© (section~\ref{sec:induction}).
+La vitesse avec laquelle l'algorithme de PRNG converge en interne vers 
+une distribution unifiorme est Ã©tduiÃ©e thÃ©oriquement et pratiquement Ã  la 
+section~\ref{sec:mixing}.
+L'extension du travail aux itÃ©rations gÃ©nÃ©ralisÃ©es est prÃ©sentÃ© Ã  la 
+section~\ref{sec:prng:gray:general}.
+Finalement, des instances de PRNGS engendrÃ©s selon les mÃ©thodes dÃ©taillÃ©es dans 
+ce chapitre sont prÃ©sentÃ©s en section~\ref{sec:prng;gray:tests}.
+Les sections~\ref{sec:plc} Ã ~\ref{sub:gray} ont Ã©tÃ© publiÃ©es 
+Ã ~\ref{chgw+14:oip}.
 
 
 % This aim of this section is to show 
@@ -21,7 +34,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. 
 
-\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 
@@ -94,7 +107,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 +127,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 +139,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,57 +195,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}
-            $ \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}
 
 
 
 
-\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}
 
-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.
 
-\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
@@ -293,15 +329,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.
 
-\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
@@ -354,50 +390,72 @@ vÃ©rifiant $\sum_{i=1}^nNT_n(i) = 2^n$.
   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
-algorithme inductif  pour gÃ©nÃ©rer  des codes  de Gray Ã©quilibrÃ©s  de $n$  bits Ã 
-partir   de  codes   de  $n-2$   bits.   Cependant,   leur  mÃ©thode   n'est  pas
-constructive. En effet, elle effectue  des manipulations sur un partitionnement du
-code de Gray  initial de $n-2$ bits pour  obtenir un code de Gray  sur $n$ bits,
-mais le  rÃ©sultat n'est pas  systÃ©matiquement Ã©quilibrÃ©. Il est  donc nÃ©cessaire
-d'Ã©valuer les rÃ©sultats obtenus Ã   partir de tous les partitionnements rÃ©alisables
-en suivant les  contraintes spÃ©cifiÃ©es.  Or, le nombre  de possibilitÃ©s augmente
-exponentiellement (voir~\cite{Mons14} pour  l'Ã©valuation dÃ©taillÃ©e), ce qui rend
-dÃ©raisonnable    tout   parcours    exhaustif.    Une    amÃ©lioration   proposÃ©e
-dans~\cite{Mons14} permet  de rÃ©duire le nombre  de partitionnements considÃ©rÃ©s,
-mais l'ordre  de grandeur  reste similaire. On  constate donc clairement  ici la
-nÃ©cessitÃ© de trouver  des algorithmes de gÃ©nÃ©ration de  codes de Gray Ã©quilibrÃ©s
-plus  efficaces.  Ce  problÃ¨me  reprÃ©sente  une des  voies  que nous  souhaitons
-explorer dans la suite de nos travaux.
-
-Le   tableau~\ref{table:nbFunc}  donne  le   nombre  de   fonctions  diffÃ©rentes
-compatibles avec les codes de  Gray Ã©quilibrÃ©s gÃ©nÃ©rÃ©s par l'approche prÃ©cÃ©dente
-selon le nombre  de bits. Il donne  donc la taille de la  classe des gÃ©nÃ©rateurs
-pouvant Ãªtre produits.  Les  cas 7 et 8 ne sont que  des bornes minimales basÃ©es
-sur des sous-ensembles des partitionnements possibles.
+De nombreuses approches ont Ã©tÃ© developpÃ©es pour rÃ©soudre le problÃ¨me de construire
+un code de Gray dans un $\mathsf{N}$-cube~\cite{Robinson:1981:CS,DBLP:journals/combinatorics/BhatS96,ZanSup04}, 
+selon les propriÃ©tÃ©s que doit vÃ©rifier ce code.
+
+Dans les travaux~\cite{Robinson:1981:CS}, les auteurs 
+proposent une approche inductive de construction de code de Gray Ã©quilibrÃ©s 
+(on passe du $\mathsf{N}-2$ Ã  $\mathsf{N}$)
+pour peu que l'utilisateur fournisse une sous-sÃ©quence possÃ©dant certaines 
+propriÃ©tÃ©s Ã  chaque pas inductif.
+Ce travail a Ã©tÃ© renforcÃ© dans ~\cite{DBLP:journals/combinatorics/BhatS96}
+oÃ¹ les auteurs donnent une maniÃ¨re explicite de construire une telle sous-sÃ©quence.
+Enfin, les autheurs de~\cite{ZanSup04} prÃ©sentent une extension de l'algorithme de
+\emph{Robinson-Cohn}. La prÃ©sentation rigoureuse de cette extension leur permet 
+principalement de prouver que si $\mathsf{N}$ est une puissance de 2, 
+le code de Gray Ã©quilibrÃ© engendrÃ© par l'extension est toujours totalement Ã©quilibrÃ© et 
+que $S_{\mathsf{N}}$ est la sÃ©quence de transition d'un code de Gray de $\mathsf{N}$ bits 
+si  $S_{\mathsf{N}-2}$ l'est aussi.. 
+Cependant les auteurs ne prouvent pas que leur approche fournit systÃ©matiquement  
+un code de Gray (totalement) Ã©quilibrÃ©. 
+Cette section montre que ceci est vrai en rappelant tout d'abord
+l'extension de l'algorithme de \emph{Robinson-Cohn} pour un 
+code de Gray avec $\mathsf{N}-2$ bits.
 
-\begin{table}[ht]
-  \begin{center}
-    \begin{tabular}{|l|c|c|c|c|c|}
-      \hline
-      $n$              & 4 & 5 & 6    & 7      & 8      \\
-      \hline
-      nb. de fonctions & 1 & 2 & 1332 & $>$ 2300 & $>$ 4500 \\
-      \hline
-    \end{tabular}
-  \end{center}
-\caption{Nombre de codes de Gray Ã©quilibrÃ©s selon le nombre de bits.}\label{table:nbFunc}
-\end{table}
+\begin{enumerate}
+\item \label{item:nondet}Soit $l$ un entier positif pair. Trouver des sous-sequences 
+$u_1, u_2, \dots , u_{l-2}, v$ (possiblement vides) de $S_{\mathsf{N}-2}$ 
+telles que $S_{\mathsf{N}-2}$ est la concatÃ©nation de  
+$$
+s_{i_1}, u_0, s_{i_2}, u_1, s_{i_3}, u_2, \dots , s_{i_l-1}, u_{l-2}, s_{i_l}, v
+$$
+oÃ¹ $i_1 = 1$, $i_2 = 2$, et $u_0 = \emptyset$ (la sÃ©quence vide).
+\item\label{item:u'} Remplacer dans $S_{\mathsf{N}-2}$ les sequences $u_0, u_1, u_2, \ldots, u_{l-2}$ 
+  par 
+  $\mathsf{N} - 1,  u'(u_1,\mathsf{N} - 1, \mathsf{N}) , u'(u_2,\mathsf{N}, \mathsf{N} - 1), u'(u_3,\mathsf{N} - 1,\mathsf{N}), \dots, u'(u_{l-2},\mathsf{N}, \mathsf{N} - 1)$
+  respectivement, oÃ¹ $u'(u,x,y)$ est la sÃ©quence $u,x,u^R,y,u$ telle que 
+  $u^R$ est $u$, mais dans l'ordre inverse. La sÃ©quence obtenue est ensuite notÃ©e $U$.
+\item\label{item:VW} Contruire les sÃ©quences $V=v^R,\mathsf{N},v$, $W=\mathsf{N}-1,S_{\mathsf{N}-2},\mathsf{N}$. Soit  alors $W'$ dÃ©finie commÃ© Ã©tant Ã©gale Ã  $W$ sauf pour les 
+deux premiers Ã©lÃ©ments qui ont Ã©tÃ© intervertis.
+\item La sÃ©quence de transition  $S_{\mathsf{N}}$ est la concatenation $U^R, V, W'$.
+\end{enumerate} 
+
+L'Ã©tape~(\ref{item:nondet}) n'est pas constructive: il n'est pas prÃ©cisÃ©
+comment sÃ©lectionner des sous-sÃ©quences qui assurent que le code obtenu est Ã©quilibrÃ©.
+La thÃ©oreme suivante montre que c'est possible et sa preuve explique comment le faire. 
+
+
+\begin{theorem}\label{prop:balanced}
+Soit $\mathsf{N}$ dans $\Nats^*$, et $a_{\mathsf{N}}$ dÃ©fini par 
+$a_{\mathsf{N}}= 2 \left\lfloor \dfrac{2^{\mathsf{N}}}{2\mathsf{N}} \right\rfloor$. 
+il existe une sÃ©quence $l$ dans l'Ã©tape~(\ref{item:nondet}) de l'extension
+de l'algorithme de \emph{Robinson-Cohn} extension telle que 
+le nombres de transitions $\textit{TC}_{\mathsf{N}}(i)$ 
+sont tous $a_{\mathsf{N}}$ ou $a_{\mathsf{N}}+2$ 
+pour chaque  $i$, $1 \le i \le \mathsf{N}$.
+\end{theorem}
 
+La preuve de ce thÃ©orÃ¨me est donnÃ©e en annexes~\ref{anx:generateur}.
 
-Ces fonctions Ã©tant gÃ©nÃ©rÃ©e, on s'intÃ©resse Ã  Ã©tudier Ã  quelle vitesse 
+Ces fonctions Ã©tant gÃ©nÃ©rÃ©es, on s'intÃ©resse Ã  Ã©tudier Ã  quelle vitesse 
 un gÃ©nÃ©rateur les embarquant converge vers la distribution uniforme.
 C'est l'objectif de la section suivante. 
 
-\section{Quantifier l'Ã©cart par rapport Ã  la distribution uniforme} 
+\section{Quantifier l'Ã©cart par rapport Ã  la distribution uniforme}\label{sec:mixing} 
 On considÃ¨re ici une fonction construite comme Ã  la section prÃ©cÃ©dente.
 On s'intÃ©resse ici Ã  Ã©tudier de maniÃ¨re thÃ©orique les 
 itÃ©rations dÃ©finies Ã  l'Ã©quation~(\ref{eq:asyn}) pour une 
@@ -518,18 +576,95 @@ Si $\tau$ est un temps d'arrÃªt fort, alors $d(t)\leq \max_{X\in\Bool^{\mathsf{N
 \P_X(\tau > t)$.
 \end{theorem}
 
+
+Soit alors $\ov{h} : \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ la fonction 
+telle que pour $X \in \Bool^{\mathsf{N}} $, 
+$(X,\ov{h}(X)) \in E$ et $X\oplus\ov{h}(X)=0^{{\mathsf{N}}-h(X)}10^{h(X)-1}$. 
+La fonction $\ov{h}$ est dite  {\it anti-involutive} si pour tout $X\in \Bool^{\mathsf{N}}$,
+$\ov{h}(\ov{h}(X))\neq X$. 
+
+
 \begin{theorem} \label{prop:stop}
-If $\ov{h}$ is bijective et telle que if for every $X\in \Bool^{\mathsf{N}}$,
+Si $\ov{h}$ is bijective et anti involutive 
 $\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 
-chemins hamiltoniens Ã©quilibrÃ©s. 
+Les dÃ©tails de la preuve sont donnÃ©s en annexes~\ref{anx:generateur}.
+On remarque tout d'abord 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.   
+
+
+Sans entrer dans les dÃ©tails de la preuve, on remarque aussi
+que le calcul  de cette borne impose uniquement que 
+pour chaque n{\oe}ud du $\mathsf{N}$-cube 
+un arc entrant et un arc sortant sont supprimÃ©s.
+Le fait qu'on enlÃ¨ve un cycle  hamiltonien et que ce dernier 
+soit Ã©quilibrÃ© n'est pas pris en compte.
 En intÃ©grant cette contrainte, la borne supÃ©rieure pourrait Ãªtre rÃ©duite.
 
-\section{Et les itÃ©rations gÃ©nÃ©ralisÃ©es?}
+En effet, le temps de mixage est en $\Theta(N\ln N)$ lors d'une
+marche alÃ©atoire classique paresseuse dans le $\mathsf{N}$-cube.
+On peut ainsi conjecturer que cet ordre de grandeur reste le mÃªme 
+dans le contexte du $\mathsf{N}$-cube privÃ© d'un chemin hamiltonien.
+
+On peut Ã©valuer ceci pratiquement: pour une fonction
+$f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ et une graine initiale
+$x^0$, le code donnÃ© Ã  l'algorithme algorithm~\ref{algo:stop} retourne le 
+nombre d'itÃ©rations suffisant tel que tous les Ã©lÃ©ments $\ell\in \llbracket 1,{\mathsf{N}} \rrbracket$ sont Ã©quitables. Il permet de dÃ©duire une approximation de $E[\ts]$
+en l'instanciant un grand nombre de fois: pour chaque nombre $\mathsf{N}$, 
+$ 3 \le \mathsf{N} \le 16$, 10 fonctionss ont Ã©tÃ© gÃ©nÃ©rÃ©es comme dans 
+ce chapitre. Pour chacune d'elle, le calcul d'une approximation de $E[\ts]$
+est exÃ©cutÃ© 10000 fois avec une graine alÃ©atoire.La Figure~\ref{fig:stopping:moy}
+rÃ©sume ces resultats. Dans celle-ci, un cercle  reprÃ©sente une approximation de 
+$E[\ts]$ pour un  $\mathsf{N}$ donnÃ© tandis que la courbe est une reprÃ©sentation de 
+la fonction $x \mapsto 2x\ln(2x+8)$. 
+On  cosntate que l'approximation de $E[\ts]$ est largement infÃ©rieure 
+Ã  la borne quadratique donnÃ©e au thÃ©rÃ¨me~\ref{prop:stop} et que la conjecture 
+donnÃ©e au paragraphe prÃ©cÃ©dent est sensÃ©e.
+
+
+\begin{algorithm}[ht]
+%\begin{scriptsize}
+\KwIn{a function $f$, an initial configuration $x^0$ ($\mathsf{N}$ bits)}
+\KwOut{a number of iterations $\textit{nbit}$}
+
+$\textit{nbit} \leftarrow 0$\;
+$x\leftarrow x^0$\;
+$\textit{fair}\leftarrow\emptyset$\;
+\While{$\left\vert{\textit{fair}}\right\vert < \mathsf{N} $}
+{
+        $ s \leftarrow \textit{Random}(\mathsf{N})$ \;
+        $\textit{image} \leftarrow f(x) $\;
+        \If{$\textit{Random}(1) \neq 0$ and $x[s] \neq \textit{image}[s]$}{
+            $\textit{fair} \leftarrow \textit{fair} \cup \{s\}$\;
+            $x[s] \leftarrow \textit{image}[s]$\;
+          }
+        $\textit{nbit} \leftarrow \textit{nbit}+1$\;
+}
+\Return{$\textit{nbit}$}\;
+%\end{scriptsize}
+\caption{Pseudo Code of stoping time calculus }
+\label{algo:stop}
+\end{algorithm}
+
+
+\begin{figure}
+\centering
+\includegraphics[width=0.49\textwidth]{images/complexityET}
+\caption{Average Stopping Time Approximation}\label{fig:stopping:moy}
+\end{figure}
+
+
+
+
+\section{Et les itÃ©rations gÃ©nÃ©ralisÃ©es?}\label{sec:prng:gray:general}
 Le chaptire prÃ©cÃ©dent a prÃ©sentÃ© un algorithme de 
 PRNG construit Ã  partir d'itÃ©rations unaires. 
 On pourrait penser que cet algorithme est peu efficace puisqu'il 
@@ -538,9 +673,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.
-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)}
@@ -567,6 +702,399 @@ 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 Ã  
-l'algorithme~\ref{CI Algorithm}.
+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|c|l|c|c|}
+        \hline
+        $n$ & fonction  & $f(x)$, $f(x)$ pour $x \in [0,1,2,\hdots,2^n-1]$                 & $b$ & $b'$ \\ 
+        \hline
+        4 & $f^{*4}$ & [13,10,9,14,3,11,1,12,15,4,7,5,2,6,0,8]                          & \textbf{17}  & \textbf{38}   \\
+        \hline
+         \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
+        \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
+         \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}
+\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  
+Ã  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}$ 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
+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 
+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.3  & 23.7 & 25.3 & 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}\label{sec:prng;gray:tests}
+
+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).
+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\%$.
+
+
+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
+%%%%%%%%% Regenerer les 10^6 bits
+%%%%%%%%% Evaluer sur NIST
+ 
+\begin{table}[ht]
+  \centering
+  \begin{scriptsize}
+
+
+\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}
+
+
+\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}
+
+
+\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}
+
+
+\section{Conclusion}
+Ce chaptitre a montrÃ© comment construire un PRNG chaotique, notamment Ã  partir 
+de codes de Gray Ã©quilibrÃ©s. Une mÃ©thode completement automatique de
+construction de ce type de codes a Ã©tÃ© prÃ©sentÃ©e Ã©tendant les mÃ©thodes 
+existantes. 
+Dans le cas des itÃ©rations unaires, 
+l'algorithme qui en dÃ©coule a un temps de mÃ©lange qui a 
+une borne sup quadratique de convergence vers la distribution uniforme. 
+Pratiquement,  ce temps de mÃ©lange se rapproche de $N\ln N$.
+Les expÃ©rimentations au travers de la batterie de test de NIST ont montrÃ©
+que toutes les propriÃ©tÃ©s statistiques sont obtenues pour
+ $\mathsf{N} = 4, 5, 6, 7, 8$.
 
