resumes retraités

[hdrcouchot.git] / 15RairoGen.tex

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,  
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.
 

René Lozi a aussi étudié la construction de PRNGs en couplant 
des suites de Lozi~\cite{espinelrojas:hal-00622989} (qui sont une variation des suites de Hénon: $x^2_t$ est remplacé par $| x_t|$),
la suite tente~\cite{DBLP:journals/ijbc/Lozi12} et en extrayant des 
sous-suites pour construire la sortie du PRNG~\cite{lozi:hal-00813087}. 
 
 


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^{\mathsf{N}} \rightarrow \Bool^{\mathsf{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}{\mathsf{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^{\mathsf{N}}}$. 
Chacun des éléments $v_j$, $1 \le j \le 2^{\mathsf{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^{\mathsf{N}}},\ldots,\frac{1}{2^{\mathsf{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^{\mathsf{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}))  = 
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^{\mathsf{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.