chapitre chaos repris

[hdrcouchot.git] / 14Secrypt.tex

diff --git a/14Secrypt.tex b/14Secrypt.tex
index e160bc33e869112c0452ba24ea228dbba8911b62..bc59ba13967f60550b0b442444b2f6810296579d 100644 (file)
--- a/14Secrypt.tex
+++ b/14Secrypt.tex
@@ -1,27 +1,40 @@
 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
 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
 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.
-
-
-This aim of this section is to show 
-that finding DSSC matrices from a hypercube
-is a typical finite domain satisfaction 
-problem, classically denoted as 
-Constraint Logic Programming on Finite Domains (CLPFD). 
-This part is addressed in the first section. Next, we analyse the first
-results to provide a generation of DSSC matrices with small mixing times. 
-
-\section{Programmation logique par contraintes sur des domaines finis}
+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 
+% that finding DSSC matrices from a hypercube
+% is a typical finite domain satisfaction 
+% problem, classically denoted as 
+% Constraint Logic Programming on Finite Domains (CLPFD). 
+% This part is addressed in the first section. Next, we analyse the first
+% results to provide a generation of DSSC matrices with small mixing times. 
+
+\section{Programmation logique par contraintes sur des domaines finis}\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 +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$, 
 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]
 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
 \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 +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}
       \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 +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.
 
 $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,50 +390,72 @@ 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}
 
 \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. 
 
 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 
 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}
 
 \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}
 \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}
 
 $\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.
 
 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 
 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.
 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 +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$.
 
 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$.