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

Private GIT Repository
ajout de l'état de l'art PRBG chaotique
[hdrcouchot.git] / 15RairoGen.tex
index 06f84b1889cafed48dad42d9b8049dbfd0981dfb..c1cf7d310f8d3cf34b708214996e76a390768986 100644 (file)
@@ -6,26 +6,72 @@ 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. 
 
 On peut penser à exploiter une de ces fonctions $G_f$ 
 comme un générateur aléatoire. 
 
-Ce chapitre  présente une application directe
+Ce chapitre  présente donc une application directe
 de la théorie développée ci-avant
 de la théorie développée ci-avant
-à la génération de nombres pseudo aléatoires. 
-
-
-La suite de ce document donnera
-une condition nécessaire est suffisante pour que
-cette propriété soit satisfaite.
-
-
-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}
+à 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 et 
+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.
  
  
+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.
 
 
-\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}
 
 
 
 
 
 
@@ -52,8 +98,8 @@ 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$;
@@ -64,10 +110,10 @@ 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
 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 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)$. 
@@ -105,11 +151,11 @@ 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)$ 
+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}$.
 
 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 nombre pseudo-aléatoires
+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.
 se doit de fournir  des nombres selon une distribution uniforme.
 Regardons comment l'uniformité de la distribution 
 contraint la fonction $f$ à itérer.
@@ -126,7 +172,7 @@ 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 le théorème classique suivant liant les 
 $$\exists k \in \mathds{N}^\ast, \forall i,j \in \llbracket 1; n \rrbracket, M_{ij}^k>0.$$
 
 On énonce le théorème classique suivant liant les 
-vecteur de probabilités 
+vecteurs de probabilités 
 et les chaînes de Markov.
 
 
 et les chaînes de Markov.
 
 
@@ -147,8 +193,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}
@@ -157,7 +203,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$.
 
 
@@ -291,10 +337,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 
@@ -302,20 +348,20 @@ 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}
@@ -333,7 +379,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 
@@ -439,7 +485,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.
@@ -454,7 +500,7 @@ Montrer que les sous-séquences de suites chaotiques ainsi générées  demeuren
 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 
@@ -486,7 +532,7 @@ 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}}=
 [\mathsf{N}]^{\Nats}\times 
  $\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 
@@ -536,7 +582,7 @@ où $s=(u,v)$ et $\check{s}=(\check{u},\check{v})$ sont dans $ \mathds{S}_{\math
 \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$. 
 \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 
+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})$.
@@ -566,7 +612,7 @@ 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
 \end{enumerate}
 \item Les $p$ suivants sont $|v^1-\check{v}^1|$, etc.
 \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.
@@ -623,7 +669,7 @@ 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 
 0600000000000000000000. 
 De manière similaire, les $\check{v}^0=2$ premiers
 termes de $\check{u}$ sont représentés par 
@@ -660,10 +706,12 @@ la séquence.
 
 
 
 
 
 
-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)$}
@@ -677,7 +725,7 @@ définit le graphe orienté $\textsc{giu}_{\mathcal{P}}(f)$ de la manière suiva
 \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 
 \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 apaprtient à  $[\mathsf{N}]$ et 
+ $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)$.
@@ -728,12 +776,12 @@ $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}
 
 
 \end{xpl}
 
@@ -741,26 +789,37 @@ Le dernier donnerait le comportement d'un générateur qui s'autoriserait
 \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$
 \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}.
+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 
+\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}
 
 
-\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.
+