X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/d3ea167453c701385858e4db6c3dcd9df216701d..HEAD:/15RairoGen.tex?ds=sidebyside

diff --git a/15RairoGen.tex b/15RairoGen.tex
index 3c49eb6..6832d33 100644
--- a/15RairoGen.tex
+++ b/15RairoGen.tex
@@ -1,182 +1,176 @@
-Pour dÃ©crire un peu plus prÃ©cisÃ©ment le principe de
-la gÃ©nÃ©ration pseudo-alÃ©atoire, considÃ©rons l'espace boolÃ©en 
-$\Bool=\{0,1\}$
-muni des lois \og +\fg{}, \og . \fg{} et \og $\overline{\mathstrut\enskip}$ \fg{} 
-dÃ©finies par les tableaux ci-dessous:
+Au bout d'un nombre $b$ d'itÃ©rations,
+si la fonction, notÃ©e $G_{f_u}$ (ou bien $G_{f_g}$) 
+prÃ©sentÃ©e au chapitre~\ref{chap:carachaos}, 
+a de \og bonnes\fg{} propriÃ©tÃ©s chaotiques, 
+le mot $x^b$ devrait  \og sembler ne plus dÃ©pendre\fg{} de $x^0$.
+On peut penser Ã  exploiter une de ces fonctions $G_f$ 
+comme un gÃ©nÃ©rateur alÃ©atoire. 
+
+Ce chapitre  prÃ©sente donc une application directe
+de la thÃ©orie dÃ©veloppÃ©e ci-avant
+Ã  la gÃ©nÃ©ration de nombres pseudo-alÃ©atoires. 
+La section~\ref{sec:PRNG:chaos:autres} prÃ©sente un Ã©tat de l'art (incomplet) de l'exploitation de 
+fonctions au comportement chaotique pour obtenir des PRNGs.
+La section~\ref{sub:prng:algo} 
+prÃ©sente ensuite l'algorithme de PRNG. La contrainte de  
+distribution uniforme de la sortie est discutÃ©e dans cette section.
+La chaoticitÃ© du gÃ©nÃ©rateur est  Ã©tudiÃ©e en 
+section~\ref{prng:unaire:chaos}.
+La section~\ref{sub:prng:algo}  a Ã©tÃ© publiÃ©e Ã  ~\cite{bcgw11:ip,bcgr11:ip}.
+
+\section{Quelques PRNGs basÃ©s sur des fonctions aux itÃ©rations chaotiques}\label{sec:PRNG:chaos:autres}
+
+Les PRNGs chaotiques (CPRNGs) sont des gÃ©nÃ©rateurs non linÃ©aires dÃ©finis par 
+$x_0 \in \mathbb{R}$ et $x_{t+1} = f(x_t)$, oÃ¹  $f$ est une fonction au comportement chaotique.
+Les raisons qui expliquent l'intÃ©rÃªt de telles fonctions sont naturellement la sensibilitÃ© aux conditions initiales, 
+leur imprÃ©visibilitÃ©\ldots Cependant, comme l'ordinateur sur lequel elles s'exÃ©cutent a une prÃ©cision finie, 
+les gÃ©nÃ©rateurs qui les embarquent peuvent avoir des pÃ©riodes arbitrairement courtes, 
+ne pas fournir de sortie selon une distribution uniforme\ldots
+D'un point de vue cryptographique, ces CPRNGs sont critiquables~\cite{wiggins2003introduction}.
+RÃ©duire ces critiques est l'objectif de nombreux travaux de recherche reportÃ©s ci dessous.
+
+
+Parmi les suites simples classiquement embarquÃ©es dans les CPRNGs, on trouve principalement
+la suite logistique,  
+la suite de HÃ©non. 
+La suite logistique~\cite{may1976simple} est dÃ©finie de $[0;1]$ dans lui mÃªme par $x_{t+1} = r \times x_t(1-x_t)$ 
+avec $x_0 \in [0;1]$ et $3,57<r<4,0$.
+La suite de HÃ©non~\cite{henon1976two} de $A \times B$ dans lui mÃªme, avec $A$ et $B$ deux sous-ensembles de $\R$, 
+est dÃ©finie par  
+$x_{t+1} = (1-a x_t^2)+y_t$  et $y_{t+1}= bx_{t+1}$, oÃ¹ $a$ et $b$ sont les paramÃ¨tres canoniques. 
+Pour $a=1,4$, $b=0,3$, $A=[-1,5;1,5]$ et $B=-[0,4;0,4]$ le comportement de cette suite est chaotique.
+
+La suite logistique est utilisÃ©e dans l'article~\cite{dabal2011chaos} dans lequel 
+les auteurs utilisent une reprÃ©sentation des rÃ©els Ã  virgule fixe.
+Les auteurs de~\cite{dabal2012fpga} comparent leur implantation de la suite logistique avec celle 
+de la suite de HÃ©non. 
+Les auteurs de~\cite{6868789} ont exploitÃ© la rÃ©Ã©criture de la suite logistique sous la forme
+$x_{t+1} = (r \times x_t)-(r \times x_t^2)$ et la possibilitÃ© de parallÃ©liser ceci 
+pour accroÃ®tre la frÃ©quence du PRNG.   
+Les auteurs de~\cite{liu2008improved} proposent de coupler deux suites logistiques,
+chacune Ã©tant paramÃ©trÃ©e diffÃ©remment ($x_0$, $r_1$ et  $y_0$, $r_2$ respectivement). L'idÃ©e principale 
+est de modifier iterrativement le paramÃ¨tre $r_2$ Ã  l'aide des itÃ©rÃ©s de $x_t$.
+Quant aux auteurs de~\cite{merahcoupling13}, ils couplent la suite logistique et celle de HÃ©non. 
+La premiÃ¨re suite sert Ã  sÃ©lectionner les Ã©lÃ©ments parmi ceux gÃ©nÃ©rÃ©s par la seconde.
+Les auteurs de~\cite{mao2006design}, combinent spatialement $L$ suites logistiques 
+et construisent ainsi $x_t(0)$, \dots, $x_t(L-1)$ selon l'Ã©quation suivante:
+\begin{equation}
+x_{t+1}(i) = 
+(1- \varepsilon) f(x_t(i)) + 
+\frac{\varepsilon}{2} 
+(f(x_t(i-1)) + f(x_t(i+1))),
+\label{eq:cml}
+\end{equation}
+\noindent oÃ¹ 
+$i \in \dfrac{\Z}{L\Z}$,
+$f$ est une adaptation de la suite logistique au cas discret,
+la graine $(X_0(0),\dots, X_0(L-1))$ et la pondÃ©ration $\varepsilon$ sont fournies par l'utilisateur.
+ 
 
-\begin{minipage}{0.33\textwidth}
-  \begin{center}
-  \begin{tabular}{|c|c|c|}
-    \hline 
-    + & 0& 1 \\
-    \hline 
-    0 & 0& 1 \\
-    \hline 
-    1 & 1& 1 \\
-    \hline
-  \end{tabular}
-\end{center}
-\end{minipage}
-\begin{minipage}{0.33\textwidth}
-  \begin{center}
-  \begin{tabular}{|c|c|c|}
-    \hline 
-    . & 0& 1 \\
-    \hline 
-    0 & 0& 0 \\
-    \hline 
-    1 & 0& 1 \\
-    \hline
-  \end{tabular}
-\end{center}
-\end{minipage}
-\begin{minipage}{0.32\textwidth}
-  \begin{center}
-  \begin{tabular}{|c|c|c|}
-    \hline 
-     & 0& 1 \\
-    \hline 
-    $\overline{\mathstrut\enskip}$ & 1& 0 \\
-    \hline 
-   \end{tabular}
-\end{center}
-\end{minipage}
+RenÃ© Lozi a aussi Ã©tudiÃ© la construction de PRNGs en couplant 
+des suites de Lozi~\cite{espinelrojas:hal-00622989} (qui sont une variation des suites de HÃ©non: $x^2_t$ est remplacÃ© par $| x_t|$),
+la suite tente~\cite{DBLP:journals/ijbc/Lozi12} et en extrayant des 
+sous-suites pour construire la sortie du PRNG~\cite{lozi:hal-00813087}. 
+ 
+ 
 
 
-La fonction itÃ©rÃ©e est
-une fonction $f$ de $\Bool^n$ dans lui-mÃªme qui Ã 
-un mot binaire $x = (x_1,\ldots,x_n)$ 
-associe le mot $(f_1(x),\ldots, f_n(x))$.
-Un exemple de fonction de $\Bool^n$ dans lui-mÃªme
-est la fonction nÃ©gation 
-dÃ©finie par  
-$\neg(x)=(\overline{x_1},\dots,\overline{x_n})$. 
+Certaines Ã©quations diffÃ©rentielles ont Ã©tÃ© Ã  la base de PRNGs chaotiques. 
+On pense aux Ã©quations de Lorenz~\cite{Lorenz1963}, Ã  celles de RÃ¶ssler~\cite{Rossler1976397}\ldots
+Celles-ci ont par exemple embarquÃ©es dans les PRNG dans les articles~\cite{Silva:2009:LLP:1592409.1592411}
+et~\cite{mansingka2013fibonacci} respectivement.
 
-Le principe itÃ©ratif est le suivant: 
-Ã  chaque itÃ©ration $t$, on choisit un indice $i$ entre $1$ et $n$,
-et le mot $x^t = (x_1^t,\ldots,x_n^t)$ est remplacÃ© par
-$x^{t+1} = (x_1^t,\ldots , x_{i-1}^t, f_i(x^t), x_{i+1}^t,\ldots, x_n^t)$.
 
-Au bout d'un nombre $N$ d'itÃ©rations,
-si la fonction, notÃ©e $G_f$ dans ce document, 
-que l'on peut associer Ã  l'algorithme dÃ©crit ci-dessus
-a de \og bonnes\fg{} propriÃ©tÃ©s chaotiques, 
-le mot $x^N$ doit Ãªtre \og trÃ¨s diffÃ©rent\fg{} de $x^0$ 
-de faÃ§on Ã  mÃªme sembler ne plus dÃ©pendre de $x_0$:
-pour un gÃ©nÃ©rateur alÃ©atoire, il faut que la structure de 
-$x^N$ semble Ãªtre due au hasard; 
-pour une application cryptographique, il faut qu'il
-soit matÃ©riellement impossible (dans les conditions techniques actuelles) 
-de retrouver $x^0$ Ã  partir de $x^N$.
-
-Tous les mots de 
-$\Bool^n$ peuvent constituer les
-$2^n$ sommets d'un \gls{graphoriente} (cf. glossaire)
-dans lequel un arc relie deux sommets $x$ et $x'$ 
-s'il existe une itÃ©ration de l'algorithme
-de gÃ©nÃ©ration qui permet de passer de $x$ Ã  $x'$. 
-Ce graphe est appelÃ© le graphe d'itÃ©rations et 
-ce document montre que si l'on a un \gls{graphfortementconnexe} (cf. glossaire),
-alors la fonction $G_f$ est transitive, donc chaotique.
-
-Enfin, un bon gÃ©nÃ©rateur alÃ©atoire se doit de 
-fournir  des nombres selon une \gls{distributionuniforme} (cf. glossaire). 
-La derniÃ¨re partie de ce document donnera, 
-dans le cas oÃ¹ le graphe d'itÃ©rations est fortement connexe, 
-une condition nÃ©cessaire est suffisante pour que
-cette propriÃ©tÃ© soit satisfaite.
-
-
- Cette section prÃ©sente une application directe de la thÃ©orie dÃ©veloppÃ©e ci-avant
-Ã  la gÃ©nÃ©ration de nombres pseudo alÃ©atoires. On prÃ©sente tout d'abord le gÃ©nÃ©rateur
-basÃ© sur des fonctions chaotiques (section~\ref{sub:prng:algo}), 
-puis comment intÃ©grer la contrainte de \gls{distributionuniforme} 
-(cf. glossaire) de la sortie 
-dans le choix de la fonction Ã  itÃ©rer (section~\ref{sub:prng:unif}). 
-L'approche est Ã©valuÃ©e dans la derniÃ¨re section.
- 
 
-\subsection{ GÃ©nÃ©rateur de nombres pseudo alÃ©atoires basÃ© sur le chaos}\label{sub:prng:algo}
+
+\section{Nombres pseudo-alÃ©atoires construits par itÃ©rations unaires}\label{sub:prng:algo}
 
 
 
 
 
-On peut penser Ã  construire un gÃ©nÃ©rateur de nombres pseudo 
-alÃ©atoires comme dans l'algorithme~\ref{CI Algorithm} donnÃ© ci-dessous.
 
 \begin{algorithm}[h]
 %\begin{scriptsize}
 \KwIn{une fonction $f$, un nombre d'itÃ©rations $b$, 
-une configuration initiale $x^0$ ($n$ bits)}
-\KwOut{une configuration $x$ ($n$ bits)}
+une configuration initiale $x^0$ (${\mathsf{N}}$ bits)}
+\KwOut{une configuration $x$ (${\mathsf{N}}$ bits)}
 $x\leftarrow x^0$\;
-$k\leftarrow b + \textit{Random}(b+1)$\;
 %$k\leftarrow b + \textit{XORshift}(b+1)$\;
-\For{$i=0,\dots,k-1$}
+\For{$i=1,\dots,b$}
 {
-$s\leftarrow{\textit{Random}(n)}$\;
+$s\leftarrow{\textit{Random}({\mathsf{N}})}$\;
 %$s\leftarrow{\textit{XORshift}(n)}$\;
-$x\leftarrow{F_f(s,x)}$\;
+$x\leftarrow{F_{f_u}(x,s)}$\;
 }
 return $x$\;
 %\end{scriptsize}
-\caption{Algorithme de gÃ©nÃ©ration de nombres pseudo alÃ©atoires 
-Ã  l'aide de la fonction chaotique $G_f$}
+\caption{PRNG basÃ© sur les itÃ©rations unaires.}
 \label{CI Algorithm}
 \end{algorithm}
 
+\subsection{Algorithme d'un gÃ©nÃ©rateur}
+On peut penser Ã  construire un gÃ©nÃ©rateur de nombres 
+pseudo-alÃ©atoires comme dans l'algorithme~\ref{CI Algorithm} donnÃ© ci-dessous.
+
 
 Celui-ci prend en entrÃ©e: une fonction $f$;
-un entier $b$, qui assure que le nombre d'itÃ©rations
-est compris entre $b+1 $ et  $2b+1$ et une configuration initiale $x^0$.
-Il retourne une nouvelle configuration $x$.
+un entier $b$, qui est le nombre d'itÃ©rations Ã  effectuer entre deux sorties 
+et une configuration initiale $x^0$.
+Il retourne une nouvelle configuration $x$ en appliquant 
+la fonction $F_{f_u}$ (Ã©quation~\ref{eq:iterations:unaires}
+vue au chapitre~\ref{chap:carachaos}) et correspondant 
+Ã  des itÃ©rations unaires.
 En interne, il exploite un algorithme de gÃ©nÃ©ration
-de nombres pseudo alÃ©atoires
-\textit{Random}$(l)$. 
-Cet algorithme est utilisÃ©e dans notre gÃ©nÃ©rateur pour construire la longueur 
-de la stratÃ©gie ainsi que les Ã©lÃ©ments qui la composent.
-Pratiquement, il retourne des entiers dans $\llbracket 1 ; l \rrbracket$ 
-selon une \gls{distributionuniforme} (cf. glossaire) et utilise 
-\textit{XORshift} qui est une classe de gÃ©nÃ©rateurs de
-nombres pseudo alÃ©atoires
-trÃ¨s rapides conÃ§us par George Marsaglia. 
-
-% L'algorithme \textit{XORshift} exploite itÃ©rativement
-% la fonction \og \gls{xor}\fg{} $\oplus$ (cf. glossaire) 
-% sur des nombres obtenus grÃ¢ce Ã  des \glspl{decalageDeBits} (cf. glossaire).
-
-L'algorithme \textit{XORshift} 
-exploite itÃ©rativement l'opÃ©rateur $\oplus$  
-sur des nombres obtenus grÃ¢ce Ã  des \glspl{decalageDeBits} (cf. glossaire).
-Cet opÃ©rateur, dÃ©fini dans $\Bool^{n}$, 
-applique la fonction \og  \gls{xor} \fg{} (cf. glossaire) 
-aux bits de mÃªme rang de ses deux opÃ©randes (\og opÃ©ration bit Ã  bit \fg{}).
-Une instance de cette classe est donnÃ©e dans l'algorithme~\ref{XORshift} donnÃ© 
-ci-dessous.
-
-\begin{algorithm}[h]
-%\SetLine
-\KwIn{la configuration interne $z$ (un mot de 32-bit)}
-\KwOut{$y$ (un mot de 32-bits)}
-$z\leftarrow{z\oplus{(z\ll13)}}$\;
-$z\leftarrow{z\oplus{(z\gg17)}}$\;
-$z\leftarrow{z\oplus{(z\ll5)}}$\;
-$y\leftarrow{z}$\;
-return $y$\;
-\medskip
-\caption{Une boucle de l'algorithme de \textit{XORshift}}
-\label{XORshift}
-\end{algorithm}
-
-
-
-Il reste Ã  instancier une fonction $f$ dans 
-l'algorithme~\ref{CI Algorithm} 
-en adÃ©quation avec  l'approche dÃ©veloppÃ©e 
-en section~\ref{sec:sccg}.
-La section suivante montre comment l'uniformitÃ© de la distribution a
-contraint cette instanciation.
+de nombres pseudo-alÃ©atoires donnÃ© en paramÃ¨tre.
+Cela peut Ãªtre n'importe quel PRNG (XORshift, Mersenne-Twister) dont la 
+sortie est uniformÃ©ment distribuÃ©e.
+Notre approche vise a donner des propriÃ©tÃ©s de chaos Ã  ce gÃ©nÃ©rateur embarquÃ©.
+
+
+% \textit{Random}$(l)$. 
+% Cet algorithme est utilisÃ©e dans notre gÃ©nÃ©rateur pour construire la longueur 
+% de la stratÃ©gie ainsi que les Ã©lÃ©ments qui la composent.
+% Pratiquement, il retourne des entiers dans $\llbracket 1 ; l \rrbracket$ 
+% selon une distribution uniforme et utilise 
+% \textit{XORshift} qui est une classe de gÃ©nÃ©rateurs de
+% nombres pseudo alÃ©atoires conÃ§us par George Marsaglia. 
+
+
+% L'algorithme \textit{XORshift} 
+% exploite itÃ©rativement l'opÃ©rateur $\oplus$  
+% sur des nombres obtenus grÃ¢ce Ã  des dÃ©calages de bits.
+% Cet opÃ©rateur, dÃ©fini dans $\Bool^{n}$, 
+% applique la fonction \og  xor \fg{} 
+% aux bits de mÃªme rang de ses deux opÃ©randes (\og opÃ©ration bit Ã  bit \fg{}).
+% Une instance de cette classe est donnÃ©e dans l'algorithme~\ref{XORshift} donnÃ© 
+% ci-dessous.
+
+% \begin{algorithm}[h]
+% %\SetLine
+% \KwIn{la configuration interne $z$ (un mot de 32-bit)}
+% \KwOut{$y$ (un mot de 32-bits)}
+% $z\leftarrow{z\oplus{(z\ll13)}}$\;
+% $z\leftarrow{z\oplus{(z\gg17)}}$\;
+% $z\leftarrow{z\oplus{(z\ll5)}}$\;
+% $y\leftarrow{z}$\;
+% return $y$\;
+% \medskip
+% \caption{Une boucle de l'algorithme de \textit{XORshift}}
+% \label{XORshift}
+% \end{algorithm}
+
+
+Nous avons vu au chapitre~\ref{chap:carachaos} que 
+$G_{f_u}$ est chaotique dans l'espace $\mathcal{X}_u$ 
+si et seulement si le graphe d'itÃ©rations $\textsc{giu}(f)$ 
+est fortement connexe.
+Pour $b=1$, l'algorithme itÃ¨re la fonction $F_{f_u}$.
+
+Pour simuler au mieux l'alÃ©a, un bon gÃ©nÃ©rateur de nombres pseudo-alÃ©atoires
+se doit de fournir  des nombres selon une distribution uniforme.
+Regardons comment l'uniformitÃ© de la distribution 
+contraint la fonction $f$ Ã  itÃ©rer.
 
 \subsection{Un gÃ©nÃ©rateur Ã  sortie uniformÃ©ment distribuÃ©e}\label{sub:prng:unif}
 
@@ -189,57 +183,123 @@ Enfin, une matrice stochastique de taille $n \times n$ est rÃ©guliÃ¨re
 si  la propriÃ©tÃ© suivante est Ã©tablie:
 $$\exists k \in \mathds{N}^\ast, \forall i,j \in \llbracket 1; n \rrbracket, M_{ij}^k>0.$$
 
-On Ã©nonce enfin le thÃ©orÃ¨me suivant liant les 
-\glspl{vecteurDeProbabilite} (cf. glossaire) 
-et les \glspl{chaineDeMarkov} (cf. glossaire):
+On Ã©nonce le thÃ©orÃ¨me classique suivant liant les 
+vecteurs de probabilitÃ©s 
+et les chaÃ®nes de Markov.
 
 
  
-\begin{Theo}\label{th}
+
+\begin{theorem}\label{th}
   Si $M$ est une matrice stochastique rÃ©guliÃ¨re, alors $M$ 
   possÃ¨de un unique vecteur stationnaire de probabilitÃ©s  $\pi$
   ($\pi.M = \pi$).
-  De plus, si $\pi^0$ est un \gls{vecteurDeProbabilite} 
+  De plus, si $\pi^0$ est un {vecteur de probabilitÃ©s} 
  et si on dÃ©finit 
   la suite $(\pi^{k})^{k \in  \Nats}$ par 
   $\pi^{k+1} = \pi^k.M $ pour $k = 0, 1,\dots$ 
-  alors la \gls{chaineDeMarkov} $\pi^k$
+  alors la {chaÃ®ne de Markov} $\pi^k$
   converge vers $\pi$ lorsque $k$ tend vers l'infini.
-\end{Theo}
+\end{theorem}
 
 
 Montrons sur un exemple jouet Ã  deux Ã©lÃ©ments 
 que ce thÃ©orÃ¨me permet de vÃ©rifier si la sortie d'un gÃ©nÃ©rateur de 
-nombres pseudo alÃ©atoires est uniformÃ©ment distribuÃ©e ou non.
-Soit alors $g$ et $h$ deux fonctions  de $\Bool^2$
+nombres pseudo-alÃ©atoires est uniformÃ©ment distribuÃ©e ou non.
+Soient alors $g$ et $h$ deux fonctions  de $\Bool^2$
 dÃ©finies par $g(x_1,x_2)=(\overline{x_1},x_1.\overline{x_2}) $
 et $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$.
 Leurs graphes d'interactions donnÃ©s en figure \ref{fig:g:inter} et \ref{fig:h:inter}
 vÃ©rifient les hypothÃ¨ses du thÃ©orÃ¨me~\ref{th:Adrien}. 
 Leurs graphes d'itÃ©rations
-sont donc fortement connexes, ce que l'on a pu dÃ©jÃ  vÃ©rifier aux figures
-\ref{fig:g:iter} et \ref{fig:h:iter}.
+sont donc fortement connexes, ce que l'on peut vÃ©rifier aux figures~\ref{fig:g:iter} 
+et~\ref{fig:h:iter}.
 \textit{A priori}, ces deux fonctions pourraient Ãªtre intÃ©grÃ©es
-dans un gÃ©nÃ©rateur de nombres pseudo alÃ©atoires. Montrons que ce n'est pas le cas pour $g$ et 
+dans un gÃ©nÃ©rateur de nombres pseudo-alÃ©atoires. Montrons que ce n'est pas le cas pour $g$ et 
 que cela l'est pour $h$.
 
 
+
+
+
+
+
+
+
+\begin{figure}%[t]
+  \begin{center}
+    \subfigure[$g(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}) $]{
+      \begin{minipage}{0.40\textwidth}
+        \begin{center}
+          \includegraphics[height=4cm]{images/g.pdf}
+        \end{center}
+      \end{minipage}
+      \label{fig:g:iter}
+    }
+    \subfigure[$h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$]{
+      \begin{minipage}{0.40\textwidth}
+        \begin{center}
+          \includegraphics[height=4cm]{images/h.pdf}
+        \end{center}
+      \end{minipage}
+      \label{fig:h:iter}
+    }    \end{center}
+    \caption{Graphes des itÃ©rations unaires 
+      de fonctions boolÃ©ennes dans $\Bool^2$}
+    \label{fig:xplgraphIter}
+  \end{figure}
+
+
+
+
+
+
+
+
+
+\begin{figure}%[t]
+  \begin{center}
+    \subfigure[$g(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}) $]{
+      \begin{minipage}{0.40\textwidth}
+        \begin{center}
+          \includegraphics[height=3cm]{images/gp.pdf}
+        \end{center}
+      \end{minipage}
+      \label{fig:g:inter}
+    }
+    \subfigure[$h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$]{
+      \begin{minipage}{0.40\textwidth}
+        \begin{center}
+          \includegraphics[height=3cm]{images/hp.pdf}
+        \end{center}
+      \end{minipage}
+      \label{fig:h:inter}
+    }    \end{center}
+    \caption{Graphes d'interactions de fonctions boolÃ©ennes dans $\Bool^2$}
+    \label{fig:xplgraphInter}
+  \end{figure}
+
+
+
+
+
+
 Comme le gÃ©nÃ©rateur \textit{Random} possÃ¨de une sortie uniformÃ©ment 
 distribuÃ©e,  la  stratÃ©gie est uniforme sur $\llbracket 1, 2 \rrbracket$,
 et donc, 
-pour tout sommet de $\Gamma(g)$ et de  $\Gamma(h)$,
+pour tout sommet de $\textsc{giu}(g)$ et de  $\textsc{giu}(h)$,
 chaque arc sortant de ce sommet a, parmi l'ensemble des arcs sortant 
 de ce sommet, une probabilitÃ© $1/2$ dâÃªtre celui qui sera traversÃ©.
-En d'autres mots, $\Gamma(g)$ est le graphe orientÃ© d'une chaÃ®ne de Markov.
-Il est facile de vÃ©rifier que la \gls{matriceDeTransitions} (cf. glossaire)
+En d'autres mots, $\textsc{giu}(g)$ est le graphe orientÃ© d'une chaÃ®ne de Markov.
+Il est facile de vÃ©rifier que la matrice de transitions
 d'un tel processus 
 est $M_g   = \frac{1}{2} \check{M}_g$, 
-oÃ¹ $\check{M}_g$ est la \gls{matriceDAdjacence} (cf. glossaire) donnÃ©e en 
-figure~\ref{fig:g:incidence} (voir ci-aprÃ¨s), et similairement pour $M_h$. 
+oÃ¹ $\check{M}_g$ est la matrice d' adjacence  donnÃ©e en 
+figure~\ref{fig:g:incidence} (voir ci-aprÃ¨s), et  de maniÃ¨re similaire pour $M_h$. 
 
 \begin{figure}[h]
   \begin{center}
-    \subfloat[$\check{M}_g $.]{
+    \subfigure[$\check{M}_g $.]{
       \begin{minipage}{0.25\textwidth}
         \begin{center}
           % \vspace{-3cm}
@@ -256,7 +316,7 @@ figure~\ref{fig:g:incidence} (voir ci-aprÃ¨s), et similairement pour $M_h$.
       \end{minipage}
       \label{fig:g:incidence}
     }
-    \subfloat[$\check{M}_h $.]{
+    \subfigure[$\check{M}_h $.]{
         \begin{minipage}{0.25\textwidth}
           \begin{center}
             $\left( 
@@ -289,10 +349,10 @@ Alors d'aprÃ¨s le thÃ©orÃ¨me~\ref{th},
 pour n'importe quel vecteur initial de probabilitÃ©s $\pi^0$, on a 
 $\lim_{k \to \infty} \pi^0 M^k_g = \pi_g$ et 
 $\lim_{k \to \infty} \pi^0 M^k_h = \pi_h$. 
-Ainsi la chaÃ®ne de Markov associÃ© Ã  $h$ tend vers une 
+Ainsi la chaÃ®ne de Markov associÃ©e Ã  $h$ tend vers une 
 distribution uniforme, contrairement Ã  celle associÃ©e Ã  $g$.
 On en dÃ©duit que $g$ ne devrait pas Ãªtre itÃ©rÃ©e dans 
-un gÃ©nÃ©rateur de nombres pseudo alÃ©atoires.
+un gÃ©nÃ©rateur de nombres pseudo-alÃ©atoires.
 Au contraire, 
 $h$ devrait pouvoir Ãªtre embarquÃ©e dans l'algorithme~\ref{CI Algorithm}, 
 pour peu que le nombre $b$ d'itÃ©rations entre deux mesures successives 
@@ -300,73 +360,30 @@ de valeurs  soit suffisamment grand de sorte que
 le vecteur dâÃ©tat de la chaÃ®ne de Markov
 ait une distribution suffisamment proche de la distribution uniforme.
 
+On Ã©nonce directement le thÃ©orÃ¨me suivant dont la preuve est donnÃ©e en annexe~\ref{anx:generateur}.
 
-ConsidÃ©rons le lemme technique suivant:
-\begin{Lemma}\label{lem:stoc}
-Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\Gamma(f)$ son graphe d'itÃ©rations, $\check{M}$ la matrice d'adjacence de $\Gamma(f)$, et  $M$  la matrice 
-$2^n\times 2^n$  dÃ©finie par
-$M = \frac{1}{n}\check{M}$.
-Alors $M$ est une matrice stochastique rÃ©guliÃ¨re si et seulement si
-$\Gamma(f)$ est fortement connexe.
-\end{Lemma}
-
-\begin{Proof}  
-On remarque tout d'abord que $M$ 
-est une matrice stochastique par construction.
-Supposons $M$ rÃ©guliÃ¨re. 
-Il existe donc  $k$ tel que $M_{ij}^k>0$ pour chaque $i,j\in \llbracket
-1;  2^n  \rrbracket$. L'inÃ©galitÃ©  $\check{M}_{ij}^k>0$  est alors Ã©tablie.
-Puisque $\check{M}_{ij}^k$ est le nombre de chemins de  $i$ Ã  $j$ de longueur $k$
-dans $\Gamma(f)$ et puisque ce nombre est positif, alors 
-$\Gamma(f)$ est fortement connexe.
-
-RÃ©ciproquement si $\Gamma(f)$ 
-est fortement connexe, alors pour tous les sommets $i$ et $j$, un chemin peut Ãªtre construit pour atteindre  $j$  depuis $i$ en au plus $2^n$ Ã©tapes.
-Il existe donc 
-$k_{ij} \in \llbracket 1,  2^n \rrbracket$ tels que $\check{M}_{ij}^{k_{ij}}>0$.  
-Comme tous les  multiples $l \times k_{ij}$ de $k_{ij}$ sont tels que 
-$\check{M}_{ij}^{l\times  k_{ij}}>0$, 
-on peut conclure que, si 
-$k$ est le plus petit multiple commun de $\{k_{ij}  \big/ i,j  \in \llbracket 1,  2^n \rrbracket  \}$ alors
-$\forall i,j  \in \llbracket  1, 2^n \rrbracket,  \check{M}_{ij}^{k}>0$. 
-Ainsi, $\check{M}$ et donc $M$ sont rÃ©guliÃ¨res.
-\end{Proof}
-
-Ces rÃ©sultats permettent formuler et de prouver le thÃ©orÃ¨me suivant:
-
-\begin{Theo}
-  Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\Gamma(f)$ son 
+\begin{restatable}[UniformitÃ© de la sortie de l'algorithme~\ref{CI Algorithm}]{theorem}{PrngCIUniforme}\label{thm:prng:u}
+  Soit $f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$, $\textsc{giu}(f)$ son 
   graphe d'itÃ©rations , $\check{M}$ sa matrice d'adjacence
-  et $M$ une matrice  $2^n\times 2^n$  dÃ©finie comme dans le lemme prÃ©cÃ©dent.
-  Si $\Gamma(f)$ est fortement connexe, alors 
-  la sortie du gÃ©nÃ©rateur de nombres pseudo alÃ©atoires dÃ©taillÃ© par 
+  et $M$ une matrice  $2^n\times 2^n$  
+  dÃ©finie par 
+  $M = \dfrac{1}{\mathsf{N}} \check{M}$.
+  Si $\textsc{giu}(f)$ est fortement connexe, alors 
+  la sortie du gÃ©nÃ©rateur de nombres pseudo-alÃ©atoires dÃ©taillÃ© par 
   l'algorithme~\ref{CI Algorithm} suit une loi qui 
   tend vers la distribution uniforme si 
   et seulement si  $M$ est une matrice doublement stochastique.
-\end{Theo}
-\begin{Proof}
-  $M$ est une matrice stochastique rÃ©guliÃ¨re (Lemme~\ref{lem:stoc}) 
-  qui a un unique vecteur de probabilitÃ©s stationnaire
-  (ThÃ©orÃ¨me \ref{th}).
-  Soit $\pi$  dÃ©fini par 
-  $\pi = \left(\frac{1}{2^n}, \hdots, \frac{1}{2^n} \right)$.
-  On a  $\pi M = \pi$ si et seulement si
-  la somme des valeurs de chaque colonne de $M$  est 1, 
-  \textit{i.e.} si et seulement si 
-  $M$ est  doublement  stochastique.
-\end{Proof}
-
-
-\subsection{ExpÃ©rimentations}
-
-On considÃ¨re le graphe d'interactions $G(f)$ donnÃ© en figure~\ref{fig:G}. 
-Il vÃ©rifie le thÃ©orÃ¨me~\ref{th:Adrien}: 
-toutes les fonctions $f$ possÃ©dant un tel graphe d'interactions
-ont un graphe d'itÃ©rations  $\Gamma(f)$ fortement connexe.
-Pratiquement, un algorithme simple de satisfaction de contraintes
-a trouvÃ©  520 fonctions $f$ non isomorphes de graphe d'interactions  $G(f)$, 
-dont seulement 16 d'entre elles possÃ©dent une matrice doublement stochastique.
+\end{restatable}
+
 
+\subsection{Quelques exemples}
+
+On considÃ¨re le graphe d'interactions $\Gamma(f)$ donnÃ©
+en figure~\ref{fig:G}. C'est le mÃªme qui a Ã©tÃ© prÃ©sentÃ©
+Ã  la section~\ref{sec:11FCT}.
+On a vu qu'il y avait  520 fonctions $f$ non isomorphes de graphe d'interactions  $\Gamma(f)$. 
+
+Seulement 16 d'entre elles possÃ¨dent une matrice doublement stochastique.
 La figure~\ref{fig:listfonction} explicite ces 16 fonctions en 
 dÃ©finissant les images des Ã©lÃ©ments de la liste
 0, 1, 2,\ldots, 14, 15 en respectant  l'ordre.
@@ -374,31 +391,37 @@ Expliquons enfin comment a Ã©tÃ© calculÃ© le nombre de la troisiÃ¨me
 colonne utilisÃ© comme le paramÃ¨tre $b$ 
 dans l'algorithme~\ref{CI Algorithm}.
 
-Soit $e_i$ le $i^{\textrm{Ã¨me}}$ vecteur la base canonique de $\R^{2^{n}}$. 
-Chacun des Ã©lÃ©ments $v_j$, $1 \le j \le 2^n$, 
+Soit $e_i$ le $i^{\textrm{Ã¨me}}$ vecteur de la base canonique de $\R^{2^{\mathsf{N}}}$. 
+Chacun des Ã©lÃ©ments $v_j$, $1 \le j \le 2^{\mathsf{N}}$, 
 du vecteur $e_i M_f^t$ reprÃ©sente la probabilitÃ© 
 d'Ãªtre dans la configuration $j$ aprÃ¨s $t$ Ã©tapes du processus de Markov 
-associÃ© Ã  $\Gamma(f)$ en partant de la configuration $i$.   
+associÃ© Ã  $\textsc{giu}(f)$ en partant de la configuration $i$.   
 Le nombre $\min \{
  t \mid t \in \Nats, \vectornorm{e_i M_f^t - \pi} < 10^{-4}
 \}$ reprÃ©sente le plus petit nombre d'itÃ©rations oÃ¹ la distance de 
-ce vecteur au vecteur $\pi=(\frac{1}{2^n},\ldots,\frac{1}{2^n})$
+ce vecteur au vecteur $\pi=(\frac{1}{2^{\mathsf{N}}},\ldots,\frac{1}{2^{\mathsf{N}}})$
 -- autrement dit, oÃ¹ la dÃ©viation par rapport Ã  la distribution uniforme --
  est infÃ©rieure 
 Ã  $10^{-4}$. En prenant le max pour tous les $e_i$, on obtient une valeur pour
- $b$. Ainsi, on a 
-$$
-b = \max\limits_{i \in \llbracket 1, 2^n \rrbracket} 
-\{
-\min \{
+ $b$. 
+Ainsi, on a 
+\begin{equation}
+b = \max\limits_{i \in \llbracket 1, 2^{\mathsf{N}} \rrbracket} 
+\left\{
+\min \left\{
  t \mid t \in \Nats, \vectornorm{e_i M_f^t - \pi} < 10^{-4}
-\}
-\}. 
-$$
+\right\}
+\right\}. 
+\label{eq:mt:ex}
+\end{equation}
+
+\noindent Par la suite, ce nombre sera appelÃ© \emph{temps de mÃ©lange}.
+
+
 
 \begin{figure}%[h]
   \begin{center}
-  \subfloat[Graphe d'interactions]{
+  \subfigure[Graphe d'interactions]{
     \begin{minipage}{0.20\textwidth}
       \begin{center}
         \includegraphics[width=3.5cm]{images/Gi.pdf}
@@ -406,7 +429,7 @@ $$
     \end{minipage}
     \label{fig:G}
   }\hfill
-  \subfloat[Fonctions doublement stochastiques]{
+  \subfigure[Fonctions doublement stochastiques]{
     \begin{minipage}{0.75\textwidth}
       \begin{scriptsize}
         \begin{center}
@@ -474,60 +497,341 @@ $\mathcal{F}_{16}$ &14, 15, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
 
 La qualitÃ© des sÃ©quences alÃ©atoires a Ã©tÃ© Ã©valuÃ©e Ã  travers la suite 
 de tests statistiques dÃ©veloppÃ©e pour les gÃ©nÃ©rateurs de nombres 
-pseudo alÃ©atoires par le 
+pseudo-alÃ©atoires par le 
 \emph{National Institute of Standards and Technology} (NIST).
-% Pour les 15 tests, le seuil $\alpha$ est fixÃ© Ã  $1\%$:
-% une  valeur  
-% qui est plus grande que $1\%$  signifie 
-% que la chaÃ®ne est considÃ©rÃ©e comme alÃ©atoire avec une confiance de $99\%$.
-% Le tableau~\ref{fig:TEST} donne une vision synthÃ©tique de toutes 
-% les expÃ©rimentations. 
 L'expÃ©rience a montrÃ© notamment que toutes ces fonctions
 passent avec succÃ¨s cette batterie de tests.
 
+Pour conclure cette section, on remarque que le gÃ©nÃ©rateur de nombres pseudo-alÃ©atoires 
+a Ã©tÃ© prouvÃ© chaotique pour $b=1$, \textit{i.e.}, lorsqu'il y a une sortie pour chaque itÃ©ration.
+Ceci est difficilement compatible avec la volontÃ© d'avoir une sortie uniformÃ©ment distribuÃ©e: 
+se rapprocher de cette distribution nÃ©cessite en effet un nombre plus Ã©levÃ©
+d'itÃ©rations $b$ entre chaque sortie. Par exemple, dans l'exemple prÃ©cÃ©dent, il est nÃ©cessaire 
+d'itÃ©rer au moins 42 fois entre chaque sortie pour suivre une loi uniforme Ã  $10^{-4}$ prÃ¨s.
+Montrer que les sous-sÃ©quences de suites chaotiques ainsi gÃ©nÃ©rÃ©es  demeurent chaotiques
+est l'objectif de la section suivante.
 
 
+\section{Un PRNG basÃ© sur des itÃ©rations unaires qui est chaotique }\label{prng:unaire:chaos}
 
-% \begin{table}[th]
-% \begin{scriptsize}
-% \begin{tabular}{|*{17}{c|}}
-% \hline
-% {PropriÃ©tÃ©}& $\mathcal{F}_{1}$ &$\mathcal{F}_{2}$ &$\mathcal{F}_{3}$ &$\mathcal{F}_{4}$ &$\mathcal{F}_{5}$ &$\mathcal{F}_{6}$ &$\mathcal{F}_{7}$ &$\mathcal{F}_{8}$ &$\mathcal{F}_{9}$ &$\mathcal{F}_{10}$ &$\mathcal{F}_{11}$ &$\mathcal{F}_{12}$ &$\mathcal{F}_{13}$ &$\mathcal{F}_{14}$ &$\mathcal{F}_{15}$ &$\mathcal{F}_{16}$ \\
-% \hline
-% FrÃ©quence &77.9 &15.4 &83.4 &59.6 &16.3 &38.4 &20.2 &29.0 &77.9 &21.3 &65.8 &85.1 &51.4 &35.0 &77.9 &92.4 \\ 
-%  \hline 
-% FrÃ©quence / bloc &88.3 &36.7 &43.7 &81.7 &79.8 &5.9 &19.2 &2.7 &98.8 &1.0 &21.3 &63.7 &1.4 &7.6 &99.1 &33.5 \\ 
-%  \hline 
-% Somme cummulÃ©e &76.4 &86.6 &8.7 &66.7 &2.2 &52.6 &20.8 &80.4 &9.8 &54.0 &73.6 &80.1 &60.7 &79.7 &76.0 &44.7 \\ 
-%  \hline 
-% ExÃ©cution &5.2 &41.9 &59.6 &89.8 &23.7 &76.0 &77.9 &79.8 &45.6 &59.6 &89.8 &2.4 &96.4 &10.9 &72.0 &11.5 \\ 
-%  \hline 
-% Longue exÃ©cution &21.3 &93.6 &69.9 &23.7 &33.5 &30.4 &41.9 &43.7 &30.4 &17.2 &41.9 &51.4 &59.6 &65.8 &11.5 &61.6 \\ 
-%  \hline 
-% Rang &1.0 &41.9 &35.0 &45.6 &51.4 &20.2 &31.9 &83.4 &89.8 &38.4 &61.6 &4.0 &21.3 &69.9 &47.5 &95.6 \\ 
-%  \hline 
-% Fourrier Rapide &40.1 &92.4 &97.8 &86.8 &43.7 &38.4 &76.0 &57.5 &36.7 &35.0 &55.4 &57.5 &86.8 &76.0 &31.9 &7.6 \\ 
-%  \hline 
-% Sans superposition &49.0 &45.7 &50.5 &51.0 &48.8 &51.2 &51.6 &50.9 &50.9 &48.8 &45.5 &47.3 &47.0 &49.2 &48.6 &46.4 \\ 
-%  \hline 
-% Avec Superposition &27.6 &10.9 &53.4 &61.6 &16.3 &2.7 &59.6 &94.6 &88.3 &55.4 &76.0 &23.7 &47.5 &91.1 &65.8 &81.7 \\ 
-%  \hline 
-% Universelle &24.9 &35.0 &72.0 &51.4 &20.2 &74.0 &40.1 &23.7 &9.1 &72.0 &4.9 &13.7 &14.5 &1.8 &93.6 &65.8 \\ 
-%  \hline 
-% Entropie approchÃ©e &33.5 &57.5 &65.8 &53.4 &26.2 &98.3 &53.4 &63.7 &38.4 &6.7 &53.4 &19.2 &20.2 &27.6 &67.9 &88.3 \\ 
-%  \hline 
-% Suite alÃ©atoire &29.8 &35.7 &40.9 &36.3 &54.8 &50.8 &43.5 &46.0 &39.1 &40.8 &29.6 &42.0 &34.8 &33.8 &63.0 &46.3 \\ 
-%  \hline 
-% Suite alÃ©atoire variante &32.2 &40.2 &23.0 &39.6 &47.5 &37.2 &56.9 &54.6 &53.3 &31.5 &23.0 &38.1 &52.3 &57.1 &47.7 &40.8 \\ 
-%  \hline 
-% SÃ©rie &56.9 &58.5 &70.4 &73.2 &31.3 &45.9 &60.8 &39.9 &57.7 &21.2 &6.4 &15.6 &44.7 &31.4 &71.7 &49.1 \\ 
-%  \hline 
-% ComplexitÃ© linÃ©aire &24.9 &23.7 &96.4 &61.6 &83.4 &49.4 &49.4 &18.2 &3.5 &76.0 &24.9 &97.2 &38.4 &38.4 &1.1 &8.6 \\ 
-%  \hline
-% \end{tabular}
-% \end{scriptsize}
-% \caption{Test de NIST rÃ©alisÃ© sur des instances de gÃ©nÃ©rateurs}\label{fig:TEST}  
-% \end{table}
+Cette section prÃ©sente un espace mÃ©trique adaptÃ© au gÃ©nÃ©rateur de nombres pseudo-alÃ©atoires 
+prÃ©sentÃ© Ã  l'algorithme~\ref{CI Algorithm} et prouve ensuite que la fonction qu'il reprÃ©sente 
+est chaotique sur cet espace.
 
+\subsection{Un espace  $\mathcal{X}_{\mathsf{N},\mathcal{P}}$    pour le PRNG de l'algorithme~\ref{CI Algorithm}}
 
 
+
+Introduisons tout d'abord $\mathcal{P} \subset \mathds{N}$ un ensemble fini non vide de cardinalitÃ© 
+$\mathsf{p} \in \mathds{N}^\ast$.
+Intuitivement, c'est le nombre d'itÃ©rations qu'il est autorisÃ© de faire.
+On ordonne les $\mathsf{p}$ Ã©lÃ©ments de $\mathcal{P}$ comme suit: 
+$\mathcal{P} = \{ p_1, p_2, \hdots, p_\mathsf{p}\}$
+et $p_1< p_2< \hdots < p_\mathsf{p}$.
+
+Dans l'algorithme~\ref{CI Algorithm}, 
+$\mathsf{p}$ vaut 1 et  $p_1=b$. 
+Cet  algorithme peut Ãªtre vu comme $b$ compostions de la fonction $F_{f_u}$.
+Ceci peut cependant se gÃ©nÃ©raliser Ã  $p_i$, $p_i \in \mathcal{P}$,
+compositions fonctionnelles de $F_{f_u}$.
+Ainsi, pour chaque $p_i \in \mathcal{P}$, on construit la fonction
+$F_{{f_u},p_i} :  \mathds{B}^\mathsf{N} \times [\mathsf{N}]^{p_i}
+\rightarrow \mathds{B}^\mathsf{N}$ dÃ©finie par
+
+$$
+F_{f_u,p_i} (x,(u^0, u^1, \hdots, u^{p_i-1}))  = 
+F_{f_u}(\hdots (F_{f_u}(F_{f_u}(x,u^0), u^1), \hdots), u^{p_i-1}).
+$$
+
+
+On construit l'espace 
+ $\mathcal{X}_{\mathsf{N},\mathcal{P}}=  \mathds{B}^\mathsf{N} \times \mathds{S}_{\mathsf{N},\mathcal{P}}$, oÃ¹
+$\mathds{S}_{\mathsf{N},\mathcal{P}}=
+[\mathsf{N}]^{\Nats}\times 
+\mathcal{P}^{\Nats}$. 
+Chaque Ã©lÃ©ment de l'espace est une paire oÃ¹ le premier Ã©lÃ©ment est 
+un $\mathsf{N}$-uplet de  $\Bool^{\mathsf{N}}$ (comme dans $\mathcal{X}_u$).
+Le second Ã©lÃ©ment est une paire $((u^k)_{k \in \Nats},(v^k)_{k \in \Nats})$ de suites infinies.
+La suite $(v^k)_{k \in \Nats}$ dÃ©finit combien d'itÃ©rations sont exÃ©cutÃ©es au temps $k$ entre deux sorties.
+La sÃ©quence $(u^k)_{k \in \Nats}$ dÃ©finit quel Ã©lÃ©ment est modifiÃ© (toujours au temps $k$).
+
+DÃ©finissons la fonction de dÃ©calage  $\Sigma$ pour chaque  Ã©lÃ©ment de $\mathds{S}_{\mathsf{N},\mathcal{P}}$.
+$$\begin{array}{cccc}
+\Sigma:&\mathds{S}_{\mathsf{N},\mathcal{P}} &\longrightarrow
+&\mathds{S}_{\mathsf{N},\mathcal{P}} \\
+& \left((u^k)_{k \in \mathds{N}},(v^k)_{k \in \mathds{N}}\right) & \longmapsto & \left(\sigma^{v^0}\left((u^k)_{k \in \mathds{N}}\right),\sigma\left((v^k)_{k \in \mathds{N}}\right)\right). 
+\end{array}
+$$
+En d'autres termes, $\Sigma$ reÃ§oit deux suites $u$ et $v$ et 
+effectue $v^0$ dÃ©calage vers la droite sur la premiÃ¨re et un dÃ©calage vers la droite 
+sur la seconde.
+
+
+Ainsi, les  sorties  $(y^0, y^1, \hdots )$ produites par le gÃ©nÃ©rateur dÃ©taillÃ© dans 
+l'algorithme~\ref{CI Algorithm}
+sont les premiers  composants des itÃ©rations $X^0 = (x^0, (u,v))$ et $\forall n \in \mathds{N}, 
+X^{n+1} = G_{f_u,\mathcal{P}}(X^{\mathsf{N}})$ dans $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ oÃ¹
+$G_{f_u,\mathcal{P}}$  est dÃ©finie par:
+
+
+
+
+\begin{equation}
+\begin{array}{cccc}
+G_{f_u,\mathcal{P}} :&  \mathcal{X}_{\mathsf{N},\mathcal{P}} & \longrightarrow & \mathcal{X}_{\mathsf{N},\mathcal{P}}\\
+   & (e,(u,v)) & \longmapsto & \left( F_{f,v^0}\left( e, (u^0, \hdots, u^{v^0-1}\right), \Sigma (u,v) \right) .
+\end{array}
+\end{equation}
+
+
+
+\subsection{Une distance sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$}
+
+On dÃ©finit la fonction  $d$ sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ comme suit:
+Soit  $x=(e,s)$ et $\check{x}=(\check{e},\check{s})$ dans 
+$\mathcal{X}_{\mathsf{N},\mathcal{P}} = \mathds{B}^\mathsf{N} \times \mathds{S}_{\mathsf{N},\mathcal{P}} $,
+oÃ¹ $s=(u,v)$ et $\check{s}=(\check{u},\check{v})$ sont dans $ \mathds{S}_{\mathsf{N},\mathcal{P}} = 
+\mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket} \times \mathcal{S}_\mathcal{P}$. 
+\begin{enumerate}
+\item $e$ et $\check{e}$ sont des entiers appartenant Ã  $\llbracket 0, 2^{\mathsf{N}-1} \rrbracket$. 
+La distance de Hamming $d_{\mathds{B}^\mathsf{N}}$ entre les 
+dÃ©compositions binaires de $e$ et de $\check{e}$ (\textit{i.e.}, le 
+le nombre de bits qu'elles ont de diffÃ©rent) constitue 
+la partie entiÃ¨re de $d(X,\check{X})$.
+\item la partie dÃ©cimale est construite Ã  partir des diffÃ©rences entre 
+$v^0$ et $\check{v}^0$, suivie des diffÃ©rences entre les sÃ©quences finies
+$u^0, u^1, \hdots, u^{v^0-1}$ et  $\check{u}^0, \check{u}^1, \hdots, \check{u}^{\check{v}^0-1}$, suivie par les diffÃ©rences entre  $v^1$ et $\check{v}^1$, 
+suivie par les diffÃ©rences entre $u^{v^0}, u^{v^0+1}, \hdots, u^{v^1-1}$ et
+$\check{u}^{\check{v}^0}, \check{u}^{\check{v}^0+1}, \hdots, \check{u}^{\check{v}^1-1}$, etc.
+
+Plus prÃ©cisÃ©ment, soit 
+$p = \lfloor \log_{10}{(\max{\mathcal{P}})}\rfloor +1$ et 
+$n = \lfloor \log_{10}{(\mathsf{N})}\rfloor +1$.
+\begin{enumerate}
+\item Les $p$ premiers Ã©lÃ©ments de $d(x,\check{x})$ sont $|v^0-\check{v}^0|$ 
+  Ã©crits en base 10 et sur $p$ indices;
+\item les $n\times \max{(\mathcal{P})}$ Ã©lÃ©ments suivants servent 
+  Ã  Ã©valuer de combien $u^0, u^1, \hdots, u^{v^0-1}$ diffÃ¨re de 
+  $\check{u}^0, \check{u}^1, \hdots, \check{u}^{\check{v}^0-1}$. 
+  Les $n$ premiers Ã©lÃ©ments sont $|u^0-\check{u}^0|$. Il sont suivis de 
+$|u^1-\check{u}^1|$ Ã©crits Ã  l'aide de $n$ Ã©lÃ©ments, etc.
+\begin{enumerate}
+\item Si
+$v^0=\check{v}^0$,
+alors le processus se continue jusqu'Ã  $|u^{v^0-1}-\check{u}^{\check{v}^0-1}|$ et la 
+partie dÃ©cimale de $d(X,\check{X})$ est complÃ©tÃ©e par des 0
+jusqu'Ã  atteindre 
+$p+n\times \max{(\mathcal{P})}$ Ã©lÃ©ments.
+\item Si $v^0<\check{v}^0$, alors les $ \max{(\mathcal{P})}$  blocs de $n$
+Ã©lÃ©ments sont $|u^0-\check{u}^0|$, ..., $|u^{v^0-1}-\check{u}^{v^0-1}|$,
+$\check{u}^{v^0}$ (sur $n$ Ã©lÃ©ments), ..., $\check{u}^{\check{v}^0-1}$ (sur $n$ Ã©lÃ©ments), suivis par des 0, si besoin.
+\item Le cas $v^0>\check{v}^0$ est similaire, et donc omis
+\end{enumerate}
+\item Les $p$ suivants sont $|v^1-\check{v}^1|$, etc.
+\end{enumerate}
+\end{enumerate}
+
+
+La fonction $d$ peut se formaliser comme suit:
+$$d(x,\check{x})=d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})+d_{\mathds{B}^\mathsf{N}}(e,\check{e}),$$
+oÃ¹: % $p=\max \mathcal{P}$ and:
+\begin{itemize}
+\item $d_{\mathds{B}^\mathsf{N}}$ est la distance de Hamming,
+\item $\forall s=(u,v), \check{s}=(\check{u},\check{v}) \in \mathcal{S}_{\mathsf{N},\mathcal{P}}$,\newline 
+$$\begin{array}{rcl}
+ d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) &= &
+   \sum_{k=0}^\infty \dfrac{1}{10^{(k+1)p+kn\max{(\mathcal{P})}}} 
+   \bigg(|v^k - \check{v}^k|  \\
+   & & + \left| \sum_{l=0}^{v^k-1} 
+       \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{(l+1)n}} -
+       \sum_{l=0}^{\check{v}^k-1} 
+       \dfrac{\check{u}^{\sum_{m=0}^{k-1} \check{v}^m +l}}{ 10^{(l+1)n}} \right| \bigg)
+\end{array}
+$$ %\left| \sum_{l=0}^{v^k-1} \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{l}} - \sum_{l=0}^{\check{v}^k-1} \dfrac{\check{u}^{\sum_{m=0}^{k-1} \check{v}^m +l}}{ 10^{l}}\right|\right)}.$$
+\end{itemize}
+
+
+
+\begin{xpl}
+On considÃ¨re par exemple 
+$\mathsf{N}=13$, $\mathcal{P}=\{1,2,11\}$ ($\mathsf{p}$ vaut ainsi $3$), 
+et 
+$s=\left\{
+\begin{array}{l}
+u=\underline{6,} ~ \underline{11,5}, ...\\
+v=1,2,...
+\end{array}
+\right.$
+avec 
+$\check{s}=\left\{
+\begin{array}{l}
+\check{u}=\underline{6,4} ~ \underline{1}, ...\\
+\check{v}=2,1,...
+\end{array}
+\right.$.
+Ainsi 
+\[
+d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 
+0.01~0004000000000000000000~01~1005 \dots\]
+En effet, les $p=2$ premiers Ã©lÃ©ments sont  01, c'est-Ã -dire 
+$|v^0-\check{v}^0|=1$, 
+et on utilise $p$ Ã©lÃ©ments pour reprÃ©senter cette diffÃ©rence
+(Comme $\mathcal{P}=\{1,2,11\}$, cette diffÃ©rence peut valoir 10).
+On prend alors le $v^0=1$ premier terme de $u$, 
+chaque terme Ã©tant codÃ© sur $n=2$ Ã©lÃ©ments, soit 06.
+Comme on itÃ¨re au plus $\max{(\mathcal{P})}$ fois, 
+on complÃ¨te cette valeur par des 0 de sorte que 
+la chaÃ®ne obtenue ait $n\times \max{(\mathcal{P})}=22$ Ã©lÃ©ments, soit:
+0600000000000000000000. 
+De maniÃ¨re similaire, les $\check{v}^0=2$ premiers
+termes de $\check{u}$ sont reprÃ©sentÃ©s par 
+0604000000000000000000.
+La valeur absolue de leur diffÃ©rence est Ã©gale Ã  
+0004000000000000000000.
+Ces Ã©lÃ©ments sont concatÃ©nÃ©s avec 01. On peut construire alors le reste de 
+la sÃ©quence.
+\end{xpl}
+
+
+% \begin{xpl}
+% On considÃ¨re Ã  prÃ©sent que  $\mathsf{N}=9$, que $\mathcal{P}=\{2,7\}$ et que
+% $$s=\left\{
+% \begin{array}{l}
+% u=\underline{6,7,} ~ \underline{4,2,} ...\\
+% v=2,2,...
+% \end{array}
+% \right.$$
+% avec
+% $$\check{s}=\left\{
+% \begin{array}{l}
+% \check{u}=\underline{4, 9, 6, 3, 6, 6, 7,} ~ \underline{9, 8}, ...\\
+% \check{v}=7,2,...
+% \end{array}
+% \right.
+% $$
+
+% Ainsi $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.5173633305600000...$, 
+% puisque 
+% $|v^0-\check{v}^0|=5$, $|4963667-6700000| = 1736333$, $|v^1-\check{v}^1|=0$,
+% et $|9800000-4200000| = 5600000$.
+% \end{xpl}
+
+
+
+On a la proposition suivante, qui est dÃ©montrÃ©e en annexe~\ref{anx:generateur}.
+
+
+\begin{restatable}[Une distance dans $\mathcal{X}_{\mathsf{N},\mathcal{P}}$]{theorem}{distancedsxnp}
+$d$ est une distance sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$.
+\end{restatable}
+
+
+\subsection{Le graphe $\textsc{giu}_{\mathcal{P}}(f)$ Ã©tendant  $\textsc{giu}(f)$}
+
+A partir de  $\mathcal{P}=\{p_1, p_2, \hdots, p_\mathsf{p}\}$, on 
+dÃ©finit le graphe orientÃ© $\textsc{giu}_{\mathcal{P}}(f)$ de la maniÃ¨re suivante:
+\begin{itemize}
+\item les n{\oe}uds sont les  $2^\mathsf{N}$ configurations de $\mathds{B}^\mathsf{N}$,
+%\item Each vertex has $\displaystyle{\sum_{i=1}^\mathsf{p} \mathsf{N}^{p_i}}$ arrows, namely all the $p_1, p_2, \hdots, p_\mathsf{p}$ tuples 
+%  having their elements in $\llbracket 1, \mathsf{N} \rrbracket $.
+\item il y a un arc libellÃ© $u_0, \hdots, u_{p_i-1}$, $i \in \llbracket 1, \mathsf{p} \rrbracket$ entre les n{\oe}uds $x$ et $y$ si et seulement si $p_i$ est un Ã©lÃ©ment de 
+$\mathcal{P}$ (\textit{i.e.}, on peut itÃ©rer $p_i$ fois), et pour chaque 
+$k$, $0 \le k \le p_i-1$, on a 
+ $u_k$ qui appartient Ã   $[\mathsf{N}]$ et 
+$y=F_{f_u,p_i} (x, (u_0, \hdots, u_{p_i-1})) $.
+\end{itemize}
+Il n'est pas difficile de constater que $\textsc{giu}_{\{1\}}(f)$ est $\textsc{giu}(f)$.
+
+
+
+
+
+\begin{figure}%[t]
+  \begin{center}
+    \subfigure[$\textsc{giu}_{\{2\}}(h)$]{
+      \begin{minipage}{0.30\textwidth}
+        \begin{center}
+          \includegraphics[scale=0.5]{images/h2prng}
+        \end{center}
+      \end{minipage}
+      \label{fig:h2prng}
+    }
+    \subfigure[$\textsc{giu}_{\{3\}}(h)$]{
+      \begin{minipage}{0.40\textwidth}
+        \begin{center}
+          \includegraphics[scale=0.5]{images/h3prng}
+        \end{center}
+      \end{minipage}
+      \label{fig:h3prng}
+    }
+    \subfigure[$\textsc{giu}_{\{2,3\}}(h)$]{
+      \begin{minipage}{0.40\textwidth}
+        \begin{center}
+          \includegraphics[scale=0.5]{images/h23prng}
+        \end{center}
+      \end{minipage}
+      \label{fig:h23prng}
+    }
+
+    \end{center}
+    \caption{Graphes d'itÃ©rations $\textsc{giu}_{\mathcal{P}}(h)$ pour $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$}
+    %\label{fig:xplgraphIter}
+  \end{figure}
+
+
+
+
+\begin{xpl}
+On reprend l'exemple oÃ¹ $\mathsf{N}=2$ et 
+$h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$ dÃ©jÃ  dÃ©taillÃ© 
+Ã  la section~\ref{sub:prng:unif}.
+
+Le graphe $\textsc{giu}_{\{1\}}(h)$ a dÃ©jÃ  Ã©tÃ© donnÃ© Ã  la figure~\ref{fig:h:iter}.
+Les graphes $\textsc{giu}_{\{2\}}(h)$, $\textsc{giu}_{\{3\}}(h)$  et
+$\textsc{giu}_{\{2,3\}}(h)$ sont respectivement donnÃ©s aux figures~\ref{fig:h2prng}, ~\ref{fig:h3prng} et ~\ref{fig:h23prng}. 
+Le premier (respectivement le second) 
+illustre le comportement du gÃ©nÃ©rateur lorsque qu'on itÃ¨re exactement 
+2 fois (resp. 3 fois) puis qu'on affiche le rÃ©sultat.
+Le dernier donnerait le comportement d'un gÃ©nÃ©rateur qui s'autoriserait 
+Ã  itÃ©rer en interne systÃ©matiquement 2 ou 3 fois avant de retourner un rÃ©sultat.
+
+\end{xpl}
+
+
+\subsection{le PRNG de l'algorithme~\ref{CI Algorithm} est chaotique sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$}
+
+Le thÃ©orÃ¨me suivant, similaire Ã  ceux dans $\mathcal{X}_u$ et dans $\mathcal{X}_g$
+est prouvÃ© en annexe~\ref{anx:generateur}.
+
+\begin{restatable}[Conditions pour la chaoticitÃ© de $G_{f_u,\mathcal{P}}$]{theorem}{thmchoticitgfp}
+La fonction $G_{f_u,\mathcal{P}}$ est chaotique sur 
+ $(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$ si et seulement si 
+le graphe d'itÃ©rations $\textsc{giu}_{\mathcal{P}}(f)$ 
+est fortement connexe.
+\end{restatable}
+% On alors corollaire suivant 
+
+% \begin{corollary}
+%   Le gÃ©nÃ©rateur de nombre pseudo alÃ©atoire dÃ©taillÃ© 
+%   Ã  l'algorithme~\ref{CI Algorithm}
+%   n'est pas chaotique 
+%   sur $(\mathcal{X}_{\mathsf{N},\{b\}},d)$ pour la fonction nÃ©gation.
+% \end{corollary}
+% \begin{proof}
+%   Dans cet algorithme, $\mathcal{P}$ est le singleton $\{b\}$.
+%   Que $b$ soit pair ou impair,  $\textsc{giu}_{\{b\}}(f)$
+%   n'est pas fortement connexe.
+% \end{proof}
+
+
+
+
+\section{Conclusion}
+Ce chapitre a proposÃ© un algorithme permettant de construire un 
+PRNG chaotique Ã  partir d'un PRNG existant. Pour ce faire, il est nÃ©cessaire 
+et suffisant que la fonction $f$ qui est itÃ©rÃ©e un nombre $b$ de fois 
+possÃ¨de un $\textsc{giu}_{\{b\}}(f)$ fortement connexe et que sa matrice de Markov associÃ©e soit doublement stochastique.
+Le chapitre suivant montre comment construire une telle fonction.
+
+ 
+ 
