après remarques tof

[hdrcouchot.git] / 15RairoGen.tex

diff --git a/15RairoGen.tex b/15RairoGen.tex
index a950d85db07541011f26e064bd0ff2ab8756ac66..38920d84a268272246b2ab2c3ac81a4112f58e3d 100644 (file)
--- a/15RairoGen.tex
+++ b/15RairoGen.tex
@@ -5,25 +5,19 @@ 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
-à 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 distribution uniforme
-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}
- 

 
 

-\section{ Nombres pseudo aléatoires construits par itérations unaires}\label{sub:prng:algo}
+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{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}

 
 
 
 
 
 


@@ -33,16 +27,15 @@ 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}


@@ -51,22 +44,22 @@ return $x$\;
 \end{algorithm}
 
 \subsection{Algorithme d'un générateur}
 \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.
+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$;
 
 
 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 donné en paramètre.
+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.
 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é.
+Notre approche vise a donner des propriétés de chaos à ce générateur embarqué.

 
 
 % \textit{Random}$(l)$. 
 
 
 % \textit{Random}$(l)$. 


@@ -104,11 +97,14 @@ Notre approche vise a donner des propriétés de chaos a ce générateur embarqu
 
 Nous avons vu au chapitre~\ref{chap:carachaos} que 
 $G_{f_u}$ est chaotique dans l'espace $\mathcal{X}_u$ 
 
 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.
+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 $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 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}
 
 
 \subsection{Un générateur à sortie uniformément distribuée}\label{sub:prng:unif}
 


@@ -121,8 +117,8 @@ 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 probabilités 
+On énonce le théorème classique suivant liant les 
+vecteurs de probabilités 

 et les chaînes de Markov.
 
 
 et les chaînes de Markov.
 
 


@@ -143,8 +139,8 @@ et les chaînes de Markov.
 
 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 
 
 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}
 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}


@@ -153,7 +149,7 @@ 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}.
 \textit{A priori}, ces deux fonctions pourraient être intégrées
 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$.
 
 
 que cela l'est pour $h$.
 
 


@@ -287,10 +283,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$. 
 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 
 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 
 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 


@@ -298,28 +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 énonce 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 annexe~\ref{anx:generateur}.

 
 

-\begin{theorem}\label{thm:prng:u}
+\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
   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 
   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 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 
+  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.
   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.


@@ -327,7 +325,7 @@ 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}.
 
 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}}$. 
+Soit $e_i$ le $i^{\textrm{ème}}$ vecteur de la base canonique de $\R^{2^{n}}$. 

 Chacun des éléments $v_j$, $1 \le j \le 2^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 
 Chacun des éléments $v_j$, $1 \le j \le 2^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 


@@ -343,11 +341,11 @@ ce vecteur au vecteur $\pi=(\frac{1}{2^n},\ldots,\frac{1}{2^n})$
 Ainsi, on a 
 \begin{equation}
 b = \max\limits_{i \in \llbracket 1, 2^n \rrbracket} 
 Ainsi, on a 
 \begin{equation}
 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}
 
 \label{eq:mt:ex}
 \end{equation}
 


@@ -433,7 +431,7 @@ $\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 
 
 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).
 L'expérience a montré notamment que toutes ces fonctions
 passent avec succès cette batterie de tests.
 \emph{National Institute of Standards and Technology} (NIST).
 L'expérience a montré notamment que toutes ces fonctions
 passent avec succès cette batterie de tests.


@@ -444,11 +442,11 @@ Ceci est difficilement compatible avec la volonté d'avoir une sortie uniformém
 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 
 présenté à l'algorithme~\ref{CI Algorithm} et prouve ensuite que la fonction qu'il représente 
 
 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 


@@ -464,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 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
 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 \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
 
 $$


@@ -481,14 +478,14 @@ F_{f_u}(\hdots (F_{f_u}(F_{f_u}(x,u^0), u^1), \hdots), u^{p_i-1}).
 $$
 
 
 $$
 
 

-on construit l'espace 
+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}}=
  $\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$).
 


@@ -529,9 +526,9 @@ 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{itemize}
+\begin{enumerate}

 \item $e$ et $\check{e}$ sont des entiers appartenant à $\llbracket 0, 2^{\mathsf{N}-1} \rrbracket$. 
 \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 
+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})$.
 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})$.


@@ -544,7 +541,7 @@ $\check{u}^{\check{v}^0}, \check{u}^{\check{v}^0+1}, \hdots, \check{u}^{\check{v
 Plus précisément, soit 
 $p = \lfloor \log_{10}{(\max{\mathcal{P}})}\rfloor +1$ et 
 $n = \lfloor \log_{10}{(\mathsf{N})}\rfloor +1$.
 Plus précisément, soit 
 $p = \lfloor \log_{10}{(\max{\mathcal{P}})}\rfloor +1$ et 
 $n = \lfloor \log_{10}{(\mathsf{N})}\rfloor +1$.

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


@@ -552,7 +549,7 @@ $n = \lfloor \log_{10}{(\mathsf{N})}\rfloor +1$.
   $\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.
   $\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{itemize}
+\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 
 \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 


@@ -561,12 +558,12 @@ 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}|$,
 $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.
+$\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
 \item Le cas $v^0>\check{v}^0$ est similaire, et donc omis

-\end{itemize}
+\end{enumerate}

 \item Les $p$ suivants sont $|v^1-\check{v}^1|$, etc.
 \item Les $p$ suivants sont $|v^1-\check{v}^1|$, etc.

-\end{itemize}
-\end{itemize}
+\end{enumerate}
+\end{enumerate}

 
 
 La fonction $d$ peut se formaliser comme suit:
 
 
 La fonction $d$ peut se formaliser comme suit:


@@ -606,8 +603,10 @@ $\check{s}=\left\{
 \check{v}=2,1,...
 \end{array}
 \right.$.
 \check{v}=2,1,...
 \end{array}
 \right.$.

-
-Ainsi $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.010004000000000000000000011005 ...$
+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
 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


@@ -616,47 +615,49 @@ 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 
 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:
+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.
 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 à 
+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}
 
 
 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.
-$$
+% \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}
+% 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 annexes~\ref{anx:generateur}.
-\begin{lemma}
+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}}$.
 $d$ est une distance sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$.

-\end{lemma}
+\end{restatable}

 
 
 \subsection{Le graphe $\textsc{giu}_{\mathcal{P}}(f)$ étendant  $\textsc{giu}(f)$}
 
 
 \subsection{Le graphe $\textsc{giu}_{\mathcal{P}}(f)$ étendant  $\textsc{giu}(f)$}


@@ -668,8 +669,9 @@ définit le graphe orienté $\textsc{giu}_{\mathcal{P}}(f)$ de la manière suiva
 %\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 
 %\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), 
-chaque $u_k$ de la suite appartient à $[\mathsf{N}]$ et 
+$\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)$.
 $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)$.


@@ -683,7 +685,7 @@ Il n'est pas difficile de constater que $\textsc{giu}_{\{1\}}(f)$ est $\textsc{g
     \subfigure[$\textsc{giu}_{\{2\}}(h)$]{
       \begin{minipage}{0.30\textwidth}
         \begin{center}
     \subfigure[$\textsc{giu}_{\{2\}}(h)$]{
       \begin{minipage}{0.30\textwidth}
         \begin{center}

-          \includegraphics[height=4cm]{images/h2prng}
+          \includegraphics[scale=0.5]{images/h2prng}

         \end{center}
       \end{minipage}
       \label{fig:h2prng}
         \end{center}
       \end{minipage}
       \label{fig:h2prng}


@@ -691,7 +693,7 @@ Il n'est pas difficile de constater que $\textsc{giu}_{\{1\}}(f)$ est $\textsc{g
     \subfigure[$\textsc{giu}_{\{3\}}(h)$]{
       \begin{minipage}{0.40\textwidth}
         \begin{center}
     \subfigure[$\textsc{giu}_{\{3\}}(h)$]{
       \begin{minipage}{0.40\textwidth}
         \begin{center}

-          \includegraphics[height=4cm]{images/h3prng}
+          \includegraphics[scale=0.5]{images/h3prng}

         \end{center}
       \end{minipage}
       \label{fig:h3prng}
         \end{center}
       \end{minipage}
       \label{fig:h3prng}


@@ -699,7 +701,7 @@ Il n'est pas difficile de constater que $\textsc{giu}_{\{1\}}(f)$ est $\textsc{g
     \subfigure[$\textsc{giu}_{\{2,3\}}(h)$]{
       \begin{minipage}{0.40\textwidth}
         \begin{center}
     \subfigure[$\textsc{giu}_{\{2,3\}}(h)$]{
       \begin{minipage}{0.40\textwidth}
         \begin{center}

-          \includegraphics[height=4cm]{images/h23prng}
+          \includegraphics[scale=0.5]{images/h23prng}

         \end{center}
       \end{minipage}
       \label{fig:h23prng}
         \end{center}
       \end{minipage}
       \label{fig:h23prng}


@@ -720,39 +722,48 @@ $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$ déjà détail
 
 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
 
 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}. 
+$\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 
 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.
+à 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}}$}
 
 
 \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 à celui dans $\mathcal{X}_u$ et dans $\mathcal{X}_g$
-est prouvé en annexes~\ref{anx:generateur}.
+Le théorème suivant, similaire à ceux dans $\mathcal{X}_u$ et dans $\mathcal{X}_g$
+est prouvé en annexe~\ref{anx:generateur}.

 
 

-\begin{theorem}
+\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 
 La fonction $G_{f_u,\mathcal{P}}$ est chaotique sur 
  $(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$ si et seulement si 

-graphe d'itération $\textsc{giu}_{\mathcal{P}}(f)$ 
+le graphe d'itérations $\textsc{giu}_{\mathcal{P}}(f)$ 

 est fortement connexe.
 est fortement connexe.

-\end{theorem}
-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}_{\mathcal{b}}(f)$
-  n'est pas fortement connexe.
-\end{proof}
-
+\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.

 
 

+ 
+