X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/22c2a9bec00707660df698103219bde5268c6ef3..ac26aa33009d503bf9c04a2b00244c5bf723e694:/15RairoGen.tex

diff --git a/15RairoGen.tex b/15RairoGen.tex
index 0519ecb..c1cf7d3 100644
--- a/15RairoGen.tex
+++ b/15RairoGen.tex
@@ -1 +1,825 @@
- 
\ No newline at end of file
+Au bout d'un nombre $b$ d'itérations,
+si la fonction, notée $G_{f_u}$ (ou bien $G_{f_g}$) 
+présentée au chapitre~\ref{chap:carachaos}, 
+a de \og bonnes\fg{} propriétés chaotiques, 
+le mot $x^b$ devrait  \og sembler ne plus dépendre\fg{} de $x^0$.
+On peut penser à exploiter une de ces fonctions $G_f$ 
+comme un générateur aléatoire. 
+
+Ce chapitre  présente donc une application directe
+de la théorie développée ci-avant
+à la génération de nombres pseudo-aléatoires. 
+La section~\ref{sec:PRNG:chaos:autres} présente un état de l'art (incomplet) de l'exploitation de 
+fonctions au comportement chaotique pour obtenir des PRNGs.
+La section~\ref{sub:prng:algo} 
+présente ensuite l'algorithme de PRNG. La contrainte de  
+distribution uniforme de la sortie est discutée dans cette section.
+La chaoticité du générateur est  étudiée en 
+section~\ref{prng:unaire:chaos}.
+La section~\ref{sub:prng:algo}  a été publiée à ~\cite{bcgw11:ip,bcgr11:ip}.
+
+\section{Quelques PRNGs basés sur des fonctions aux itérations chaotiques}\label{sec:PRNG:chaos:autres}
+
+Les PRNGs chaotiques (CPRNGs) sont des générateurs non linéaires définis par 
+$x_0 \in \mathbb{R}$ et $x_{t+1} = f(x_t)$, où  $f$ est une fonction au comportement chaotique.
+Les raisons qui expliquent l'intérêt de telles fonctions sont naturellement la sensibilité aux conditions initiales, 
+leur imprévisibilité\ldots Cependant, comme l'ordinateur sur lequel elles s'exécutent a une précision finie, 
+les générateurs qui les embarquent peuvent avoir des périodes arbitrairement courtes, 
+ne pas fournir de sortie selon une distribution uniforme\ldots
+D'un point de vue cryptographique, ces CPRNGs sont critiquables~\cite{wiggins2003introduction}.
+Réduire ces critiques est l'objectif de nombreux travaux de recherche reportés ci dessous.
+
+
+Parmi les suites simples classiquement embarquées dans les CPRNGs, on trouve principalement
+la suite logistique 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}
+
+
+
+
+
+
+\begin{algorithm}[h]
+%\begin{scriptsize}
+\KwIn{une fonction $f$, un nombre d'itérations $b$, 
+une configuration initiale $x^0$ (${\mathsf{N}}$ bits)}
+\KwOut{une configuration $x$ (${\mathsf{N}}$ bits)}
+$x\leftarrow x^0$\;
+%$k\leftarrow b + \textit{XORshift}(b+1)$\;
+\For{$i=1,\dots,b$}
+{
+$s\leftarrow{\textit{Random}({\mathsf{N}})}$\;
+%$s\leftarrow{\textit{XORshift}(n)}$\;
+$x\leftarrow{F_{f_u}(x,s)}$\;
+}
+return $x$\;
+%\end{scriptsize}
+\caption{PRNG basé sur les itérations unaires.}
+\label{CI Algorithm}
+\end{algorithm}
+
+\subsection{Algorithme d'un générateur}
+On peut penser à construire un générateur de nombres 
+pseudo-aléatoires comme dans l'algorithme~\ref{CI Algorithm} donné ci-dessous.
+
+
+Celui-ci prend en entrée: une fonction $f$;
+un entier $b$, qui est le nombre d'itérations à effectuer entre deux sorties 
+et une configuration initiale $x^0$.
+Il retourne une nouvelle configuration $x$ en appliquant 
+la fonction $F_{f_u}$ (équation~\ref{eq:iterations:unaires}
+vue au chapitre~\ref{chap:carachaos}) et correspondant 
+à des itérations unaires.
+En interne, il exploite un algorithme de génération
+de nombres pseudo-aléatoires donné en paramètre.
+Cela peut être n'importe quel PRNG (XORshift, Mersenne-Twister) dont la 
+sortie est uniformément distribuée.
+Notre approche vise a donner des propriétés de chaos à ce générateur embarqué.
+
+
+% \textit{Random}$(l)$. 
+% Cet algorithme est utilisée dans notre générateur pour construire la longueur 
+% de la stratégie ainsi que les éléments qui la composent.
+% Pratiquement, il retourne des entiers dans $\llbracket 1 ; l \rrbracket$ 
+% selon une distribution uniforme et utilise 
+% \textit{XORshift} qui est une classe de générateurs de
+% nombres pseudo aléatoires conçus par George Marsaglia. 
+
+
+% L'algorithme \textit{XORshift} 
+% exploite itérativement l'opérateur $\oplus$  
+% sur des nombres obtenus grâce à des décalages de bits.
+% Cet opérateur, défini dans $\Bool^{n}$, 
+% applique la fonction \og  xor \fg{} 
+% aux bits de même rang de ses deux opérandes (\og opération bit à bit \fg{}).
+% Une instance de cette classe est donnée dans l'algorithme~\ref{XORshift} donné 
+% ci-dessous.
+
+% \begin{algorithm}[h]
+% %\SetLine
+% \KwIn{la configuration interne $z$ (un mot de 32-bit)}
+% \KwOut{$y$ (un mot de 32-bits)}
+% $z\leftarrow{z\oplus{(z\ll13)}}$\;
+% $z\leftarrow{z\oplus{(z\gg17)}}$\;
+% $z\leftarrow{z\oplus{(z\ll5)}}$\;
+% $y\leftarrow{z}$\;
+% return $y$\;
+% \medskip
+% \caption{Une boucle de l'algorithme de \textit{XORshift}}
+% \label{XORshift}
+% \end{algorithm}
+
+
+Nous avons vu au chapitre~\ref{chap:carachaos} que 
+$G_{f_u}$ est chaotique dans l'espace $\mathcal{X}_u$ 
+si et seulement si le graphe d'itérations $\textsc{giu}(f)$ 
+est fortement connexe.
+Pour $b=1$, l'algorithme itère la fonction $F_{f_u}$.
+
+Pour simuler au mieux l'aléa, un bon générateur de nombres pseudo-aléatoires
+se doit de fournir  des nombres selon une distribution uniforme.
+Regardons comment l'uniformité de la distribution 
+contraint la fonction $f$ à itérer.
+
+\subsection{Un générateur à sortie uniformément distribuée}\label{sub:prng:unif}
+
+Une matrice stochastique est une matrice carrée
+dont tous les éléments sont positifs ou nuls et dont
+la somme de chaque ligne
+vaut 1. 
+Une matrice stochastique l'est doublement si la somme de chaque colonne est 1.
+Enfin, une matrice stochastique de taille $n \times n$ est régulière 
+si  la propriété suivante est établie:
+$$\exists k \in \mathds{N}^\ast, \forall i,j \in \llbracket 1; n \rrbracket, M_{ij}^k>0.$$
+
+On énonce le théorème classique suivant liant les 
+vecteurs de probabilités 
+et les chaînes de Markov.
+
+
+ 
+
+\begin{theorem}\label{th}
+  Si $M$ est une matrice stochastique régulière, alors $M$ 
+  possède un unique vecteur stationnaire de probabilités  $\pi$
+  ($\pi.M = \pi$).
+  De plus, si $\pi^0$ est un {vecteur de probabilités} 
+ et si on définit 
+  la suite $(\pi^{k})^{k \in  \Nats}$ par 
+  $\pi^{k+1} = \pi^k.M $ pour $k = 0, 1,\dots$ 
+  alors la {chaîne de Markov} $\pi^k$
+  converge vers $\pi$ lorsque $k$ tend vers l'infini.
+\end{theorem}
+
+
+Montrons sur un exemple jouet à deux éléments 
+que ce théorème permet de vérifier si la sortie d'un générateur de 
+nombres pseudo-aléatoires est uniformément distribuée ou non.
+Soient alors $g$ et $h$ deux fonctions  de $\Bool^2$
+définies par $g(x_1,x_2)=(\overline{x_1},x_1.\overline{x_2}) $
+et $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$.
+Leurs graphes d'interactions donnés en figure \ref{fig:g:inter} et \ref{fig:h:inter}
+vérifient les hypothèses du théorème~\ref{th:Adrien}. 
+Leurs graphes d'itérations
+sont donc fortement connexes, ce que l'on 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 des itérations unaires 
+      de fonctions booléennes dans $\Bool^2$}
+    \label{fig:xplgraphIter}
+  \end{figure}
+
+
+
+
+
+
+
+
+
+\begin{figure}%[t]
+  \begin{center}
+    \subfigure[$g(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}) $]{
+      \begin{minipage}{0.40\textwidth}
+        \begin{center}
+          \includegraphics[height=3cm]{images/gp.pdf}
+        \end{center}
+      \end{minipage}
+      \label{fig:g:inter}
+    }
+    \subfigure[$h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$]{
+      \begin{minipage}{0.40\textwidth}
+        \begin{center}
+          \includegraphics[height=3cm]{images/hp.pdf}
+        \end{center}
+      \end{minipage}
+      \label{fig:h:inter}
+    }    \end{center}
+    \caption{Graphes d'interactions de fonctions booléennes dans $\Bool^2$}
+    \label{fig:xplgraphInter}
+  \end{figure}
+
+
+
+
+
+
+Comme le générateur \textit{Random} possède une sortie uniformément 
+distribuée,  la  stratégie est uniforme sur $\llbracket 1, 2 \rrbracket$,
+et donc, 
+pour tout sommet de $\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, $\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 matrice d' adjacence  donnée en 
+figure~\ref{fig:g:incidence} (voir ci-après), et  de manière similaire pour $M_h$. 
+
+\begin{figure}[h]
+  \begin{center}
+    \subfigure[$\check{M}_g $.]{
+      \begin{minipage}{0.25\textwidth}
+        \begin{center}
+          % \vspace{-3cm}
+          $\left( 
+            \begin{array}{cccc} 
+              1 & 0 & 1 & 0 \\ 
+              1 & 0 & 0 & 1 \\ 
+              1 & 0 & 0 & 1 \\ 
+              0 & 1 & 1 & 0 
+            \end{array}
+          \right)
+          $
+        \end{center}
+      \end{minipage}
+      \label{fig:g:incidence}
+    }
+    \subfigure[$\check{M}_h $.]{
+        \begin{minipage}{0.25\textwidth}
+          \begin{center}
+            $\left( 
+              \begin{array}{cccc} 
+                1 & 0 & 1 & 0 \\ 
+                0 & 1 & 0 & 1 \\ 
+                1 & 0 & 0 & 1 \\ 
+                0 & 1 & 1 & 0 
+              \end{array}
+            \right)
+            $
+          \end{center}
+        \end{minipage}
+        \label{fig:h:incidence}
+      }
+    \end{center}
+    \caption{Graphe des fonctions candidates avec $n=2$}
+    \label{fig:xplgraph}
+  \end{figure}
+
+Les deux matrices $M_g$ et $M_h$ sont  stochastiques. Pour
+montrer qu'elles sont régulières il suffit de constater qu'aucun élément de 
+$M^5_g$ ni de  $M^3_h$ n'est nul.
+De plus, les vecteurs de probabilités 
+$\pi_g=(\frac{4}{10}, \frac{1}{10},\frac{3}{10},\frac{2}{10})$ et
+$\pi_h=(\frac{1}{4},\frac{1}{4},\frac{1}{4},\frac{1}{4})$ 
+vérifient $\pi_g M_g = \pi_g$ et 
+$\pi_h M_h = \pi_h$. 
+Alors d'après le théorème~\ref{th}, 
+pour n'importe quel vecteur initial de probabilités $\pi^0$, on a 
+$\lim_{k \to \infty} \pi^0 M^k_g = \pi_g$ et 
+$\lim_{k \to \infty} \pi^0 M^k_h = \pi_h$. 
+Ainsi la chaîne de Markov associée à $h$ tend vers une 
+distribution uniforme, contrairement à celle associée à $g$.
+On en déduit que $g$ ne devrait pas être itérée dans 
+un générateur de nombres pseudo-aléatoires.
+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 
+de valeurs  soit suffisamment grand de sorte que
+le vecteur d’état de la chaîne de Markov
+ait une distribution suffisamment proche de la distribution uniforme.
+
+On énonce directement le théorème suivant dont la preuve est donnée en annexe~\ref{anx:generateur}.
+
+\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 
+  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{restatable}
+
+
+\subsection{Quelques exemples}
+
+On considère le graphe d'interactions $\Gamma(f)$ donné
+en figure~\ref{fig:G}. C'est le même qui a été présenté
+à la section~\ref{sec:11FCT}.
+On a vu qu'il y avait  520 fonctions $f$ non isomorphes de graphe d'interactions  $\Gamma(f)$. 
+
+Seulement 16 d'entre elles possèdent une matrice doublement stochastique.
+La figure~\ref{fig:listfonction} explicite ces 16 fonctions en 
+définissant les images des éléments de la liste
+0, 1, 2,\ldots, 14, 15 en respectant  l'ordre.
+Expliquons enfin comment a été calculé le nombre de la troisième 
+colonne utilisé comme le paramètre $b$ 
+dans l'algorithme~\ref{CI Algorithm}.
+
+Soit $e_i$ le $i^{\textrm{ème}}$ vecteur 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 
+associé à $\textsc{giu}(f)$ en partant de la configuration $i$.   
+Le nombre $\min \{
+ t \mid t \in \Nats, \vectornorm{e_i M_f^t - \pi} < 10^{-4}
+\}$ représente le plus petit nombre d'itérations où la distance de 
+ce vecteur au vecteur $\pi=(\frac{1}{2^n},\ldots,\frac{1}{2^n})$
+-- autrement dit, où la déviation par rapport à la distribution uniforme --
+ est inférieure 
+à $10^{-4}$. En prenant le max pour tous les $e_i$, on obtient une valeur pour
+ $b$. 
+Ainsi, on a 
+\begin{equation}
+b = \max\limits_{i \in \llbracket 1, 2^n \rrbracket} 
+\left\{
+\min \left\{
+ t \mid t \in \Nats, \vectornorm{e_i M_f^t - \pi} < 10^{-4}
+\right\}
+\right\}. 
+\label{eq:mt:ex}
+\end{equation}
+
+\noindent Par la suite, ce nombre sera appelé \emph{temps de mélange}.
+
+
+
+\begin{figure}%[h]
+  \begin{center}
+  \subfigure[Graphe d'interactions]{
+    \begin{minipage}{0.20\textwidth}
+      \begin{center}
+        \includegraphics[width=3.5cm]{images/Gi.pdf}
+      \end{center}
+    \end{minipage}
+    \label{fig:G}
+  }\hfill
+  \subfigure[Fonctions doublement stochastiques]{
+    \begin{minipage}{0.75\textwidth}
+      \begin{scriptsize}
+        \begin{center}
+          \begin{tabular}{|c|c|c|}
+\hline
+{Nom}& {Définition}&{$b$} \\
+\hline 
+$\mathcal{F}_1$ & 14, 15, 12, 13, 10, 11, 8, 9, 6, 7, 4, 5, 2, 3, 1, 0  & 206\\
+\hline
+$\mathcal{F}_2$ &14, 15, 12, 13, 10, 11, 8, 9, 6, 7, 5, 4, 3, 2, 0, 1  
+ & 94 \\
+\hline
+$\mathcal{F}_3$ &14, 15, 12, 13, 10, 11, 8, 9, 6, 7, 5, 4, 3, 2, 1, 0
+ & 69 \\
+\hline
+$\mathcal{F}_4$ &14, 15, 12, 13, 10, 11, 9, 8, 6, 7, 5, 4, 3, 2, 0, 1
+ & 56 \\
+\hline
+$\mathcal{F}_5$ &14, 15, 12, 13, 10, 11, 9, 8, 6, 7, 5, 4, 3, 2, 1, 0
+ & 48 \\
+\hline
+$\mathcal{F}_6$ &14, 15, 12, 13, 10, 11, 9, 8, 7, 6, 4, 5, 2, 3, 0, 1
+ & 86 \\
+\hline
+$\mathcal{F}_7$ &14, 15, 12, 13, 10, 11, 9, 8, 7, 6, 4, 5, 2, 3, 1, 0
+ & 58 \\
+\hline
+$\mathcal{F}_8$ &14, 15, 12, 13, 10, 11, 9, 8, 7, 6, 4, 5, 3, 2, 1, 0
+ & 46 \\
+\hline
+$\mathcal{F}_9$ &14, 15, 12, 13, 10, 11, 9, 8, 7, 6, 5, 4, 3, 2, 0, 1
+ & 42 \\
+\hline
+$\mathcal{F}_{10}$ &14, 15, 12, 13, 10, 11, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
+ & 69 \\
+\hline
+$\mathcal{F}_{11}$ &14, 15, 12, 13, 11, 10, 9, 8, 7, 6, 5, 4, 2, 3, 1, 0
+ & 58 \\
+\hline
+$\mathcal{F}_{12}$ &14, 15, 13, 12, 11, 10, 8, 9, 7, 6, 4, 5, 2, 3, 1, 0
+ & 35 \\
+\hline
+$\mathcal{F}_{13}$ &14, 15, 13, 12, 11, 10, 8, 9, 7, 6, 4, 5, 3, 2, 1, 0
+ & 56 \\
+\hline
+$\mathcal{F}_{14}$ &14, 15, 13, 12, 11, 10, 8, 9, 7, 6, 5, 4, 3, 2, 1, 0
+ & 94 \\
+\hline
+$\mathcal{F}_{15}$ &14, 15, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 0, 1
+ & 86 \\ 
+\hline
+$\mathcal{F}_{16}$ &14, 15, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
+  & 206 \\
+ \hline
+\end{tabular}
+\end{center}
+\end{scriptsize}
+\end{minipage}
+\label{fig:listfonction}
+}
+\end{center}
+\caption{Candidates pour le générateur  avec $n=4$}
+ \end{figure}
+
+
+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).
+L'expérience a montré notamment que toutes ces fonctions
+passent avec succès cette batterie de tests.
+
+Pour conclure cette section, on remarque que le générateur de nombres pseudo-aléatoires 
+a été prouvé chaotique pour $b=1$, \textit{i.e.}, lorsqu'il y a une sortie pour chaque itération.
+Ceci est difficilement compatible avec la volonté d'avoir une sortie uniformément distribuée: 
+se rapprocher de cette distribution nécessite en effet un nombre plus élevé
+d'itérations $b$ entre chaque sortie. Par exemple, dans l'exemple précédent, il est nécessaire 
+d'itérer au moins 42 fois entre chaque sortie pour suivre une loi uniforme à $10^{-4}$ près.
+Montrer que les sous-séquences de suites chaotiques ainsi générées  demeurent chaotiques
+est l'objectif de la section suivante.
+
+
+\section{Un PRNG basé sur des itérations unaires qui est chaotique }\label{prng:unaire:chaos}
+
+Cette section présente un espace métrique adapté au générateur de nombres pseudo-aléatoires 
+présenté à l'algorithme~\ref{CI Algorithm} et prouve ensuite que la fonction qu'il représente 
+est chaotique sur cet espace.
+
+\subsection{Un espace  $\mathcal{X}_{\mathsf{N},\mathcal{P}}$    pour le PRNG de l'algorithme~\ref{CI Algorithm}}
+
+
+
+Introduisons tout d'abord $\mathcal{P} \subset \mathds{N}$ un ensemble fini non vide de cardinalité 
+$\mathsf{p} \in \mathds{N}^\ast$.
+Intuitivement, c'est le nombre d'itérations qu'il est autorisé de faire.
+On ordonne les $\mathsf{p}$ éléments de $\mathcal{P}$ comme suit: 
+$\mathcal{P} = \{ p_1, p_2, \hdots, p_\mathsf{p}\}$
+et $p_1< p_2< \hdots < p_\mathsf{p}$.
+
+Dans l'algorithme~\ref{CI Algorithm}, 
+$\mathsf{p}$ vaut 1 et  $p_1=b$. 
+Cet  algorithme peut être vu comme $b$ compostions de la fonction $F_{f_u}$.
+Ceci peut cependant se généraliser à $p_i$, $p_i \in \mathcal{P}$,
+compositions fonctionnelles de $F_{f_u}$.
+Ainsi, pour chaque $p_i \in \mathcal{P}$, on construit la fonction
+$F_{{f_u},p_i} :  \mathds{B}^\mathsf{N} \times [\mathsf{N}]^{p_i}
+\rightarrow \mathds{B}^\mathsf{N}$ définie par
+
+$$
+F_{f_u,p_i} (x,(u^0, u^1, \hdots, u^{p_i-1}))  \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}}=
+[\mathsf{N}]^{\Nats}\times 
+\mathcal{P}^{\Nats}$. 
+Chaque élément de l'espace est une paire où le premier élément est 
+un $\mathsf{N}$-uplet de  $\Bool^{\mathsf{N}}$ (comme dans $\mathcal{X}_u$).
+Le second élément est une paire $((u^k)_{k \in \Nats},(v^k)_{k \in \Nats})$ de suites infinies.
+La suite $(v^k)_{k \in \Nats}$ définit combien d'itérations sont exécutées au temps $k$ entre deux sorties.
+La séquence $(u^k)_{k \in \Nats}$ définit quel élément est modifié (toujours au temps $k$).
+
+Définissons la fonction de décalage  $\Sigma$ pour chaque  élément de $\mathds{S}_{\mathsf{N},\mathcal{P}}$.
+$$\begin{array}{cccc}
+\Sigma:&\mathds{S}_{\mathsf{N},\mathcal{P}} &\longrightarrow
+&\mathds{S}_{\mathsf{N},\mathcal{P}} \\
+& \left((u^k)_{k \in \mathds{N}},(v^k)_{k \in \mathds{N}}\right) & \longmapsto & \left(\sigma^{v^0}\left((u^k)_{k \in \mathds{N}}\right),\sigma\left((v^k)_{k \in \mathds{N}}\right)\right). 
+\end{array}
+$$
+En d'autres termes, $\Sigma$ reçoit deux suites $u$ et $v$ et 
+effectue $v^0$ décalage vers la droite sur la première et un décalage vers la droite 
+sur la seconde.
+
+
+Ainsi, les  sorties  $(y^0, y^1, \hdots )$ produites par le générateur détaillé dans 
+l'algorithme~\ref{CI Algorithm}
+sont les premiers  composants des itérations $X^0 = (x^0, (u,v))$ et $\forall n \in \mathds{N}, 
+X^{n+1} = G_{f_u,\mathcal{P}}(X^n)$ dans $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ où
+$G_{f_u,\mathcal{P}}$  est définie par:
+
+
+
+
+\begin{equation}
+\begin{array}{cccc}
+G_{f_u,\mathcal{P}} :&  \mathcal{X}_{\mathsf{N},\mathcal{P}} & \longrightarrow & \mathcal{X}_{\mathsf{N},\mathcal{P}}\\
+   & (e,(u,v)) & \longmapsto & \left( F_{f,v^0}\left( e, (u^0, \hdots, u^{v^0-1}\right), \Sigma (u,v) \right) .
+\end{array}
+\end{equation}
+
+
+
+\subsection{Une distance sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$}
+
+On définit la fonction  $d$ sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ comme suit:
+Soit  $x=(e,s)$ et $\check{x}=(\check{e},\check{s})$ dans 
+$\mathcal{X}_{\mathsf{N},\mathcal{P}} = \mathds{B}^\mathsf{N} \times \mathds{S}_{\mathsf{N},\mathcal{P}} $,
+où $s=(u,v)$ et $\check{s}=(\check{u},\check{v})$ sont dans $ \mathds{S}_{\mathsf{N},\mathcal{P}} = 
+\mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket} \times \mathcal{S}_\mathcal{P}$. 
+\begin{enumerate}
+\item $e$ et $\check{e}$ sont des entiers appartenant à $\llbracket 0, 2^{\mathsf{N}-1} \rrbracket$. 
+La distance de Hamming $d_{\mathds{B}^\mathsf{N}}$ entre les 
+décompositions binaires de $e$ et de $\check{e}$ (\textit{i.e.}, le 
+le nombre de bits qu'elles ont de différent) constitue 
+la partie entière de $d(X,\check{X})$.
+\item la partie décimale est construite à partir des différences entre 
+$v^0$ et $\check{v}^0$, suivie des différences entre les séquences finies
+$u^0, u^1, \hdots, u^{v^0-1}$ et  $\check{u}^0, \check{u}^1, \hdots, \check{u}^{\check{v}^0-1}$, suivie par les différences entre  $v^1$ et $\check{v}^1$, 
+suivie par les différences entre $u^{v^0}, u^{v^0+1}, \hdots, u^{v^1-1}$ et
+$\check{u}^{\check{v}^0}, \check{u}^{\check{v}^0+1}, \hdots, \check{u}^{\check{v}^1-1}$, etc.
+
+Plus précisément, soit 
+$p = \lfloor \log_{10}{(\max{\mathcal{P}})}\rfloor +1$ et 
+$n = \lfloor \log_{10}{(\mathsf{N})}\rfloor +1$.
+\begin{enumerate}
+\item Les $p$ premiers éléments de $d(x,\check{x})$ sont $|v^0-\check{v}^0|$ 
+  écrits en base 10 et sur $p$ indices;
+\item les $n\times \max{(\mathcal{P})}$ éléments suivants servent 
+  à évaluer de combien $u^0, u^1, \hdots, u^{v^0-1}$ diffère de 
+  $\check{u}^0, \check{u}^1, \hdots, \check{u}^{\check{v}^0-1}$. 
+  Les $n$ premiers éléments sont $|u^0-\check{u}^0|$. Il sont suivis de 
+$|u^1-\check{u}^1|$ écrits à l'aide de $n$ éléments, etc.
+\begin{enumerate}
+\item Si
+$v^0=\check{v}^0$,
+alors le processus se continue jusqu'à $|u^{v^0-1}-\check{u}^{\check{v}^0-1}|$ et la 
+partie décimale de $d(X,\check{X})$ est complétée par des 0
+jusqu'à atteindre 
+$p+n\times \max{(\mathcal{P})}$ éléments.
+\item Si $v^0<\check{v}^0$, alors les $ \max{(\mathcal{P})}$  blocs de $n$
+éléments sont $|u^0-\check{u}^0|$, ..., $|u^{v^0-1}-\check{u}^{v^0-1}|$,
+$\check{u}^{v^0}$ (sur $n$ éléments), ..., $\check{u}^{\check{v}^0-1}$ (sur $n$ éléments), suivis par des 0, si besoin.
+\item Le cas $v^0>\check{v}^0$ est similaire, et donc omis
+\end{enumerate}
+\item Les $p$ suivants sont $|v^1-\check{v}^1|$, etc.
+\end{enumerate}
+\end{enumerate}
+
+
+La fonction $d$ peut se formaliser comme suit:
+$$d(x,\check{x})=d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})+d_{\mathds{B}^\mathsf{N}}(e,\check{e}),$$
+où: % $p=\max \mathcal{P}$ and:
+\begin{itemize}
+\item $d_{\mathds{B}^\mathsf{N}}$ est la distance de Hamming,
+\item $\forall s=(u,v), \check{s}=(\check{u},\check{v}) \in \mathcal{S}_{\mathsf{N},\mathcal{P}}$,\newline 
+$$\begin{array}{rcl}
+ d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) &= &
+   \sum_{k=0}^\infty \dfrac{1}{10^{(k+1)p+kn\max{(\mathcal{P})}}} 
+   \bigg(|v^k - \check{v}^k|  \\
+   & & + \left| \sum_{l=0}^{v^k-1} 
+       \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{(l+1)n}} -
+       \sum_{l=0}^{\check{v}^k-1} 
+       \dfrac{\check{u}^{\sum_{m=0}^{k-1} \check{v}^m +l}}{ 10^{(l+1)n}} \right| \bigg)
+\end{array}
+$$ %\left| \sum_{l=0}^{v^k-1} \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{l}} - \sum_{l=0}^{\check{v}^k-1} \dfrac{\check{u}^{\sum_{m=0}^{k-1} \check{v}^m +l}}{ 10^{l}}\right|\right)}.$$
+\end{itemize}
+
+
+
+\begin{xpl}
+On considère par exemple 
+$\mathsf{N}=13$, $\mathcal{P}=\{1,2,11\}$ ($\mathsf{p}$ vaut ainsi $3$), 
+et 
+$s=\left\{
+\begin{array}{l}
+u=\underline{6,} ~ \underline{11,5}, ...\\
+v=1,2,...
+\end{array}
+\right.$
+avec 
+$\check{s}=\left\{
+\begin{array}{l}
+\check{u}=\underline{6,4} ~ \underline{1}, ...\\
+\check{v}=2,1,...
+\end{array}
+\right.$.
+Ainsi 
+\[
+d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 
+0.01~0004000000000000000000~01~1005 \dots\]
+En effet, les $p=2$ premiers éléments sont  01, c'est-à-dire 
+$|v^0-\check{v}^0|=1$, 
+et on utilise $p$ éléments pour représenter cette différence
+(Comme $\mathcal{P}=\{1,2,11\}$, cette différence peut valoir 10).
+On prend alors le $v^0=1$ premier terme de $u$, 
+chaque terme étant codé sur $n=2$ éléments, soit 06.
+Comme on itère au plus $\max{(\mathcal{P})}$ fois, 
+on complète cette valeur par des 0 de sorte que 
+la chaîne obtenue ait $n\times \max{(\mathcal{P})}=22$ éléments, soit:
+0600000000000000000000. 
+De manière similaire, les $\check{v}^0=2$ premiers
+termes de $\check{u}$ sont représentés par 
+0604000000000000000000.
+La valeur absolue de leur différence est égale à 
+0004000000000000000000.
+Ces éléments sont concaténés avec 01. On peut construire alors le reste de 
+la séquence.
+\end{xpl}
+
+
+% \begin{xpl}
+% On considère à présent que  $\mathsf{N}=9$, que $\mathcal{P}=\{2,7\}$ et que
+% $$s=\left\{
+% \begin{array}{l}
+% u=\underline{6,7,} ~ \underline{4,2,} ...\\
+% v=2,2,...
+% \end{array}
+% \right.$$
+% avec
+% $$\check{s}=\left\{
+% \begin{array}{l}
+% \check{u}=\underline{4, 9, 6, 3, 6, 6, 7,} ~ \underline{9, 8}, ...\\
+% \check{v}=7,2,...
+% \end{array}
+% \right.
+% $$
+
+% Ainsi $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.5173633305600000...$, 
+% puisque 
+% $|v^0-\check{v}^0|=5$, $|4963667-6700000| = 1736333$, $|v^1-\check{v}^1|=0$,
+% et $|9800000-4200000| = 5600000$.
+% \end{xpl}
+
+
+
+On a la proposition suivante, qui est démontrée en annexe~\ref{anx:generateur}.
+
+
+\begin{restatable}[Une distance dans $\mathcal{X}_{\mathsf{N},\mathcal{P}}$]{theorem}{distancedsxnp}
+$d$ est une distance sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$.
+\end{restatable}
+
+
+\subsection{Le graphe $\textsc{giu}_{\mathcal{P}}(f)$ étendant  $\textsc{giu}(f)$}
+
+A partir de  $\mathcal{P}=\{p_1, p_2, \hdots, p_\mathsf{p}\}$, on 
+définit le graphe orienté $\textsc{giu}_{\mathcal{P}}(f)$ de la manière suivante:
+\begin{itemize}
+\item les n{\oe}uds sont les  $2^\mathsf{N}$ configurations de $\mathds{B}^\mathsf{N}$,
+%\item Each vertex has $\displaystyle{\sum_{i=1}^\mathsf{p} \mathsf{N}^{p_i}}$ arrows, namely all the $p_1, p_2, \hdots, p_\mathsf{p}$ tuples 
+%  having their elements in $\llbracket 1, \mathsf{N} \rrbracket $.
+\item il y a un arc libellé $u_0, \hdots, u_{p_i-1}$, $i \in \llbracket 1, \mathsf{p} \rrbracket$ entre les n{\oe}uds $x$ et $y$ si et seulement si $p_i$ est un élément de 
+$\mathcal{P}$ (\textit{i.e.}, on peut itérer $p_i$ fois), et pour chaque 
+$k$, $0 \le k \le p_i-1$, on a 
+ $u_k$ qui appartient à  $[\mathsf{N}]$ et 
+$y=F_{f_u,p_i} (x, (u_0, \hdots, u_{p_i-1})) $.
+\end{itemize}
+Il n'est pas difficile de constater que $\textsc{giu}_{\{1\}}(f)$ est $\textsc{giu}(f)$.
+
+
+
+
+
+\begin{figure}%[t]
+  \begin{center}
+    \subfigure[$\textsc{giu}_{\{2\}}(h)$]{
+      \begin{minipage}{0.30\textwidth}
+        \begin{center}
+          \includegraphics[scale=0.5]{images/h2prng}
+        \end{center}
+      \end{minipage}
+      \label{fig:h2prng}
+    }
+    \subfigure[$\textsc{giu}_{\{3\}}(h)$]{
+      \begin{minipage}{0.40\textwidth}
+        \begin{center}
+          \includegraphics[scale=0.5]{images/h3prng}
+        \end{center}
+      \end{minipage}
+      \label{fig:h3prng}
+    }
+    \subfigure[$\textsc{giu}_{\{2,3\}}(h)$]{
+      \begin{minipage}{0.40\textwidth}
+        \begin{center}
+          \includegraphics[scale=0.5]{images/h23prng}
+        \end{center}
+      \end{minipage}
+      \label{fig:h23prng}
+    }
+
+    \end{center}
+    \caption{Graphes d'itérations $\textsc{giu}_{\mathcal{P}}(h)$ pour $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$}
+    %\label{fig:xplgraphIter}
+  \end{figure}
+
+
+
+
+\begin{xpl}
+On reprend l'exemple où $\mathsf{N}=2$ et 
+$h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$ déjà détaillé 
+à la section~\ref{sub:prng:unif}.
+
+Le graphe $\textsc{giu}_{\{1\}}(h)$ a déjà été donné à la figure~\ref{fig:h:iter}.
+Les graphes $\textsc{giu}_{\{2\}}(h)$, $\textsc{giu}_{\{3\}}(h)$  et
+$\textsc{giu}_{\{2,3\}}(h)$ sont respectivement donnés aux figures~\ref{fig:h2prng}, ~\ref{fig:h3prng} et ~\ref{fig:h23prng}. 
+Le premier (respectivement le second) 
+illustre le comportement du générateur lorsque qu'on itère exactement 
+2 fois (resp. 3 fois) puis qu'on affiche le résultat.
+Le dernier donnerait le comportement d'un générateur qui s'autoriserait 
+à itérer en interne systématiquement 2 ou 3 fois avant de retourner un résultat.
+
+\end{xpl}
+
+
+\subsection{le PRNG de l'algorithme~\ref{CI Algorithm} est chaotique sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$}
+
+Le théorème suivant, similaire à ceux dans $\mathcal{X}_u$ et dans $\mathcal{X}_g$
+est prouvé en annexe~\ref{anx:generateur}.
+
+\begin{restatable}[Conditions pour la chaoticité de $G_{f_u,\mathcal{P}}$]{theorem}{thmchoticitgfp}
+La fonction $G_{f_u,\mathcal{P}}$ est chaotique sur 
+ $(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$ si et seulement si 
+le graphe d'itérations $\textsc{giu}_{\mathcal{P}}(f)$ 
+est fortement connexe.
+\end{restatable}
+% On alors corollaire suivant 
+
+% \begin{corollary}
+%   Le générateur de nombre pseudo aléatoire détaillé 
+%   à l'algorithme~\ref{CI Algorithm}
+%   n'est pas chaotique 
+%   sur $(\mathcal{X}_{\mathsf{N},\{b\}},d)$ pour la fonction négation.
+% \end{corollary}
+% \begin{proof}
+%   Dans cet algorithme, $\mathcal{P}$ est le singleton $\{b\}$.
+%   Que $b$ soit pair ou impair,  $\textsc{giu}_{\{b\}}(f)$
+%   n'est pas fortement connexe.
+% \end{proof}
+
+
+
+
+\section{Conclusion}
+Ce chapitre a proposé un algorithme permettant de construire un 
+PRNG chaotique à partir d'un PRNG existant. Pour ce faire, il est nécessaire 
+et suffisant que la fonction $f$ qui est itérée un nombre $b$ de fois 
+possède un $\textsc{giu}_{\{b\}}(f)$ fortement connexe et que sa matrice de Markov associée soit doublement stochastique.
+Le chapitre suivant montre comment construire une telle fonction.
+
+ 
+