relecture

[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{sub:prng:algo} 
présente tout d'abord l'algorithme de PRNG. La contrainte de  
distribution uniforme de la sortie est discutée dans cette section.
La chaoticité du générateur est ensuite étudiée en 
section~\ref{prng:unaire:chaos}.
La section~\ref{sub:prng:algo}  a été publiée à ~\cite{bcgw11:ip,bcgr11:ip}.


\section{ Nombres pseudo aléatoires construits par itérations unaires}\label{sub:prng:algo}






\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 a 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 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 nombre 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 
vecteur 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.
Soit 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é à $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 annexes~\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 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}}$ sur 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), suivi 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 a $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 annexes~\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 figure~\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 trois 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 annexes~\ref{anx:generateur}.

\begin{restatable}[Conditions pour la choticité 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ération $\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.