]> AND Private Git Repository - hdrcouchot.git/blobdiff - 15RairoGen.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
permiere version complete
[hdrcouchot.git] / 15RairoGen.tex
index e4f88582bd0509d851b304af9065da937d114af5..432991fb638780d70496df8040141d53282eeb99 100644 (file)
@@ -5,23 +5,17 @@ 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. 
 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. 
-Enfin, un bon générateur aléatoire se doit de 
-fournir  des nombres selon une distribution uniforme 
-La suite de ce document donnera
-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
+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 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 distributionuniforme
-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.
-\JFC{plan à revoir}
+La section~\ref{sub:prng:algo} 
+présente tout d'abord 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 ensuite étudiée en 
+section~\ref{prng:unaire:chaos}.
+La section~\ref{sub:prng:algo}  a été publiée à ~\cite{bcgw11:ip,bcgr11:ip}.
+
 
 \section{ Nombres pseudo aléatoires construits par itérations unaires}\label{sub:prng:algo}
 
 
 \section{ Nombres pseudo aléatoires construits par itérations unaires}\label{sub:prng:algo}
 
@@ -33,21 +27,19 @@ L'approche est évaluée dans la dernière section.
 \begin{algorithm}[h]
 %\begin{scriptsize}
 \KwIn{une fonction $f$, un nombre d'itérations $b$, 
 \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$\;
 $x\leftarrow x^0$\;
-$k\leftarrow b $\;
 %$k\leftarrow b + \textit{XORshift}(b+1)$\;
 %$k\leftarrow b + \textit{XORshift}(b+1)$\;
-\For{$i=1,\dots,k$}
+\For{$i=1,\dots,b$}
 {
 {
-$s\leftarrow{\textit{Random}(n)}$\;
+$s\leftarrow{\textit{Random}({\mathsf{N}})}$\;
 %$s\leftarrow{\textit{XORshift}(n)}$\;
 %$s\leftarrow{\textit{XORshift}(n)}$\;
-$x\leftarrow{F_{f_u}(s,x)}$\;
+$x\leftarrow{F_{f_u}(x,s)}$\;
 }
 return $x$\;
 %\end{scriptsize}
 }
 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}
 
 \label{CI Algorithm}
 \end{algorithm}
 
@@ -57,54 +49,62 @@ aléatoires comme dans l'algorithme~\ref{CI Algorithm} donné ci-dessous.
 
 
 Celui-ci prend en entrée: une fonction $f$;
 
 
 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 donc supérieur à $b$) 
+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 
 et une configuration initiale $x^0$.
 Il retourne une nouvelle configuration $x$ en appliquant 
-la fonction $F_{f_u}$ vue au chapitre~\ref{chap:carachaos} et correspondant 
+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
 à 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 distributionuniforme 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 decalages 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}
+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 a 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 le graphe d'itérations $\textsc{giu}(f)$ 
 
 
 Nous avons vu au chapitre~\ref{chap:carachaos} que 
 $G_{f_u}$ est chaotique dans l'espace $\mathcal{X}_u$ 
 si et seulement le graphe d'itérations $\textsc{giu}(f)$ 
-doit être fortement connexe.
+est fortement connexe.
 Pour $b=1$, l'algorithme itère la fonction $F_{f_u}$.
 Pour $b=1$, l'algorithme itère la fonction $F_{f_u}$.
-Regardons comment l'uniformité de la distribution a
-contraint la fonction.
+
+Pour simuler au mieux l'aléa, un bon générateur de nombre 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}
 
 
 \subsection{Un générateur à sortie uniformément distribuée}\label{sub:prng:unif}
 
@@ -117,9 +117,9 @@ 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.$$
 
 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 
-vecteur de probabilite 
-et les chaines de Markov.
+On énonce le théorème classique suivant liant les 
+vecteur de probabilités 
+et les chaînes de Markov.
 
 
  
 
 
  
@@ -128,11 +128,11 @@ et les chaines de Markov.
   Si $M$ est une matrice stochastique régulière, alors $M$ 
   possède un unique vecteur stationnaire de probabilités  $\pi$
   ($\pi.M = \pi$).
   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 {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$ 
  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 {chaineDeMarkov} $\pi^k$
+  alors la {chaîne de Markov} $\pi^k$
   converge vers $\pi$ lorsque $k$ tend vers l'infini.
 \end{theorem}
 
   converge vers $\pi$ lorsque $k$ tend vers l'infini.
 \end{theorem}
 
@@ -146,8 +146,8 @@ 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
 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 peut 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 
 que cela l'est pour $h$.
 \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 
 que cela l'est pour $h$.
@@ -178,7 +178,8 @@ que cela l'est pour $h$.
       \end{minipage}
       \label{fig:h:iter}
     }    \end{center}
       \end{minipage}
       \label{fig:h:iter}
     }    \end{center}
-    \caption{Graphes d'itérations de fonctions booléennes dans $\Bool^2$}
+    \caption{Graphes des itérations unaires 
+      de fonctions booléennes dans $\Bool^2$}
     \label{fig:xplgraphIter}
   \end{figure}
 
     \label{fig:xplgraphIter}
   \end{figure}
 
@@ -228,7 +229,7 @@ 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 matrice d' adjacence  donnée en 
 d'un tel processus 
 est $M_g   = \frac{1}{2} \check{M}_g$, 
 où $\check{M}_g$ est la matrice d' adjacence  donnée en 
-figure~\ref{fig:g:incidence} (voir ci-après), et similairement pour $M_h$. 
+figure~\ref{fig:g:incidence} (voir ci-après), et  de manière similaire pour $M_h$. 
 
 \begin{figure}[h]
   \begin{center}
 
 \begin{figure}[h]
   \begin{center}
@@ -293,26 +294,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.
 
 le vecteur d’état de la chaîne de Markov
 ait une distribution suffisamment proche de la distribution uniforme.
 
-On énnonce directement le théorème suivant dont la preuve est donnée en annexes~\ref{anx:generateur}.
+On énonce directement le théorème suivant dont la preuve est donnée en annexes~\ref{anx:generateur}.
 
 
-\begin{theorem}
+\begin{restatable}[Uniformité de la sortie de l'algorithme~\ref{CI Algorithm}]{theorem}{PrngCIUniforme}\label{thm:prng:u}
   Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\textsc{giu}(f)$ son 
   graphe d'itérations , $\check{M}$ sa matrice d'adjacence
   Soit $f: \Bool^{n} \rightarrow \Bool^{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.
+  et $M$ une matrice  $2^n\times 2^n$  
+  définie par 
+  $M = \dfrac{1}{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.
   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{theorem}
+\end{restatable}
 
 
 \subsection{Quelques exemples}
 
 
 
 \subsection{Quelques exemples}
 
-On reprend le graphe d'interactions $\Gamma(f)$ donné en figure~\ref{fig:G} à la section~\ref{sec:11FCT}.
-On a vu qu'il y avait  520 fonctions $f$ non isomorphes de graphe d'interactions  $\Gamma(f)$, 
-dont seulement 16 d'entre elles possédent une matrice doublement stochastique.
+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.
 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.
@@ -332,15 +337,21 @@ ce vecteur au vecteur $\pi=(\frac{1}{2^n},\ldots,\frac{1}{2^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
 -- 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$. 
+Ainsi, on a 
+\begin{equation}
 b = \max\limits_{i \in \llbracket 1, 2^n \rrbracket} 
 b = \max\limits_{i \in \llbracket 1, 2^n \rrbracket} 
-\{
-\min \{
+\left\{
+\min \left\{
  t \mid t \in \Nats, \vectornorm{e_i M_f^t - \pi} < 10^{-4}
  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}
 
 \begin{figure}%[h]
   \begin{center}
@@ -426,19 +437,19 @@ 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 
 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.}, lorqu'il y a une sortie pour chaque itération.
-Ceci est difficilement compatible avec la volonté d'avoir une sortie uniformémement distribuée: 
+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.
 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 les sous-séquences de suites chaotiques ainsi générées  demeurent chaotiques
+Montrer que les sous-séquences de suites chaotiques ainsi générées  demeurent chaotiques
 est l'objectif de la section suivante.
 
 
 est l'objectif de la section suivante.
 
 
-\section{Un PRNG basé sur des itérations unaires qui est chaotique }
+\section{Un PRNG basé sur des itérations unaires qui est chaotique }\label{prng:unaire:chaos}
 
 Cette section présente un espace métrique adapté au générateur de nombres pseudo-aléatoires 
 
 Cette section présente un espace métrique adapté au générateur de nombres pseudo-aléatoires 
-pésenté à l'algorithme~\ref{CI Algorithm} et prouve ensuite que la fonction qu'il représente 
+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}}
 est chaotique sur cet espace.
 
 \subsection{Un espace  $\mathcal{X}_{\mathsf{N},\mathcal{P}}$    pour le PRNG de l'algorithme~\ref{CI Algorithm}}
@@ -451,15 +462,14 @@ 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}$.
 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$. 
 Dans l'algorithme~\ref{CI Algorithm}, 
 $\mathsf{p}$ vaut 1 et  $p_1=b$. 
-
-
-Cet  algorithme peut être vu comme $b$ compostions de la function $F_{f_u}$.
+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
 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 \llbracket 1, \mathsf{N} \rrbracket^{p_i}
+$F_{{f_u},p_i} :  \mathds{B}^\mathsf{N} \times [\mathsf{N}]^{p_i}
 \rightarrow \mathds{B}^\mathsf{N}$ définie par
 
 $$
 \rightarrow \mathds{B}^\mathsf{N}$ définie par
 
 $$
@@ -471,15 +481,15 @@ $$
 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}}=
 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}}=
-\llbracket 1, \mathsf{N} \rrbracket^{\Nats}\times 
+[\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$).
 \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 aussi une paire $((u^k)_{k \in \Nats},(v^k)_{k \in \Nats})$ de suites infinies.
+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$).
 
 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écallage  $\Sigma$ pour chaque  élément de $\mathds{S}_{\mathsf{N},\mathcal{P}}$.
+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}} \\
 $$\begin{array}{cccc}
 \Sigma:&\mathds{S}_{\mathsf{N},\mathcal{P}} &\longrightarrow
 &\mathds{S}_{\mathsf{N},\mathcal{P}} \\
@@ -487,7 +497,7 @@ $$\begin{array}{cccc}
 \end{array}
 $$
 En d'autres termes, $\Sigma$ reçoit deux suites $u$ et $v$ et 
 \end{array}
 $$
 En d'autres termes, $\Sigma$ reçoit deux suites $u$ et $v$ et 
-effectue $v^0$ décallage vers la droite sur la première et un décallage vers la droite 
+effectue $v^0$ décalage vers la droite sur la première et un décalage vers la droite 
 sur la seconde.
 
 
 sur la seconde.
 
 
@@ -516,115 +526,244 @@ 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}$. 
 $\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}}$ sur 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), suivi 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}
 \begin{itemize}
-\item $e$ et $\check{e}$ sont des entiers appartenant à $\llbracket 0, 2^{\mathsf{N}-1} \rrbracket$. The Hamming distance
-on their binary decomposition, that is, the number of dissimilar binary digits, constitutes the integral
-part of $d(X,\check{X})$.
-\item The fractional part is constituted by the differences between $v^0$ and $\check{v}^0$, followed by the differences
-between finite sequences $u^0, u^1, \hdots, u^{v^0-1}$ and  $\check{u}^0, \check{u}^1, \hdots, \check{u}^{\check{v}^0-1}$, followed by 
- differences between $v^1$ and $\check{v}^1$, followed by the differences
-between $u^{v^0}, u^{v^0+1}, \hdots, u^{v^1-1}$ and  $\check{u}^{\check{v}^0}, \check{u}^{\check{v}^0+1}, \hdots, \check{u}^{\check{v}^1-1}$, etc.
-More precisely, let $p = \lfloor \log_{10}{(\max{\mathcal{P}})}\rfloor +1$ and $n = \lfloor \log_{10}{(\mathsf{N})}\rfloor +1$.
-\begin{itemize}
-\item The $p$ first digits of $d(x,\check{x})$ is $|v^0-\check{v}^0|$ written in decimal numeration (and with $p$ digits).
-\item The next $n\times \max{(\mathcal{P})}$ digits aim at measuring how much $u^0, u^1, \hdots, u^{v^0-1}$ differs from $\check{u}^0, \check{u}^1, \hdots, \check{u}^{\check{v}^0-1}$. The $n$ first
-digits are $|u^0-\check{u}^0|$. They are followed by 
-$|u^1-\check{u}^1|$ written with $n$ digits, etc.
-\begin{itemize}
-\item If
-$v^0=\check{v}^0$, then the process is continued until $|u^{v^0-1}-\check{u}^{\check{v}^0-1}|$ and the fractional
-part of $d(X,\check{X})$ is completed by 0's until reaching
-$p+n\times \max{(\mathcal{P})}$ digits.
-\item If $v^0<\check{v}^0$, then the $ \max{(\mathcal{P})}$  blocs of $n$
-digits are $|u^0-\check{u}^0|$, ..., $|u^{v^0-1}-\check{u}^{v^0-1}|$,
-$\check{u}^{v^0}$ (on $n$ digits), ..., $\check{u}^{\check{v}^0-1}$ (on $n$ digits), followed by 0's if required.
-\item The case $v^0>\check{v}^0$ is dealt similarly.
-\end{itemize}
-\item The next $p$ digits are $|v^1-\check{v}^1|$, etc.
-\end{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}
 
 
 
 \end{itemize}
 
 
 
-
 \begin{xpl}
 \begin{xpl}
-Consider for instance that $\mathsf{N}=13$, $\mathcal{P}=\{1,2,11\}$ (so $\mathsf{p}=3$), and that
+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.$
 $s=\left\{
 \begin{array}{l}
 u=\underline{6,} ~ \underline{11,5}, ...\\
 v=1,2,...
 \end{array}
 \right.$
-while
+avec 
 $\check{s}=\left\{
 \begin{array}{l}
 \check{u}=\underline{6,4} ~ \underline{1}, ...\\
 \check{v}=2,1,...
 \end{array}
 \right.$.
 $\check{s}=\left\{
 \begin{array}{l}
 \check{u}=\underline{6,4} ~ \underline{1}, ...\\
 \check{v}=2,1,...
 \end{array}
 \right.$.
-
-So $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.010004000000000000000000011005 ...$
-Indeed, the $p=2$ first digits are 01, as $|v^0-\check{v}^0|=1$, 
-and we use $p$ digits to code this difference ($\mathcal{P}$ being $\{1,2,11\}$, this difference can be equal to 10). We then take the $v^0=1$ first terms of $u$, each term being coded in $n=2$ digits, that is, 06. As we can iterate
-at most $\max{(\mathcal{P})}$ times, we must complete this
-value by some 0's in such a way that the obtained result
-has $n\times \max{(\mathcal{P})}=22$ digits, that is: 
-0600000000000000000000. Similarly, the $\check{v}^0=2$ first
-terms in $\check{u}$ are represented by 0604000000000000000000, and the absolute value of their
-difference is equal to 0004000000000000000000. These digits are concatenated to 01, and
-we start again with the remainder of the sequences.
+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 a $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}
 
 
 \end{xpl}
 
 
-\begin{xpl}
-Consider now that $\mathsf{N}=9$, and $\mathcal{P}=\{2,7\}$, and that
+% \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.
+% $$
 
 
-$s=\left\{
-\begin{array}{l}
-u=\underline{6,7,} ~ \underline{4,2,} ...\\
-v=2,2,...
-\end{array}
-\right.$
-while
-$\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}
 
 
-So $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.5173633305600000...$, as $|v^0-\check{v}^0|=5$, $|4963667-6700000| = 1736333$, $|v^1-\check{v}^1|=0$,
-and $|9800000-4200000| = 5600000$.
-\end{xpl}
 
 
 
 
+On a la proposition suivante, qui est démontrée en annexes~\ref{anx:generateur}.
 
 
-$d$ can be more rigorously written as follows:
-$$d(x,\check{x})=d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})+d_{\mathds{B}^\mathsf{N}}(e,\check{e}),$$
-where: % $p=\max \mathcal{P}$ and:
+
+\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}
 \begin{itemize}
-\item $d_{\mathds{B}^\mathsf{N}}$ is the Hamming distance,
-\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)}.$$
+\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}
 \end{itemize}
+Il n'est pas difficile de constater que $\textsc{giu}_{\{1\}}(f)$ est $\textsc{giu}(f)$.
 
 
 
 
-Let us show that,
-\begin{prpstn}
-$d$ is a distance on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$.
-\end{prpstn}
 
 
 
 
-\subsection{Le graphe $\textsc{giu}_{\mathcal{P}}(f)$ étendant  $\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 figure~\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 trois 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}}$}
 
 
 \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 annexes~\ref{anx:generateur}.
+
+\begin{restatable}[Conditions pour la choticité 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ération $\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.
+