From: Jean-François Couchot <couchot@couchot.iut-bm.univ-fcomte.fr>
Date: Thu, 16 Jul 2015 11:58:16 +0000 (+0200)
Subject: ajout de fichiers + 15Rairo
X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/commitdiff_plain/eb86b87fcb8bd9aa66283fcea4d9efbe964179ff

ajout de fichiers + 15Rairo
---

diff --git a/15RairoGen.tex b/15RairoGen.tex
index f2b9243..e4f8858 100644
--- a/15RairoGen.tex
+++ b/15RairoGen.tex
@@ -6,9 +6,8 @@ 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 {distributionuniforme} 
-La suite de ce document donnera, 
-dans le cas où le graphe d'itérations est fortement connexe, 
+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.
 
@@ -24,14 +23,12 @@ L'approche est évaluée dans la dernière section.
 \JFC{plan à revoir}
  
 
-\subsection{ Générateur de nombres pseudo aléatoires basé sur le chaos}\label{sub:prng:algo}
+\section{ Nombres pseudo aléatoires construits par itérations unaires}\label{sub:prng:algo}
 
 
 
 
 
-On peut penser à construire un générateur de nombres pseudo 
-aléatoires comme dans l'algorithme~\ref{CI Algorithm} donné ci-dessous.
 
 \begin{algorithm}[h]
 %\begin{scriptsize}
@@ -39,13 +36,13 @@ aléatoires comme dans l'algorithme~\ref{CI Algorithm} donné ci-dessous.
 une configuration initiale $x^0$ ($n$ bits)}
 \KwOut{une configuration $x$ ($n$ bits)}
 $x\leftarrow x^0$\;
-$k\leftarrow b + \textit{Random}(b+1)$\;
+$k\leftarrow b $\;
 %$k\leftarrow b + \textit{XORshift}(b+1)$\;
-\For{$i=0,\dots,k-1$}
+\For{$i=1,\dots,k$}
 {
 $s\leftarrow{\textit{Random}(n)}$\;
 %$s\leftarrow{\textit{XORshift}(n)}$\;
-$x\leftarrow{F_f(s,x)}$\;
+$x\leftarrow{F_{f_u}(s,x)}$\;
 }
 return $x$\;
 %\end{scriptsize}
@@ -54,11 +51,18 @@ return $x$\;
 \label{CI Algorithm}
 \end{algorithm}
 
+\subsection{Algorithme d'un générateur}
+On peut penser à construire un générateur de nombres pseudo 
+aléatoires comme dans l'algorithme~\ref{CI Algorithm} donné ci-dessous.
+
 
 Celui-ci prend en entrée: une fonction $f$;
 un entier $b$, qui assure que le nombre d'itérations
-est compris entre $b+1 $ et  $2b+1$ et une configuration initiale $x^0$.
-Il retourne une nouvelle configuration $x$.
+est compris entre $b+1 $ et  $2b+1$ (et donc supérieur à $b$) 
+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 
+à des itérations unaires.
 En interne, il exploite un algorithme de génération
 de nombres pseudo aléatoires
 \textit{Random}$(l)$. 
@@ -67,12 +71,8 @@ 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
-très rapides conçus par George Marsaglia. 
+nombres pseudo aléatoires conçus par George Marsaglia. 
 
-% L'algorithme \textit{XORshift} exploite itérativement
-% la fonction \og {xor}\fg{} $\oplus$ (cf. glossaire) 
-% sur des nombres obtenus grâce à des pl{decalageDeBits} (cf. glossaire).
 
 L'algorithme \textit{XORshift} 
 exploite itérativement l'opérateur $\oplus$  
@@ -98,13 +98,13 @@ return $y$\;
 \end{algorithm}
 
 
-
-Il reste à instancier une fonction $f$ dans 
-l'algorithme~\ref{CI Algorithm} 
-en adéquation avec  l'approche développée 
-en section~\ref{sec:sccg}.
-La section suivante montre comment l'uniformité de la distribution a
-contraint cette instanciation.
+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.
+Pour $b=1$, l'algorithme itère la fonction $F_{f_u}$.
+Regardons comment l'uniformité de la distribution a
+contraint la fonction.
 
 \subsection{Un générateur à sortie uniformément distribuée}\label{sub:prng:unif}
 
@@ -118,12 +118,13 @@ 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 
-vecteurDeProbabilite 
-et les chaineDeMarkov:
+vecteur de probabilite 
+et les chaines de Markov.
 
 
  
-\begin{Theo}\label{th}
+
+\begin{theorem}\label{th}
   Si $M$ est une matrice stochastique régulière, alors $M$ 
   possède un unique vecteur stationnaire de probabilités  $\pi$
   ($\pi.M = \pi$).
@@ -133,7 +134,7 @@ et les chaineDeMarkov:
   $\pi^{k+1} = \pi^k.M $ pour $k = 0, 1,\dots$ 
   alors la {chaineDeMarkov} $\pi^k$
   converge vers $\pi$ lorsque $k$ tend vers l'infini.
-\end{Theo}
+\end{theorem}
 
 
 Montrons sur un exemple jouet à deux éléments 
@@ -145,29 +146,93 @@ et $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$.
 Leurs graphes d'interactions donnés en figure \ref{fig:g:inter} et \ref{fig:h:inter}
 vérifient les hypothèses du théorème~\ref{th:Adrien}. 
 Leurs graphes d'itérations
-sont donc fortement connexes, ce que l'on a pu déjà vérifier aux figures
+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$.
 
 
+
+
+
+
+
+
+
+\begin{figure}%[t]
+  \begin{center}
+    \subfigure[$g(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}) $]{
+      \begin{minipage}{0.40\textwidth}
+        \begin{center}
+          \includegraphics[height=4cm]{images/g.pdf}
+        \end{center}
+      \end{minipage}
+      \label{fig:g:iter}
+    }
+    \subfigure[$h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$]{
+      \begin{minipage}{0.40\textwidth}
+        \begin{center}
+          \includegraphics[height=4cm]{images/h.pdf}
+        \end{center}
+      \end{minipage}
+      \label{fig:h:iter}
+    }    \end{center}
+    \caption{Graphes d'itérations de fonctions booléennes dans $\Bool^2$}
+    \label{fig:xplgraphIter}
+  \end{figure}
+
+
+
+
+
+
+
+
+
+\begin{figure}%[t]
+  \begin{center}
+    \subfigure[$g(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}) $]{
+      \begin{minipage}{0.40\textwidth}
+        \begin{center}
+          \includegraphics[height=3cm]{images/gp.pdf}
+        \end{center}
+      \end{minipage}
+      \label{fig:g:inter}
+    }
+    \subfigure[$h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$]{
+      \begin{minipage}{0.40\textwidth}
+        \begin{center}
+          \includegraphics[height=3cm]{images/hp.pdf}
+        \end{center}
+      \end{minipage}
+      \label{fig:h:inter}
+    }    \end{center}
+    \caption{Graphes d'interactions de fonctions booléennes dans $\Bool^2$}
+    \label{fig:xplgraphInter}
+  \end{figure}
+
+
+
+
+
+
 Comme le générateur \textit{Random} possède une sortie uniformément 
 distribuée,  la  stratégie est uniforme sur $\llbracket 1, 2 \rrbracket$,
 et donc, 
-pour tout sommet de $\Gamma(g)$ et de  $\Gamma(h)$,
+pour tout sommet de $\textsc{giu}(g)$ et de  $\textsc{giu}(h)$,
 chaque arc sortant de ce sommet a, parmi l'ensemble des arcs sortant 
 de ce sommet, une probabilité $1/2$ d’être celui qui sera traversé.
-En d'autres mots, $\Gamma(g)$ est le graphe orienté d'une chaîne de Markov.
-Il est facile de vérifier que la {matriceDeTransitions}
+En d'autres mots, $\textsc{giu}(g)$ est le graphe orienté d'une chaîne de Markov.
+Il est facile de vérifier que la matrice de transitions
 d'un tel processus 
 est $M_g   = \frac{1}{2} \check{M}_g$, 
-où $\check{M}_g$ est la {matriceDAdjacence}  donnée en 
+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$. 
 
 \begin{figure}[h]
   \begin{center}
-    \subfloat[$\check{M}_g $.]{
+    \subfigure[$\check{M}_g $.]{
       \begin{minipage}{0.25\textwidth}
         \begin{center}
           % \vspace{-3cm}
@@ -184,7 +249,7 @@ figure~\ref{fig:g:incidence} (voir ci-après), et similairement pour $M_h$.
       \end{minipage}
       \label{fig:g:incidence}
     }
-    \subfloat[$\check{M}_h $.]{
+    \subfigure[$\check{M}_h $.]{
         \begin{minipage}{0.25\textwidth}
           \begin{center}
             $\left( 
@@ -228,71 +293,24 @@ de valeurs  soit suffisamment grand de sorte que
 le vecteur d’état de la chaîne de Markov
 ait une distribution suffisamment proche de la distribution uniforme.
 
+On énnonce directement le théorème suivant dont la preuve est donnée en annexes~\ref{anx:generateur}.
 
-Considérons le lemme technique suivant:
-\begin{Lemma}\label{lem:stoc}
-Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\Gamma(f)$ son graphe d'itérations, $\check{M}$ la matrice d'adjacence de $\Gamma(f)$, et  $M$  la matrice 
-$2^n\times 2^n$  définie par
-$M = \frac{1}{n}\check{M}$.
-Alors $M$ est une matrice stochastique régulière si et seulement si
-$\Gamma(f)$ est fortement connexe.
-\end{Lemma}
-
-\begin{Proof}  
-On remarque tout d'abord que $M$ 
-est une matrice stochastique par construction.
-Supposons $M$ régulière. 
-Il existe donc  $k$ tel que $M_{ij}^k>0$ pour chaque $i,j\in \llbracket
-1;  2^n  \rrbracket$. L'inégalité  $\check{M}_{ij}^k>0$  est alors établie.
-Puisque $\check{M}_{ij}^k$ est le nombre de chemins de  $i$ à $j$ de longueur $k$
-dans $\Gamma(f)$ et puisque ce nombre est positif, alors 
-$\Gamma(f)$ est fortement connexe.
-
-Réciproquement si $\Gamma(f)$ 
-est fortement connexe, alors pour tous les sommets $i$ et $j$, un chemin peut être construit pour atteindre  $j$  depuis $i$ en au plus $2^n$ étapes.
-Il existe donc 
-$k_{ij} \in \llbracket 1,  2^n \rrbracket$ tels que $\check{M}_{ij}^{k_{ij}}>0$.  
-Comme tous les  multiples $l \times k_{ij}$ de $k_{ij}$ sont tels que 
-$\check{M}_{ij}^{l\times  k_{ij}}>0$, 
-on peut conclure que, si 
-$k$ est le plus petit multiple commun de $\{k_{ij}  \big/ i,j  \in \llbracket 1,  2^n \rrbracket  \}$ alors
-$\forall i,j  \in \llbracket  1, 2^n \rrbracket,  \check{M}_{ij}^{k}>0$. 
-Ainsi, $\check{M}$ et donc $M$ sont régulières.
-\end{Proof}
-
-Ces résultats permettent formuler et de prouver le théorème suivant:
-
-\begin{Theo}
-  Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\Gamma(f)$ son 
+\begin{theorem}
+  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.
-  Si $\Gamma(f)$ est fortement connexe, alors 
+  Si $\textsc{giu}(f)$ est fortement connexe, alors 
   la sortie du générateur de nombres pseudo aléatoires détaillé par 
   l'algorithme~\ref{CI Algorithm} suit une loi qui 
   tend vers la distribution uniforme si 
   et seulement si  $M$ est une matrice doublement stochastique.
-\end{Theo}
-\begin{Proof}
-  $M$ est une matrice stochastique régulière (Lemme~\ref{lem:stoc}) 
-  qui a un unique vecteur de probabilités stationnaire
-  (Théorème \ref{th}).
-  Soit $\pi$  défini par 
-  $\pi = \left(\frac{1}{2^n}, \hdots, \frac{1}{2^n} \right)$.
-  On a  $\pi M = \pi$ si et seulement si
-  la somme des valeurs de chaque colonne de $M$  est 1, 
-  \textit{i.e.} si et seulement si 
-  $M$ est  doublement  stochastique.
-\end{Proof}
-
-
-\subsection{Expérimentations}
-
-On considère le graphe d'interactions $G(f)$ donné en figure~\ref{fig:G}. 
-Il vérifie le théorème~\ref{th:Adrien}: 
-toutes les fonctions $f$ possédant un tel graphe d'interactions
-ont un graphe d'itérations  $\Gamma(f)$ fortement connexe.
-Pratiquement, un algorithme simple de satisfaction de contraintes
-a trouvé  520 fonctions $f$ non isomorphes de graphe d'interactions  $G(f)$, 
+\end{theorem}
+
+
+\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.
 
 La figure~\ref{fig:listfonction} explicite ces 16 fonctions en 
@@ -306,7 +324,7 @@ Soit $e_i$ le $i^{\textrm{ème}}$ vecteur la base canonique de $\R^{2^{n}}$.
 Chacun des éléments $v_j$, $1 \le j \le 2^n$, 
 du vecteur $e_i M_f^t$ représente la probabilité 
 d'être dans la configuration $j$ après $t$ étapes du processus de Markov 
-associé à $\Gamma(f)$ en partant de la configuration $i$.   
+associé à $\textsc{giu}(f)$ en partant de la configuration $i$.   
 Le nombre $\min \{
  t \mid t \in \Nats, \vectornorm{e_i M_f^t - \pi} < 10^{-4}
 \}$ représente le plus petit nombre d'itérations où la distance de 
@@ -326,7 +344,7 @@ $$
 
 \begin{figure}%[h]
   \begin{center}
-  \subfloat[Graphe d'interactions]{
+  \subfigure[Graphe d'interactions]{
     \begin{minipage}{0.20\textwidth}
       \begin{center}
         \includegraphics[width=3.5cm]{images/Gi.pdf}
@@ -334,7 +352,7 @@ $$
     \end{minipage}
     \label{fig:G}
   }\hfill
-  \subfloat[Fonctions doublement stochastiques]{
+  \subfigure[Fonctions doublement stochastiques]{
     \begin{minipage}{0.75\textwidth}
       \begin{scriptsize}
         \begin{center}
@@ -404,58 +422,209 @@ 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 
 \emph{National Institute of Standards and Technology} (NIST).
-% Pour les 15 tests, le seuil $\alpha$ est fixé à $1\%$:
-% une  valeur  
-% qui est plus grande que $1\%$  signifie 
-% que la chaîne est considérée comme aléatoire avec une confiance de $99\%$.
-% Le tableau~\ref{fig:TEST} donne une vision synthétique de toutes 
-% les expérimentations. 
 L'expérience a montré notamment que toutes ces fonctions
 passent avec succès cette batterie de tests.
 
+Pour conclure cette section, on remarque que le générateur de nombres pseudo-aléatoires 
+a été prouvé chaotique pour $b=1$, \textit{i.e.}, 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: 
+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
+est l'objectif de la section suivante.
+
+
+\section{Un PRNG basé sur des itérations unaires qui est chaotique }
+
+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 
+est chaotique sur cet espace.
 
+\subsection{Un espace  $\mathcal{X}_{\mathsf{N},\mathcal{P}}$    pour le PRNG de l'algorithme~\ref{CI Algorithm}}
 
 
-% \begin{table}[th]
-% \begin{scriptsize}
-% \begin{tabular}{|*{17}{c|}}
-% \hline
-% {Propriété}& $\mathcal{F}_{1}$ &$\mathcal{F}_{2}$ &$\mathcal{F}_{3}$ &$\mathcal{F}_{4}$ &$\mathcal{F}_{5}$ &$\mathcal{F}_{6}$ &$\mathcal{F}_{7}$ &$\mathcal{F}_{8}$ &$\mathcal{F}_{9}$ &$\mathcal{F}_{10}$ &$\mathcal{F}_{11}$ &$\mathcal{F}_{12}$ &$\mathcal{F}_{13}$ &$\mathcal{F}_{14}$ &$\mathcal{F}_{15}$ &$\mathcal{F}_{16}$ \\
-% \hline
-% Fréquence &77.9 &15.4 &83.4 &59.6 &16.3 &38.4 &20.2 &29.0 &77.9 &21.3 &65.8 &85.1 &51.4 &35.0 &77.9 &92.4 \\ 
-%  \hline 
-% Fréquence / bloc &88.3 &36.7 &43.7 &81.7 &79.8 &5.9 &19.2 &2.7 &98.8 &1.0 &21.3 &63.7 &1.4 &7.6 &99.1 &33.5 \\ 
-%  \hline 
-% Somme cummulée &76.4 &86.6 &8.7 &66.7 &2.2 &52.6 &20.8 &80.4 &9.8 &54.0 &73.6 &80.1 &60.7 &79.7 &76.0 &44.7 \\ 
-%  \hline 
-% Exécution &5.2 &41.9 &59.6 &89.8 &23.7 &76.0 &77.9 &79.8 &45.6 &59.6 &89.8 &2.4 &96.4 &10.9 &72.0 &11.5 \\ 
-%  \hline 
-% Longue exécution &21.3 &93.6 &69.9 &23.7 &33.5 &30.4 &41.9 &43.7 &30.4 &17.2 &41.9 &51.4 &59.6 &65.8 &11.5 &61.6 \\ 
-%  \hline 
-% Rang &1.0 &41.9 &35.0 &45.6 &51.4 &20.2 &31.9 &83.4 &89.8 &38.4 &61.6 &4.0 &21.3 &69.9 &47.5 &95.6 \\ 
-%  \hline 
-% Fourrier Rapide &40.1 &92.4 &97.8 &86.8 &43.7 &38.4 &76.0 &57.5 &36.7 &35.0 &55.4 &57.5 &86.8 &76.0 &31.9 &7.6 \\ 
-%  \hline 
-% Sans superposition &49.0 &45.7 &50.5 &51.0 &48.8 &51.2 &51.6 &50.9 &50.9 &48.8 &45.5 &47.3 &47.0 &49.2 &48.6 &46.4 \\ 
-%  \hline 
-% Avec Superposition &27.6 &10.9 &53.4 &61.6 &16.3 &2.7 &59.6 &94.6 &88.3 &55.4 &76.0 &23.7 &47.5 &91.1 &65.8 &81.7 \\ 
-%  \hline 
-% Universelle &24.9 &35.0 &72.0 &51.4 &20.2 &74.0 &40.1 &23.7 &9.1 &72.0 &4.9 &13.7 &14.5 &1.8 &93.6 &65.8 \\ 
-%  \hline 
-% Entropie approchée &33.5 &57.5 &65.8 &53.4 &26.2 &98.3 &53.4 &63.7 &38.4 &6.7 &53.4 &19.2 &20.2 &27.6 &67.9 &88.3 \\ 
-%  \hline 
-% Suite aléatoire &29.8 &35.7 &40.9 &36.3 &54.8 &50.8 &43.5 &46.0 &39.1 &40.8 &29.6 &42.0 &34.8 &33.8 &63.0 &46.3 \\ 
-%  \hline 
-% Suite aléatoire variante &32.2 &40.2 &23.0 &39.6 &47.5 &37.2 &56.9 &54.6 &53.3 &31.5 &23.0 &38.1 &52.3 &57.1 &47.7 &40.8 \\ 
-%  \hline 
-% Série &56.9 &58.5 &70.4 &73.2 &31.3 &45.9 &60.8 &39.9 &57.7 &21.2 &6.4 &15.6 &44.7 &31.4 &71.7 &49.1 \\ 
-%  \hline 
-% Complexité linéaire &24.9 &23.7 &96.4 &61.6 &83.4 &49.4 &49.4 &18.2 &3.5 &76.0 &24.9 &97.2 &38.4 &38.4 &1.1 &8.6 \\ 
-%  \hline
-% \end{tabular}
-% \end{scriptsize}
-% \caption{Test de NIST réalisé sur des instances de générateurs}\label{fig:TEST}  
-% \end{table}
 
+Introduisons tout d'abord $\mathcal{P} \subset \mathds{N}$ un ensemble fini non vide de cardinalité 
+$\mathsf{p} \in \mathds{N}^\ast$.
+Intuitivement, c'est le nombre d'itérations qu'il est autorisé de faire.
+On ordonne les $\mathsf{p}$ éléments de $\mathcal{P}$ comme suit: 
+$\mathcal{P} = \{ p_1, p_2, \hdots, p_\mathsf{p}\}$
+et $p_1< p_2< \hdots < p_\mathsf{p}$.
+Dans l'algorithme~\ref{CI Algorithm}, 
+$\mathsf{p}$ vaut 1 et  $p_1=b$. 
 
 
+Cet  algorithme peut être vu comme $b$ compostions de la function $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}
+\rightarrow \mathds{B}^\mathsf{N}$ définie par
+
+$$
+F_{f_u,p_i} (x,(u^0, u^1, \hdots, u^{p_i-1}))  \mapsto 
+F_{f_u}(\hdots (F_{f_u}(F_{f_u}(x,u^0), u^1), \hdots), u^{p_i-1}).
+$$
+
+
+on construit l'espace 
+ $\mathcal{X}_{\mathsf{N},\mathcal{P}}=  \mathds{B}^\mathsf{N} \times \mathds{S}_{\mathsf{N},\mathcal{P}}$, où
+$\mathds{S}_{\mathsf{N},\mathcal{P}}=
+\llbracket 1, \mathsf{N} \rrbracket^{\Nats}\times 
+\mathcal{P}^{\Nats}$. 
+Chaque élément de l'espace est une paire où le premier élément est 
+un $\mathsf{N}$-uplet de  $\Bool^{\mathsf{N}}$ (comme dans $\mathcal{X}_u$).
+Le second élément est aussi une paire $((u^k)_{k \in \Nats},(v^k)_{k \in \Nats})$ de suites infinies.
+La suite $(v^k)_{k \in \Nats}$ définit combien d'itérations sont exécutées au temps $k$ entre deux sorties.
+La séquence $(u^k)_{k \in \Nats}$ définit quel élément est modifié (toujours au temps $k$).
+
+Définissons la fonction de décallage  $\Sigma$ pour chaque  élément de $\mathds{S}_{\mathsf{N},\mathcal{P}}$.
+$$\begin{array}{cccc}
+\Sigma:&\mathds{S}_{\mathsf{N},\mathcal{P}} &\longrightarrow
+&\mathds{S}_{\mathsf{N},\mathcal{P}} \\
+& \left((u^k)_{k \in \mathds{N}},(v^k)_{k \in \mathds{N}}\right) & \longmapsto & \left(\sigma^{v^0}\left((u^k)_{k \in \mathds{N}}\right),\sigma\left((v^k)_{k \in \mathds{N}}\right)\right). 
+\end{array}
+$$
+En d'autres termes, $\Sigma$ reçoit deux suites $u$ et $v$ et 
+effectue $v^0$ décallage vers la droite sur la première et un décallage vers la droite 
+sur la seconde.
+
+
+Ainsi, les  sorties  $(y^0, y^1, \hdots )$ produites par le générateur détaillé dans 
+l'algorithme~\ref{CI Algorithm}
+sont les premiers  composants des itérations $X^0 = (x^0, (u,v))$ et $\forall n \in \mathds{N}, 
+X^{n+1} = G_{f_u,\mathcal{P}}(X^n)$ dans $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ où
+$G_{f_u,\mathcal{P}}$  est définie par:
+
+
+
+
+\begin{equation}
+\begin{array}{cccc}
+G_{f_u,\mathcal{P}} :&  \mathcal{X}_{\mathsf{N},\mathcal{P}} & \longrightarrow & \mathcal{X}_{\mathsf{N},\mathcal{P}}\\
+   & (e,(u,v)) & \longmapsto & \left( F_{f,v^0}\left( e, (u^0, \hdots, u^{v^0-1}\right), \Sigma (u,v) \right) .
+\end{array}
+\end{equation}
+
+
+
+\subsection{Une distance sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$}
+
+On définit la fonction  $d$ sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ comme suit:
+Soit  $x=(e,s)$ et $\check{x}=(\check{e},\check{s})$ dans 
+$\mathcal{X}_{\mathsf{N},\mathcal{P}} = \mathds{B}^\mathsf{N} \times \mathds{S}_{\mathsf{N},\mathcal{P}} $,
+où $s=(u,v)$ et $\check{s}=(\check{u},\check{v})$ sont dans $ \mathds{S}_{\mathsf{N},\mathcal{P}} = 
+\mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket} \times \mathcal{S}_\mathcal{P}$. 
+\begin{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}
+\end{itemize}
+
+
+
+
+\begin{xpl}
+Consider for instance that $\mathsf{N}=13$, $\mathcal{P}=\{1,2,11\}$ (so $\mathsf{p}=3$), and that
+$s=\left\{
+\begin{array}{l}
+u=\underline{6,} ~ \underline{11,5}, ...\\
+v=1,2,...
+\end{array}
+\right.$
+while
+$\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.
+\end{xpl}
+
+
+\begin{xpl}
+Consider now that $\mathsf{N}=9$, and $\mathcal{P}=\{2,7\}$, and that
+
+$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.$
+
+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}
+
+
+
+$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{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)}.$$
+\end{itemize}
+
+
+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)$}
+
+\subsection{le PRNG de l'algorithme~\ref{CI Algorithm} est chaotique sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$}
+
diff --git a/annexePreuveDistribution.tex b/annexePreuveDistribution.tex
new file mode 100644
index 0000000..7a05f11
--- /dev/null
+++ b/annexePreuveDistribution.tex
@@ -0,0 +1,57 @@
+ 
+Considérons le lemme technique suivant:
+\begin{lemma}\label{lem:stoc}
+Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\textsc{giu}(f)$ son graphe d'itérations, $\check{M}$ la matrice d'adjacence de $\textsc{giu}(f)$, et  $M$  la matrice 
+$2^n\times 2^n$  définie par
+$M = \frac{1}{n}\check{M}$.
+Alors $M$ est une matrice stochastique régulière si et seulement si
+$\textsc{giu}(f)$ est fortement connexe.
+\end{lemma}
+
+\begin{Proof}  
+On remarque tout d'abord que $M$ 
+est une matrice stochastique par construction.
+Supposons $M$ régulière. 
+Il existe donc  $k$ tel que $M_{ij}^k>0$ pour chaque $i,j\in \llbracket
+1;  2^n  \rrbracket$. L'inégalité  $\check{M}_{ij}^k>0$  est alors établie.
+Puisque $\check{M}_{ij}^k$ est le nombre de chemins de  $i$ à $j$ de longueur $k$
+dans $\textsc{giu}(f)$ et puisque ce nombre est positif, alors 
+$\textsc{giu}(f)$ est fortement connexe.
+
+Réciproquement si $\textsc{giu}(f)$ 
+est fortement connexe, alors pour tous les sommets $i$ et $j$, un chemin peut être construit pour atteindre  $j$  depuis $i$ en au plus $2^n$ étapes.
+Il existe donc 
+$k_{ij} \in \llbracket 1,  2^n \rrbracket$ tels que $\check{M}_{ij}^{k_{ij}}>0$.  
+Comme tous les  multiples $l \times k_{ij}$ de $k_{ij}$ sont tels que 
+$\check{M}_{ij}^{l\times  k_{ij}}>0$, 
+on peut conclure que, si 
+$k$ est le plus petit multiple commun de $\{k_{ij}  \big/ i,j  \in \llbracket 1,  2^n \rrbracket  \}$ alors
+$\forall i,j  \in \llbracket  1, 2^n \rrbracket,  \check{M}_{ij}^{k}>0$. 
+Ainsi, $\check{M}$ et donc $M$ sont régulières.
+\end{Proof}
+
+Ces résultats permettent formuler et de prouver le théorème suivant:
+
+\begin{theorem}
+  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.
+  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}
+
+\begin{Proof}
+  $M$ est une matrice stochastique régulière (Lemme~\ref{lem:stoc}) 
+  qui a un unique vecteur de probabilités stationnaire
+  (Théorème \ref{th}).
+  Soit $\pi$  défini par 
+  $\pi = \left(\frac{1}{2^n}, \hdots, \frac{1}{2^n} \right)$.
+  On a  $\pi M = \pi$ si et seulement si
+  la somme des valeurs de chaque colonne de $M$  est 1, 
+  \textit{i.e.} si et seulement si 
+  $M$ est  doublement  stochastique.
+\end{Proof}
+
diff --git a/annexePreuvePRNGchotique.tex b/annexePreuvePRNGchotique.tex
new file mode 100644
index 0000000..5277040
--- /dev/null
+++ b/annexePreuvePRNGchotique.tex
@@ -0,0 +1,328 @@
+
+
+
+
+
+\subsection{A metric on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$}
+
+We define a distance $d$ on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ as follows. 
+Consider 
+$x=(e,s)$ and $\check{x}=(\check{e},\check{s})$ in 
+$\mathcal{X}_{\mathsf{N},\mathcal{P}} = \mathds{B}^\mathsf{N} \times \mathds{S}_{\mathsf{N},\mathcal{P}} $,
+where $s=(u,v)$ and $\check{s}=(\check{u},\check{v})$ are in $ \mathds{S}_{\mathsf{N},\mathcal{P}} = 
+\mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket} \times \mathcal{S}_\mathcal{P}$. 
+\begin{itemize}
+\item $e$ and $\check{e}$ are integers belonging in $\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}
+\end{itemize}
+
+
+
+
+\begin{xpl}
+Consider for instance that $\mathsf{N}=13$, $\mathcal{P}=\{1,2,11\}$ (so $\mathsf{p}=3$), and that
+$s=\left\{
+\begin{array}{l}
+u=\underline{6,} ~ \underline{11,5}, ...\\
+v=1,2,...
+\end{array}
+\right.$
+while
+$\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.
+\end{xpl}
+
+
+\begin{xpl}
+Consider now that $\mathsf{N}=9$, and $\mathcal{P}=\{2,7\}$, and that
+
+$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.$
+
+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}
+
+
+
+$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{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)}.$$
+\end{itemize}
+
+
+Let us show that,
+\begin{prpstn}
+$d$ is a distance on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$.
+\end{prpstn}
+
+
+\begin{proof}
+ $d_{\mathds{B}^\mathsf{N}}$ is the Hamming distance. We will prove that 
+ $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}$ is a distance
+too, thus $d$ will also be a distance, being the sum of two distances.
+ \begin{itemize}
+\item Obviously, $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})\geqslant 0$, and if $s=\check{s}$, then 
+$d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=0$. Conversely, if $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=0$, then 
+$\forall k \in \mathds{N}, v^k=\check{v}^k$ due to the 
+definition of $d$. Then, as digits between positions $p+1$ and $p+n$ are null and correspond to $|u^0-\check{u}^0|$, we can conclude that $u^0=\check{u}^0$. An extension of this result to the whole first $n \times \max{(\mathcal{P})}$ bloc leads to $u^i=\check{u}^i$, $\forall i \leqslant v^0=\check{v}^0$, and by checking all the $n \times \max{(\mathcal{P})}$ blocs, $u=\check{u}$.
+ \item $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}$ is clearly symmetric 
+($d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(\check{s},s)$). 
+\item The triangle inequality is obtained because the absolute value satisfies it too.
+ \end{itemize}
+\end{proof}
+
+
+Before being able to study the topological behavior of the general 
+chaotic iterations, we must first establish that:
+
+\begin{prpstn}
+ For all $f:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N} $, the function $G_f$ is continuous on 
+$\left( \mathcal{X},d\right)$.
+\end{prpstn}
+
+
+\begin{proof}
+We will show this result by using the sequential continuity. Consider a
+sequence $x^n=(e^n,(u^n,v^n)) \in \mathcal{X}_{\mathsf{N},\mathcal{P}}^\mathds{N}$ such
+that $d(x^n,x) \longrightarrow 0$, for some $x=(e,(u,v))\in
+\mathcal{X}_{\mathsf{N},\mathcal{P}}$. We will show that
+$d\left(G_f(x^n),G_f(x)\right) \longrightarrow 0$.
+Remark that $u$ and $v$ are sequences of sequences.
+
+As $d(x^n,x) \longrightarrow 0$, there exists 
+$n_0\in\mathds{N}$ such that 
+$d(x^n,x) < 10^{-(p+n \max{(\mathcal{P})})}$
+(its $p+n \max{(\mathcal{P})}$ first digits are null). 
+In particular, $\forall n \geqslant n_0, e^n=e$,
+as the Hamming distance between the integral parts of
+$x$ and $\check{x}$ is 0. Similarly, due to the nullity 
+of the $p+n \max{(\mathcal{P})}$ first digits of 
+$d(x^n,x)$, we can conclude that $\forall n \geqslant n_0$,
+$(v^n)^0=v^0$, and that $\forall n \geqslant n_0$,
+$(u^n)^0=u^0$, $(u^n)^1=u^1$, ..., $(u^n)^{v^0-1}=u^{v^0-1}$.
+This implies that:
+\begin{itemize}
+\item $G_f(x^n)_1=G_f(x)_1$: they have the same
+Boolean vector as first coordinate.
+\item $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(\Sigma (u^n,v^n); \Sigma(u,v)) = 10^{p+n \max{(\mathcal{P})}} d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u^n,v^n); (u,v))$. As the right part of the equality tends
+to 0, we can deduce that it is the case too for the left part of the equality, and so
+$G_f(x^n)_2$ is convergent to $G_f(x)_2$.
+\end{itemize}
+\end{proof}
+
+
+
+\subsection{$\Gamma_{\mathcal{P}}(f)$ as an extension of  $\Gamma(f)$}
+
+Let $\mathcal{P}=\{p_1, p_2, \hdots, p_\mathsf{p}\}$.
+We define the directed graph $\Gamma_{\mathcal{P}}(f)$ as follows.
+\begin{itemize}
+\item Its vertices are the $2^\mathsf{N}$ elements of $\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 There is an arc labeled $u_0, \hdots, u_{p_i-1}$, $i \in \llbracket 1, \mathsf{p} \rrbracket$ between vertices $x$ and $y$ if and only if 
+$y=F_{f,p_i} (x, (u_0, \hdots, u_{p_i-1})) $.
+\end{itemize}
+
+It is not hard to see that the graph $\Gamma_{\{1\}}(f)$ is 
+$\Gamma(f)$.
+
+\begin{figure}[ht]
+  \centering
+  \begin{subfigure}[b]{0.45\textwidth}
+    \centering
+    \includegraphics[scale=0.85]{graphe1.pdf}
+    \caption{$\Gamma(f_0)$}
+    \label{graphe1}
+  \end{subfigure}%
+  ~ %add desired spacing between images, e. g. ~, \quad, \qquad, \hfill etc.
+  % (or a blank line to force the subfigure onto a new line)
+  \begin{subfigure}[b]{0.3\textwidth}
+    \centering  
+    \includegraphics[scale=0.85]{graphe2.pdf}
+    \caption{$\Gamma_{\{2,3\}}(f_0)$}
+    \label{graphe2}
+  \end{subfigure}
+  ~ %add desired spacing between images, e. g. ~, \quad, \qquad, \hfill etc.
+  \caption{Iterating $f_0:(x_1,x_2) \mapsto (\overline{x_1}, \overline{x_2})$}
+  \label{fig:itg}
+\end{figure}
+
+
+\begin{xpl}
+Consider for instance $\mathsf{N}=2$, 
+Let $f_0:\mathds{B}^2 \longrightarrow \mathds{B}^2$ be the negation function,
+\textit{i.e.}, $f_0(x_1,x_2) = (\overline{x_1}, \overline{x_2})$, and consider
+$\mathcal{P}=\{2,3\}$. The graphs of iterations are given in 
+\textsc{Figure~\ref{fig:itg}}.
+The \textsc{Figure~\ref{graphe1}} shows what happens when 
+displaying each iteration result.
+On the contrary, the \textsc{Figure~\ref{graphe2}} explicits the behaviors
+when always applying 2 or 3 modification and next outputing results. 
+Notice that here, orientations of arcs are not necessary 
+since the function $f_0$ is equal to its inverse $f_0^{-1}$. 
+\end{xpl}
+
+\subsection{Proofs of chaos}
+
+We will show that,
+\begin{prpstn}
+\label{prop:trans}
+ $\Gamma_{\mathcal{P}}(f)$ is strongly connected if and only if $G_f$ is 
+topologically transitive on $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$.
+\end{prpstn}
+
+
+\begin{proof}
+Suppose that $\Gamma_{\mathcal{P}}(f)$ is strongly connected. 
+Let $x=(e,(u,v)),\check{x}=(\check{e},(\check{u},\check{v})) 
+\in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ and $\varepsilon >0$.
+We will find a point $y$ in the open ball $\mathcal{B}(x,\varepsilon )$ and
+$n_0 \in \mathds{N}$ such that $G_f^{n_0}(y)=\check{x}$: this strong transitivity
+will imply the transitivity property.
+We can suppose that $\varepsilon <1$ without loss of generality. 
+
+Let us denote by $(E,(U,V))$  the elements of $y$. As
+$y$ must be in $\mathcal{B}(x,\varepsilon)$ and  $\varepsilon < 1$,
+$E$ must be equal to $e$. Let $k=\lfloor \log_{10} (\varepsilon) \rfloor +1$.
+$d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))$ must be lower than
+$\varepsilon$, so the $k$ first digits of the fractional part of 
+$d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))$ are null.
+Let $k_1$ the smallest integer such that, if $V^0=v^0$, ...,  $V^{k_1}=v^{k_1}$,
+ $U^0=u^0$, ..., $U^{\sum_{l=0}^{k_1}V^l-1} = u^{\sum_{l=0}^{k_1}v^l-1}$.
+Then $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))<\varepsilon$.
+In other words, any $y$ of the form $(e,((u^0, ..., u^{\sum_{l=0}^{k_1}v^l-1}),
+(v^0, ..., v^{k_1}))$ is in $\mathcal{B}(x,\varepsilon)$.
+
+Let $y^0$ such a point and $z=G_f^{k_1}(y^0) = (e',(u',v'))$. $\Gamma_{\mathcal{P}}(f)$
+being strongly connected, there is a path between $e'$ and $\check{e}$. Denote
+by $a_0, \hdots, a_{k_2}$ the edges visited by this path. We denote by
+$V^{k_1}=|a_0|$ (number of terms in the finite sequence $a_1$),
+$V^{k_1+1}=|a_1|$, ..., $V^{k_1+k_2}=|a_{k_2}|$, and by 
+$U^{k_1}=a_0^0$, $U^{k_1+1}=a_0^1$, ..., $U^{k_1+V_{k_1}-1}=a_0^{V_{k_1}-1}$,
+$U^{k_1+V_{k_1}}=a_1^{0}$, $U^{k_1+V_{k_1}+1}=a_1^{1}$,...
+
+Let $y=(e,((u^0, ..., u^{\sum_{l=0}^{k_1}v^l-1}, a_0^0, ..., a_0^{|a_0|}, a_1^0, ..., a_1^{|a_1|},..., 
+ a_{k_2}^0, ..., a_{k_2}^{|a_{k_2}|},$ \linebreak
+ $\check{u}^0, \check{u}^1, ...),(v^0, ..., v^{k_1},|a_0|, ...,
+ |a_{k_2}|,\check{v}^0, \check{v}^1, ...)))$. So $y\in \mathcal{B}(x,\varepsilon)$
+ and $G_{f}^{k_1+k_2}(y)=\check{x}$.
+ 
+ 
+Conversely, if $\Gamma_{\mathcal{P}}(f)$ is not strongly connected, then there are 
+2 vertices $e_1$ and $e_2$ such that there is no path between $e_1$ and $e_2$.
+That is, it is impossible to find $(u,v)\in \mathds{S}_{\mathsf{N},\mathcal{P}}$
+and $n \mathds{N}$ such that $G_f^n(e,(u,v))_1=e_2$. The open ball $\mathcal{B}(e_2, 1/2)$
+cannot be reached from any neighborhood of $e_1$, and thus $G_f$ is not transitive.
+\end{proof}
+
+
+We show now that,
+\begin{prpstn}
+If $\Gamma_{\mathcal{P}}(f)$ is strongly connected, then $G_f$ is 
+regular on $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$.
+\end{prpstn}
+
+\begin{proof}
+Let $x=(e,(u,v)) \in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ and $\varepsilon >0$. 
+As in the proofs of Prop.~\ref{prop:trans}, let $k_1 \in \mathds{N}$ such
+that 
+$$\left\{(e, ((u^0, ..., u^{v^{k_1-1}},U^0, U^1, ...),(v^0, ..., v^{k_1},V^0, V^1, ...)) \mid \right.$$
+$$\left.\forall i,j \in \mathds{N}, U^i \in \llbracket 1, \mathsf{N} \rrbracket, V^j \in \mathcal{P}\right\}
+\subset \mathcal{B}(x,\varepsilon),$$
+and $y=G_f^{k_1}(e,(u,v))$. $\Gamma_{\mathcal{P}}(f)$ being strongly connected,
+there is at least a path from the Boolean state $y_1$ of $y$ and $e$.
+Denote by $a_0, \hdots, a_{k_2}$ the edges of such a path.
+Then the point:
+$$(e,((u^0, ..., u^{v^{k_1-1}},a_0^0, ..., a_0^{|a_0|}, a_1^0, ..., a_1^{|a_1|},..., 
+ a_{k_2}^0, ..., a_{k_2}^{|a_{k_2}|},u^0, ..., u^{v^{k_1-1}},$$
+$$a_0^0, ...,a_{k_2}^{|a_{k_2}|}...),(v^0, ..., v^{k_1}, |a_0|, ..., |a_{k_2}|,v^0, ..., v^{k_1}, |a_0|, ..., |a_{k_2}|,...))$$
+is a periodic point in the neighborhood $\mathcal{B}(x,\varepsilon)$ of $x$.
+\end{proof}
+
+$G_f$ being topologically transitive and regular, we can thus conclude that
+\begin{thrm}
+The function $G_f$ is chaotic on $(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$ if
+and only if its iteration graph $\Gamma_{\mathcal{P}}(f)$ is strongly connected.
+\end{thrm}
+
+\begin{crllr}
+  The pseudorandom number generator $\chi_{\textit{14Secrypt}}$ is not chaotic
+  on $(\mathcal{X}_{\mathsf{N},\{b\}},d)$ for the negation function.
+\end{crllr}
+\begin{proof}
+  In this context, $\mathcal{P}$ is the singleton $\{b\}$.
+  If $b$ is even, any vertex $e$ of $\Gamma_{\{b\}}(f_0)$ cannot reach 
+  its neighborhood and thus $\Gamma_{\{b\}}(f_0)$ is not strongly connected. 
+  If $b$ is even, any vertex $e$ of $\Gamma_{\{b\}}(f_0)$ cannot reach itself 
+  and thus $\Gamma_{\{b\}}(f_0)$ is not strongly connected.
+\end{proof}
+
+The next section shows how to generate functions and a iteration number $b$
+such that $\Gamma_{\{b\}}$ is strongly connected.
+
+
+ 
\ No newline at end of file
diff --git a/main.tex b/main.tex
index dcbfa74..34e991d 100644
--- a/main.tex
+++ b/main.tex
@@ -17,6 +17,7 @@
 \usepackage[utf8]{inputenc}
 \usepackage{thmtools, thm-restate}
 \usepackage{multirow}
+\usepackage{algorithm2e}
 %\declaretheorem{theorem}
 
 %%--------------------
@@ -175,7 +176,7 @@ au chaos}
 
 \chapter[Caracterisation des systèmes 
   discrets chaotiques]{Caracterisation des systèmes 
-  discrets chaotiques pour les schémas unaires et généralisés}
+  discrets chaotiques pour les schémas unaires et généralisés}\label{chap:carachaos}
 
 La première section  rappelle ce que sont les systèmes dynamiques chaotiques.
 Dire que cette caractérisation dépend du type de stratégie : unaire (TIPE), 
@@ -195,7 +196,7 @@ On montre qu'on a des résultats similaires.
 \input{15TSI}
 
 
-\section{Générer des fonctions chaotiques}
+\section{Générer des fonctions chaotiques}\label{sec:11FCT}
 \input{11FCT} 
 
 \chapter{Prédiction des systèmes chaotiques}
@@ -290,7 +291,8 @@ par deux entiers voisins.
 \input{annexesccg}
 
 
-
+\chapter{Preuves sur les générateurs de nombres pseudo-aléatoires}\label{anx:generateur}
+\input{annexePreuveDistribution}
 
 \backmatter