fin relecture sylvaine

[hdrcouchot.git] / 14Secrypt.tex

diff --git a/14Secrypt.tex b/14Secrypt.tex
index fd6cbaf360a09e028d485be31989a2d0bffbe8a3..5e4cafc4272a23dbcf3348975b5b5cec818ea973 100644 (file)
--- 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
 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.
+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 dite équilibré. La section~\ref{sub:gray} établit le
+lien avec les codes de Gray équilibrés, étudiés dans la litté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 uniforme est étudiée théoriquement et pratiquement à la 
+section~\ref{sec:mixing}.
+L'extension du travail aux itérations généralisées est présentée à 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 
+à~\cite{chgw+14:oip}.

 
 
 % This aim of this section is to show 
 
 
 % This aim of this section is to show 


@@ -42,10 +55,10 @@ la matrice est stochastique à droite;
 \item pour chaque indice de colonne $j$, 
   $1 \le j\le 2^{\mathsf{N}}$, ${\mathsf{N}} = \sum_{1 \le i\le 2^{\mathsf{N}}} M_{ij}$: 
   la matrice est stochastique à gauche;
 \item pour chaque indice de colonne $j$, 
   $1 \le j\le 2^{\mathsf{N}}$, ${\mathsf{N}} = \sum_{1 \le i\le 2^{\mathsf{N}}} M_{ij}$: 
   la matrice est stochastique à gauche;

-\item Toutes les éléments de la somme $\sum_{1\le k\le 2^{\mathsf{N}}}M^k$ sont strictement positif, \textit{i.e.}, le graphe $\textsc{giu}(f)$ est fortement connexe;
+\item Tous les éléments de la somme $\sum_{1\le k\le 2^{\mathsf{N}}}M^k$ sont strictement positifs, \textit{i.e.}, le graphe $\textsc{giu}(f)$ est fortement connexe;

 \end{enumerate}
 Ce problème s'exprime sur des domaines finis entiers avec des opérateurs  
 \end{enumerate}
 Ce problème s'exprime sur des domaines finis entiers avec des opérateurs  

-arithmétiques simples (sommes et produits). il pourrait théoriquement être 
+arithmétiques simples (sommes et produits). Il pourrait théoriquement être 

 traité par des démarches de programmation logique par contrainte
 sur des domaines finis (comme en PROLOG).
 L'algorithme donné en Figure~\ref{fig:prolog}
 traité par des démarches de programmation logique par contrainte
 sur des domaines finis (comme en PROLOG).
 L'algorithme donné en Figure~\ref{fig:prolog}


@@ -56,8 +69,8 @@ ici pour  $\mathsf{N} = 2$. Dans ce code,
 \verb+summ(+$X,Y,R$\verb+)+ 
 valent True si et seulement si $R$ 
 est le produit matriciel  (ou la somme matricielle) 
 \verb+summ(+$X,Y,R$\verb+)+ 
 valent True si et seulement si $R$ 
 est le produit matriciel  (ou la somme matricielle) 

-entre  $X$ and $Y$ respectivement. 
-il n'est pas difficile d'adapter ce code à n'importe quelle valeur 
+entre  $X$ et $Y$ respectivement. 
+Il n'est pas difficile d'adapter ce code à n'importe quelle valeur 

 entière naturelle  $\mathsf{N}$.  
 
 \begin{figure}[ht]
 entière naturelle  $\mathsf{N}$.  
 
 \begin{figure}[ht]


@@ -87,15 +100,15 @@ bistoc(X):-
 \end{figure}
 
 Enfin, on définit la relation $\mathcal{R}$, qui est établie pour les deux 
 \end{figure}
 
 Enfin, on définit la relation $\mathcal{R}$, qui est établie pour les deux 

-fonctions  $f$ et $g$ si leur graphes 
-respectifs  $\textsf{giu}(f)$ et $\textsf{giu}(g)$ 
+fonctions  $f$ et $g$ si leurs graphes 
+respectifs  $\textsc{giu}(f)$ et $\textsc{giu}(g)$ 

 sont isomorphes.
 C'est évidemment une relation d'équivalence.
 
 
 
 %\subsection{Analyse de l'approche}\label{sub:prng:ana}
 sont isomorphes.
 C'est évidemment une relation d'équivalence.
 
 
 
 %\subsection{Analyse de l'approche}\label{sub:prng:ana}

-Exécutée sur un ordinateur personnelle, PROLOG trouve 
+Exécutée sur un ordinateur personnel, PROLOG trouve 

 en moins d'une seconde les
 49 solutions pour  $n=2$, 
 dont 2 seulement ne sont pas équivalentes, 
 en moins d'une seconde les
 49 solutions pour  $n=2$, 
 dont 2 seulement ne sont pas équivalentes, 


@@ -107,9 +120,9 @@ Cette approche, basée sur une démarche de type \emph{générer, tester} ne peu
 pas être retenue pour $n$ de grande taille, même 
 en s'appuyant sur l'efficience de l'algorithme de backtrack natif de PROLOG.
 
 pas être retenue pour $n$ de grande taille, même 
 en s'appuyant sur l'efficience de l'algorithme de backtrack natif de PROLOG.
 

-Cependant, pour des valeurs de $n$ petites, nous avons 
+Cependant, pour des petites valeurs de $n$, nous avons 

 comparé les fonctions non équivalentes selon leur proportion
 comparé les fonctions non équivalentes selon leur proportion

-à engendrer des temps de mélange petits (cf. équation~\ref{eq:mt:ex}).
+à engendrer des temps de mélange petits (cf. équation~(\ref{eq:mt:ex})).

 
 
 
 
 
 


@@ -149,14 +162,14 @@ $$
 \end{table}
 \end{xpl}
 
 \end{table}
 \end{xpl}
 

-Une analyse syntaxique de ces fonctions ne permet pas, à priori, 
+Une analyse syntaxique de ces fonctions ne permet pas, a priori, 

 de déduire des règles permettant de construire de nouvelles
 de déduire des règles permettant de construire de nouvelles

-fonction dont le temps de mélange serait faible.
+fonctions dont le temps de mélange serait faible.

 Cependant, le graphe $\textsc{giu}(f^*)$ 
 (donné à la Figure~\ref{fig:iteration:f*})
 est le $3$-cube dans lequel le cycle 
 $000,100,101,001,011,111,110,010,000$ 
 Cependant, le graphe $\textsc{giu}(f^*)$ 
 (donné à la Figure~\ref{fig:iteration:f*})
 est le $3$-cube dans lequel le cycle 
 $000,100,101,001,011,111,110,010,000$ 

-a été enlevé. Dans cette figure, le le graphe $\textsc{giu}(f)$ est
+a été enlevé. Dans cette figure, le  graphe $\textsc{giu}(f)$ est

 en continu tandis que le cycle est en pointillés.
 Ce cycle qui visite chaque n{\oe}ud exactement une fois est un  
 \emph{cycle hamiltonien}.
 en continu tandis que le cycle est en pointillés.
 Ce cycle qui visite chaque n{\oe}ud exactement une fois est un  
 \emph{cycle hamiltonien}.


@@ -265,12 +278,12 @@ connexité du graphe d'itérations.
   La suppression d'un cycle hamiltonien dans une matrice de Markov $M$, issue du
   $n$-cube, produit une matrice doublement stochastique.
 \end{theorem}
   La suppression d'un cycle hamiltonien dans une matrice de Markov $M$, issue du
   $n$-cube, produit une matrice doublement stochastique.
 \end{theorem}

-\begin{Proof}
+\begin{proof}

 
 Un cycle hamiltonien passe par chaque n{\oe}ud une et une seule fois.
 Pour chaque n{\oe}ud $v$ dans le $n$-cube $C_1$,
 une arête entrante $(o,v)$ et une arête sortante $(v,e)$ 
 
 Un cycle hamiltonien passe par chaque n{\oe}ud une et une seule fois.
 Pour chaque n{\oe}ud $v$ dans le $n$-cube $C_1$,
 une arête entrante $(o,v)$ et une arête sortante $(v,e)$ 

-est ainsi enlevée.
+sont ainsi enlevées.

 Considérons un autre  $n$-cube $C_2$ auquel on ajoute les arêtes 
 pour le rendre complet. La matrice de Markov $M$ correspondante est
 remplie de $\frac{1}{2^n}$ et est doublement stochastique.
 Considérons un autre  $n$-cube $C_2$ auquel on ajoute les arêtes 
 pour le rendre complet. La matrice de Markov $M$ correspondante est
 remplie de $\frac{1}{2^n}$ et est doublement stochastique.


@@ -289,7 +302,7 @@ $2^{n-1}$ arêtes menant à $v$ qui sont enlevées.
 Dans $M$ les $2^{n-1}$ coefficients correspondants sont mis à 0 et 
 $M_{vv}$ vaut alors $\frac{2^{n-1} +1}{2}$.
 $M$ est donc doublement stochastique.
 Dans $M$ les $2^{n-1}$ coefficients correspondants sont mis à 0 et 
 $M_{vv}$ vaut alors $\frac{2^{n-1} +1}{2}$.
 $M$ est donc doublement stochastique.

-\end{Proof}
+\end{proof}

 
 
 
 
 
 


@@ -299,7 +312,7 @@ $M$ est donc doublement stochastique.
 \end{theorem}
 
 
 \end{theorem}
 
 

-\begin{Proof}
+\begin{proof}

 On considère les deux $n$-cubes $C_1$ et $C_2$ définis 
 dans la preuve du théorème~\ref{th:supprCH}.
 Dans $C_1$ on considère le cycle inverse $r$ du cycle
 On considère les deux $n$-cubes $C_1$ et $C_2$ définis 
 dans la preuve du théorème~\ref{th:supprCH}.
 Dans $C_1$ on considère le cycle inverse $r$ du cycle


@@ -307,61 +320,59 @@ hamiltonien $c$.
 Aucun arc n'appartient à la fois  à $r$ et à $c$: 
 en effet, sinon $c$ contiendrait un n{\oe}ud deux fois.
 Ainsi aucune arête de $r$ n'est enlevée dans $C_1$.
 Aucun arc n'appartient à la fois  à $r$ et à $c$: 
 en effet, sinon $c$ contiendrait un n{\oe}ud deux fois.
 Ainsi aucune arête de $r$ n'est enlevée dans $C_1$.

-Le cycle $r$ est évidement un cycle hamiltonien et contient tous les n{\oe}uds.
-Tous les n{\oe}uds de $C_1$ dans lequel $c$ a été enlevé sont accessibles 
-depuis n'importe quel n{\oe}ud. Le graphe des itérations $\textsf{giu}$ qui
+Le cycle $r$ est évidemment un cycle hamiltonien et contient tous les n{\oe}uds.
+Tous les n{\oe}uds de $C_1$ dans lesquels $c$ a été enlevé sont accessibles 
+depuis n'importe quel n{\oe}ud. Le graphe des itérations $\textsc{giu}$ qui

 étend le précédent graphe est ainsi fortement connexe. 
 
 étend le précédent graphe est ainsi fortement connexe. 
 

-\end{Proof}
+\end{proof}

 
 
 
 %Les preuves, relativement directes, sont  laissées en exercices au lecteur.  
 
 
 
 %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
+Générer un  cycle hamiltonien dans le
+$n$-cube revient à  trouver un  \emph{code de  Gray  cyclique}.  On
+rappelle qu'un code de  Gray est une  séquence de mots binaires  de taille
+fixe ($\mathsf{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.
 
 \section{Lien avec les codes de Gray cycliques (totalement) équilibrés}
 \label{sub:gray}
 
 code  de  Gray est  \emph{cyclique}  si  le premier  élément  et  le dernier  ne
 différent que par un seul bit.
 
 \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
+Un minorant du  nombre de codes  de Gray  ($\left(\frac{n*\log2}{e \log

     \log   n}\times(1  -  o(1))\right)^{2^n}$),   donnée  dans~\cite{Feder2009NTB},
 indique  une explosion combinatoire  pour notre  recherche.  Afin  de contourner
 cette  difficulté,  nous  nous   restreignons  aux  codes  induisant  un  graphe
     \log   n}\times(1  -  o(1))\right)^{2^n}$),   donnée  dans~\cite{Feder2009NTB},
 indique  une explosion combinatoire  pour notre  recherche.  Afin  de contourner
 cette  difficulté,  nous  nous   restreignons  aux  codes  induisant  un  graphe

-d'itérations $\textsf{giu}(f)$  \emph{uniforme}.  Cette uniformité se  traduit par des
+d'itérations $\textsc{giu}(f)$  \emph{uniforme}.  Cette uniformité se  traduit par des

 nombres d'arcs  équilibrés entre les  \emph{dimensions} du graphe,  la dimension
 $i$  correspondant aux  seules variations  du  bit $i$  (parmi les  $n$ bits  au
 total).   Cette  approche  revient  à  chercher  des  codes  de  Gray  cycliques
 \emph{équilibrés}.
 
 nombres d'arcs  équilibrés entre les  \emph{dimensions} du graphe,  la dimension
 $i$  correspondant aux  seules variations  du  bit $i$  (parmi les  $n$ bits  au
 total).   Cette  approche  revient  à  chercher  des  codes  de  Gray  cycliques
 \emph{équilibrés}.
 

-Un code de Gray équilibré peut être défini de la façon suivante :
-
-\begin{Def}[Code de Gray cyclique équilibré]\label{def:grayequ}
-  Soit $L = w_1,  w_2, \dots, w_{2^n}$ la séquence d'un code  de Gray cyclique à
-  $n$ bits.  Soit $S = s_1,  s_2, \dots, s_{2^n}$ la séquence des transitions où
-  $s_i$, $1  \le i \le 2^n$  est l'indice du seul  bit qui varie  entre les mots
-  $w_i$ et  $w_{i+1}$. Enfin, soit  $\textit{NT}_n : \{1,\dots,  n\} \rightarrow
-  \{0, \ldots, 2^n\}$  la fonction qui au paramètre  $i$ associe le \emph{nombre
-    de transitions} présentes dans la séquence $L$ pour le bit $i$, c'est-à-dire
-  le nombre d'occurrences de $i$ dans $S$.
+On formalise un code de Gray équilibré comme suit.
+Soit $L = w_1,  w_2, \dots, w_{2^n}$ la séquence d'un code  de Gray cyclique à
+$n$ bits.  Soit $S = s_1,  s_2, \dots, s_{2^n}$ la séquence des transitions où
+$s_i$, $1  \le i \le 2^n$  est l'indice du seul  bit qui varie  entre les mots
+$w_i$ et  $w_{i+1}$. Enfin, soit  $\textit{TC}_n : \{1,\dots,  n\} \rightarrow
+\{0, \ldots, 2^n\}$  la fonction qui au paramètre  $i$ associe le \emph{nombre
+  de transitions} présentes dans la séquence $L$ pour le bit $i$, c'est-à-dire
+le nombre d'occurrences de $i$ dans $S$.

   
   

-  Le      code       $L$      est      \textbf{équilibré}       si      $\forall
-  i,j\in\{1,...,n\},~|\textit{NT}_n(i)  -  \textit{NT}_n(j)|  \le  2$.   Il  est
-  \textbf{totalement             équilibré}             si             $\forall
-  i\in\{1,...,n\},~\textit{NT}_n(i)=\frac{2^n}{n}$.
-\end{Def}
+Le      code       $L$      est      \textbf{équilibré}       si      $\forall
+i,j\in\{1,...,n\},~|\textit{TC}_n(i)  -  \textit{TC}_n(j)|  \le  2$.   Il  est
+\textbf{totalement             équilibré}             si             $\forall
+i\in\{1,...,n\},~\textit{TC}_n(i)=\frac{2^n}{n}$.
+

 
 On peut  donc déjà déduire  qu'il ne peut  exister des codes de  Gray totalement
 équilibrés que  pour les  systèmes ayant un  nombre d'éléments $n=2^k,  k>0$. De
 
 On peut  donc déjà déduire  qu'il ne peut  exister des codes de  Gray totalement
 équilibrés que  pour les  systèmes ayant un  nombre d'éléments $n=2^k,  k>0$. De

-plus,  comme  dans tout  code  de  Gray  cyclique, $\textit{NT}_n(i)$  est  pair
+plus,  comme  dans tout  code  de  Gray  cyclique, $\textit{TC}_n(i)$  est  pair

 $\forall  i\in\{1,...,n\}$,  alors  les  systèmes  ayant  un  nombre  d'éléments
 différent  de $2^k$,  ne peuvent  avoir  que des  codes de  Gray équilibrés  avec
 $\forall  i\in\{1,...,n\}$,  alors  les  systèmes  ayant  un  nombre  d'éléments
 différent  de $2^k$,  ne peuvent  avoir  que des  codes de  Gray équilibrés  avec

-$\textit{NT}_n(i)=\lfloor\frac{2^n}{n}\rfloor$                                 ou
-$\textit{NT}_n(i)=\lceil\frac{2^n}{n}\rceil,    \forall    i\in\{1,...,n\}$   et
-vérifiant $\sum_{i=1}^nNT_n(i) = 2^n$.
+$\textit{TC}_n(i)=\lfloor\frac{2^n}{n}\rfloor$                                 ou
+$\textit{TC}_n(i)=\lceil\frac{2^n}{n}\rceil,    \forall    i\in\{1,...,n\}$   et
+vérifiant $\sum_{i=1}^n\textit{TC}_n(i) = 2^n$.

 
 \begin{xpl}
   Soit  $L^*=000,100,101,001,011,111,110,010$ le code  de Gray  correspondant au
 
 \begin{xpl}
   Soit  $L^*=000,100,101,001,011,111,110,010$ le code  de Gray  correspondant au


@@ -380,47 +391,69 @@ vérifiant $\sum_{i=1}^nNT_n(i) = 2^n$.
 \section{Génération de codes de Gray équilibrés par induction}
 \label{sec: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.
-
-\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}
-
+De nombreuses approches ont été développé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 auteurs 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
+défini à partir de la séquence $S_{\mathsf{N}-2}$.

 
 

-Ces fonctions étant générée, on s'intéresse à étudier à quelle vitesse 
+\begin{enumerate}
+\item \label{item:nondet}Soit $l$ un entier positif pair. Trouver des sous-séquences 
+$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 séquences $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} Construire les séquences $V=v^R,\mathsf{N},v$, $W=\mathsf{N}-1,S_{\mathsf{N}-2},\mathsf{N}$. Soit  alors $W'$ définie comme é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 concaténation $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é.
+Le théorème suivant montre que c'est possible et sa preuve,
+donnée en annexe~\ref{anx:generateur}, explique comment le faire. 
+
+\begin{restatable}[Existence d'un code de Gray équilibré]{theorem}{theograyequilibre}
+\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}  telle que 
+les nombres de transitions $\textit{TC}_{\mathsf{N}}(i)$ 
+valent tous $a_{\mathsf{N}}$ ou $a_{\mathsf{N}}+2$ 
+pour chaque  $i$, $1 \le i \le \mathsf{N}$.
+\end{restatable}
+
+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 


@@ -428,11 +461,11 @@ stratégie donnée.
 Tout d'abord, celles-ci peuvent être interprétées comme une marche le long d'un 
 graphe d'itérations $\textsc{giu}(f)$ tel que le choix de tel ou tel arc est donné par la 
 stratégie.
 Tout d'abord, celles-ci peuvent être interprétées comme une marche le long d'un 
 graphe d'itérations $\textsc{giu}(f)$ tel que le choix de tel ou tel arc est donné par la 
 stratégie.

-On remarque que ce graphe d'itération est toujours un sous graphe 
+On remarque que ce graphe d'itérations est toujours un sous graphe 

 du   ${\mathsf{N}}$-cube augmenté des 
 boucles sur chaque sommet, \textit{i.e.}, les arcs
 $(v,v)$ pour chaque $v \in \Bool^{\mathsf{N}}$. 
 du   ${\mathsf{N}}$-cube augmenté des 
 boucles sur chaque sommet, \textit{i.e.}, les arcs
 $(v,v)$ pour chaque $v \in \Bool^{\mathsf{N}}$. 

-Ainsi, le travail ci dessous répond à la question de 
+Ainsi, le travail ci-dessous répond à la question de 

 définir la longueur du chemin minimum dans ce graphe pour 
 obtenir une distribution uniforme.
 Ceci se base sur la théorie des chaînes de Markov.
 définir la longueur du chemin minimum dans ce graphe pour 
 obtenir une distribution uniforme.
 Ceci se base sur la théorie des chaînes de Markov.


@@ -444,6 +477,8 @@ particulièrement au chapitre sur les temps d'arrêt.
 
 
 
 
 
 

+
+

 \begin{xpl}
 On considère par exemple le graphe $\textsc{giu}(f)$ donné à la 
 \textsc{Figure~\ref{fig:iteration:f*}.} et la fonction de 
 \begin{xpl}
 On considère par exemple le graphe $\textsc{giu}(f)$ donné à la 
 \textsc{Figure~\ref{fig:iteration:f*}.} et la fonction de 


@@ -451,7 +486,7 @@ probabilités $p$ définie sur l'ensemble des arcs comme suit:
 $$
 p(e) \left\{
 \begin{array}{ll}
 $$
 p(e) \left\{
 \begin{array}{ll}

-= \frac{2}{3} \textrm{ si $e=(v,v)$ avec $v \in \Bool^3$,}\\
+= \frac{1}{2} + \frac{1}{6} \textrm{ si $e=(v,v)$ avec $v \in \Bool^3$,}\\

 = \frac{1}{6} \textrm{ sinon.}
 \end{array}
 \right.  
 = \frac{1}{6} \textrm{ sinon.}
 \end{array}
 \right.  


@@ -474,7 +509,17 @@ P=\dfrac{1}{6} \left(
 \]
 \end{xpl}
 
 \]
 \end{xpl}
 

+On remarque que dans cette marche on reste sur place avec une probabilité égale 
+à $\frac{1}{2}+\frac{1}{2\mathsf{N}}$ et l'on passe d'un sommet à son voisin
+lorsque c'est possible avec une probabilité $\frac{1}{2\mathsf{N}}$.
+Les probabilités usuelles que l'on appliquerait aux transitions de 
+l'algorithme~\ref{CI Algorithm} seraient quant à elles uniformément égales 
+à $\frac{1}{\mathsf{N}}$.
+Cette manière paresseuse d'itérer (puisqu'on reste plus souvent sur place) n'est donc pas équivalente à celle issue de l'algorithme. 

 
 

+Cependant, l'étude théorique de référence~\cite{LevinPeresWilmer2006}
+considère cette marche comme cadre. S'inspirant de 
+celle-ci, le travail suivant se replace donc dans ce cadre théorique.

 
 
 Tout d'abord, soit $\pi$ et $\mu$ deux distributions sur 
 
 
 Tout d'abord, soit $\pi$ et $\mu$ deux distributions sur 


@@ -485,7 +530,7 @@ $$\tv{\pi-\mu}=\max_{A\subset \Bool^{\mathsf{N}}} |\pi(A)-\mu(A)|.$$
 On sait que 
 $$\tv{\pi-\mu}=\frac{1}{2}\sum_{X\in\Bool^{\mathsf{N}}}|\pi(X)-\mu(X)|.$$
 De plus, si 
 On sait que 
 $$\tv{\pi-\mu}=\frac{1}{2}\sum_{X\in\Bool^{\mathsf{N}}}|\pi(X)-\mu(X)|.$$
 De plus, si 

-$\nu$ est une distribution on $\Bool^{\mathsf{N}}$, on a 
+$\nu$ est une distribution sur $\Bool^{\mathsf{N}}$, on a 

 $$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}.$$
 
 Soit $P$ une matrice d'une chaîne de Markov sur $\Bool^{\mathsf{N}}$. 
 $$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}.$$
 
 Soit $P$ une matrice d'une chaîne de Markov sur $\Bool^{\mathsf{N}}$. 


@@ -498,75 +543,99 @@ $$d(t)=\max_{X\in\Bool^{\mathsf{N}}}\tv{P^t(X,\cdot)-\pi}$$
 et
 
 $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
 et
 
 $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$

-
-Un résultat classique est
-
-$$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$
-
-
-
-
-Soit $(X_t)_{t\in \mathbb{N}}$ une suite de  variables aléatoires de 
-$\Bool^{\mathsf{N}}$.
-une variable aléatoire $\tau$ dans $\mathbb{N}$ est un  
-\emph{temps d'arrêt} pour la suite
-$(X_i)$ si pour chaque $t$ il existe $B_t\subseteq
-(\Bool^{\mathsf{N}})^{t+1}$ tel que 
-$\{\tau=t\}=\{(X_0,X_1,\ldots,X_t)\in B_t\}$. 
-En d'autres termes, l'événement $\{\tau = t \}$ dépend uniquement des valeurs 
-de  
-$(X_0,X_1,\ldots,X_t)$, et non de celles de $X_k$ pour $k > t$. 

  
  

+Intuitivement, $t_{\rm mix}(\varepsilon)$ est le nombre d'itérations nécessaire 
+pour être proche de la distribution stationnaire à $\varepsilon$ près, 
+peu importe la configuration de départ. On a le théorème suivant démontré en annexe~\ref{anx:generateur}.

 
 

-Soit $(X_t)_{t\in \mathbb{N}}$ une chaîne de Markov et 
-$f(X_{t-1},Z_t)$  une représentation fonctionnelle de celle-ci. 
-Un \emph{temps d'arrêt aléatoire} pour la chaîne de 
-Markov  est un temps d'arrêt pour 
-$(Z_t)_{t\in\mathbb{N}}$.
-Si la chaîne de Markov  est irréductible et a $\pi$
-comme distribution stationnaire, alors un 
-\emph{temps stationnaire} $\tau$ est temps d'arrêt aléatoire
-(qui peut dépendre de la configuration initiale $X$),
-tel que la distribution de $X_\tau$ est $\pi$:
-$$\P_X(X_\tau=Y)=\pi(Y).$$

 
 

+\begin{restatable}[Temps de mixage sans chemin hamiltonien]{theorem}{theotpsmix}
+\label{theo:tmps:mix}
+On considère un $\mathsf{N}$-cube dans lequel un chemin hamiltonien a été supprimé et la fonction de 
+probabilités $p$ définie sur l'ensemble des arcs comme suit:
+\[
+p(e) \left\{
+\begin{array}{ll}
+= \frac{1}{2} + \frac{1}{2\mathsf{N}} \textrm{ si $e=(v,v)$ avec $v \in \Bool^{\mathsf{N}}$,}\\
+= \frac{1}{2\mathsf{N}} \textrm{ sinon.}
+\end{array}
+\right.  
+\]

 
 

-Un temps d'arrêt  $\tau$ est qualifié de  \emph{fort} si  $X_{\tau}$ 
-est indépendant de  $\tau$.  On a les deux théorèmes suivants, dont les 
-démonstrations sont données en annexes~\ref{anx:generateur}.
+La chaîne de Markov associée converge vers la distribution uniforme et 

 
 

+\[
+\forall \varepsilon >0,\, t_{\rm mix}(\varepsilon) \le 32 {\mathsf{N}}^2+ 16{\mathsf{N}}\ln ({\mathsf{N}}+1) = O(N^2).
+\] 
+\end{restatable}
+
+
+
+Sans entrer dans les détails de la preuve, on remarque aussi
+que le calcul  de ce majorant 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, ce majorant  pourrait être réduit.
+
+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~\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 fonctions 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 résultats. 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  constate que l'approximation de $E[\ts]$ est largement inférieure 
+au majorant quadratique donné au théorème~\ref{prop:stop} et que la conjecture 
+donnée au paragraphe précédent est sensée.

 
 

-\begin{theorem}
-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}

 
 

-\begin{theorem} \label{prop:stop}
-If $\ov{h}$ is bijective et telle que if for every $X\in \Bool^{\mathsf{N}}$,
-$\ov{h}(\ov{h}(X))\neq X$, alors
-$E[\ts]\leq 8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1)$. 
-\end{theorem}
+\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 pour évaluer le temps d'arrêt}
+\label{algo:stop}
+\end{algorithm}

 
 

-Sans entrer dans les détails de la preuve, on remarque tout d'abord 
-que le calcul 
-de cette borne n'intègre pas le fait qu'on préfère enlever des 
-chemins hamiltoniens équilibrés. 
-En intégrant cette contrainte, la borne supérieure pourrait être réduite.

 
 

-On remarque ensuite que la chaîne de Markov proposée ne suit pas exactement
-l'algorithme~\ref{CI Algorithm}. En effet dans la section présente, 
-la probabilité de rester dans une configuration donnée 
-est fixée à $frac{1}{2}+\frac{1}{2n}$.
-Dans l'algorithme initial, celle-ci est de ${1}{n}$.
-Cette version, qui reste davantage sur place que l'algorithme original,
-a été introduite pour simplifier le calcul de la borne sup 
-du temps d'arrêt.   
+\begin{figure}
+\centering
+\includegraphics[width=0.49\textwidth]{images/complexityET}
+\caption{Interpolation du temps d'arrêt}\label{fig:stopping:moy}
+\end{figure}

 
 
 
 
 
 
 
 

-\section{Et les itérations généralisées?}
-Le chaptire précédent a présenté un algorithme de 
+\section{Et les itérations généralisées?}\label{sec:prng:gray:general}
+Le chapitre 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 
 dispose d'une fonction $f$ de $\Bool^n$ dans lui même mais il ne modifie à 
 PRNG construit à partir d'itérations unaires. 
 On pourrait penser que cet algorithme est peu efficace puisqu'il 
 dispose d'une fonction $f$ de $\Bool^n$ dans lui même mais il ne modifie à 


@@ -599,7 +668,7 @@ la ligne $s\leftarrow{\textit{Set}(\textit{Random}(2^n))}$ est différente.
 Dans celle-ci la fonction  $\textit{Set}   :    \{1,\ldots,2^n\}   \rightarrow
 \mathcal{P}(\{1,\ldots   n\})$   retourne  l'ensemble   dont   la   fonction
 caractéristique  serait  représentée par  le  nombre  donné  en argument.
 Dans celle-ci la fonction  $\textit{Set}   :    \{1,\ldots,2^n\}   \rightarrow
 \mathcal{P}(\{1,\ldots   n\})$   retourne  l'ensemble   dont   la   fonction
 caractéristique  serait  représentée par  le  nombre  donné  en argument.

-Par exemple, pour $n=3$, l'ensemble $\textit{Set}(6)$ vaudraitt $\{3,2\}$.
+Par exemple, pour $n=3$, l'ensemble $\textit{Set}(6)$ vaudrait $\{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$.
 


@@ -626,8 +695,9 @@ Elle n'est donc pas rappelée.
 \begin{xpl}
 
   On reprend l'exemple donné à la section~\ref{sec:plc}.
 \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 
+  On considère le cycle hamiltonien défini par la séquence
+  $000,100,101,001,011,111,110,010,000$. En supprimant celui-ci dans 
+  le $3$-cube, cela engendre 

   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},
   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},


@@ -713,48 +783,44 @@ la figure~\ref{fig:markov:f*}.
     & &  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
     & &  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

-
-
-
-
-
-
-         &$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{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 
 \end{table}
 
 Le  tableau~\ref{table:functions} reprend  une synthèse de 


@@ -762,19 +828,24 @@ 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
 à 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
+valeur de $n=7$ et $8$,  seuls $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 y 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
 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
+distribution uniforme.  On constate de  plus que ce nombre décroît avec

 le nombre d'éléments alors qu'il augmente dans l'approche initiale où 
 l'on marche.
 
 le nombre d'éléments alors qu'il augmente dans l'approche initiale où 
 l'on marche.
 


@@ -812,7 +883,7 @@ 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 le 
+On constate que le nombre d'appels par bit généré décroît avec $n$ dans le 

 cas des itérations généralisées et est toujours plus faible
 que celui des itérations unaires.
 
 cas des itérations généralisées et est toujours plus faible
 que celui des itérations unaires.
 


@@ -824,38 +895,53 @@ $$
 \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}
 $$
 \caption{Nombre moyen 
 \hline
 \end{array}
 $$
 \caption{Nombre moyen 

-  d'appels à un générateurs binaire par bit généré}\label{table:marchevssaute}
+  d'appels à un générateur binaire par bit généré}\label{table:marchevssaute}

 \end{table}
 
 
 
 
 \end{table}
 
 
 
 

-\section{Tests statistiques}
+\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).
 
 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\%$.
 
 
  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 ces expérimentations. 
+Les tableaux~\ref{fig:TEST:generalise} donnent
+une vision synthétique de ces expérimentations. 

 Nous avons évalué les fonctions préfixées par 
 Nous avons évalué les fonctions préfixées par 

-$f$ (respecitvement $g$) avec le générateur issu des itérations 
+$f$ (respectivement $g$) avec les générateurs issus des itérations 

 généralisées (resp. unaires).
 généralisées (resp. unaires).

-%L'expérience a montré notamment que toutes ces fonctions
-%passent avec succès cette batterie de tests. 
+Quelle que soit la méthode utilisée, on constate que chacun des 
+générateurs passe 
+avec succès le test de NIST. 
+
+Interpréter ces résultats en concluant que ces générateurs sont 
+tous équivalents serait erroné: la meilleure 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 meilleure de celles qui 
+sont basées sur les itérations unaires.

 
 
 
 
 
 


@@ -870,26 +956,116 @@ généralisées (resp. unaires).
   \begin{scriptsize}
 
 
   \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}
 
   \end{scriptsize}
 

-\label{fig:TEST:generalise}
+

 \caption{Test de NIST pour les fonctions 
 \caption{Test de NIST pour les fonctions 

-  du tableau~\ref{table:functions} selon les itérations généralisées}
+  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}
 \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}
 
 
 
 
   \end{scriptsize}
 

-\label{fig:TEST:unaire}
-\caption{Test de NIST pour les fonctions 
-  du tableau~\ref{table:functions} selon les itérations unaires}
+
+\caption{Test de NIST pour l'algorithme de Mersenne Twister}\label{fig:TEST:Mersenne}

 \end{table}
 
 \end{table}
 

-%
+
+\section{Conclusion}
+Ce chapitre a montré comment construire un PRNG chaotique, notamment à partir 
+de codes de Gray équilibrés. Une méthode complètement 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 
+un majorant 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$.
+