preuve promela traduite

[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. 
Enfin, un bon générateur aléatoire se doit de 
fournir  des nombres selon une distribution uniforme 
La suite de ce document donnera
une condition nécessaire est suffisante pour que
cette propriété soit satisfaite.


Cette section présente une application directe de la théorie développée ci-avant
à la génération de nombres pseudo aléatoires. 
On présente tout d'abord le générateur
basé sur des fonctions chaotiques (section~\ref{sub:prng:algo}), 
puis comment intégrer la contrainte de distribution uniforme
de la sortie 
dans le choix de la fonction à itérer (section~\ref{sub:prng:unif}). 
L'approche est évaluée dans la dernière section.
\JFC{plan à revoir}
 

\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$ ($n$ bits)}
\KwOut{une configuration $x$ ($n$ bits)}
$x\leftarrow x^0$\;
$k\leftarrow b $\;
%$k\leftarrow b + \textit{XORshift}(b+1)$\;
\For{$i=1,\dots,k$}
{
$s\leftarrow{\textit{Random}(n)}$\;
%$s\leftarrow{\textit{XORshift}(n)}$\;
$x\leftarrow{F_{f_u}(s,x)}$\;
}
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 assure que le nombre d'itérations
est compris entre $b+1 $ et  $2b+1$ (et donc supérieur à $b$) 
et une configuration initiale $x^0$.
Il retourne une nouvelle configuration $x$ en appliquant 
la fonction $F_{f_u}$ vue au chapitre~\ref{chap:carachaos} et correspondant 
à des itérations unaires.
En interne, il exploite un algorithme de génération
de nombres pseudo aléatoires 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)$ 
doit être fortement connexe.
Pour $b=1$, l'algorithme itère la fonction $F_{f_u}$.
Regardons comment l'uniformité de la distribution a
contraint la fonction.

\subsection{Un générateur à sortie uniformément distribuée}\label{sub:prng:unif}

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 enfin le théorème 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{theorem}\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{theorem}


\subsection{Quelques exemples}

On reprend le graphe d'interactions $\Gamma(f)$ donné en figure~\ref{fig:G} à la section~\ref{sec:11FCT}.
On a vu qu'il y avait  520 fonctions $f$ non isomorphes de graphe d'interactions  $\Gamma(f)$, 
dont seulement 16 d'entre elles possèdent une matrice doublement stochastique.

La figure~\ref{fig:listfonction} explicite ces 16 fonctions en 
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} 
\{
\min \{
 t \mid t \in \Nats, \vectornorm{e_i M_f^t - \pi} < 10^{-4}
\}
\}. 
\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 les sous-séquences de suites chaotiques ainsi générées  demeurent chaotiques
est l'objectif de la section suivante.


\section{Un PRNG basé sur des itérations unaires qui est chaotique }

Cette section présente un espace métrique adapté au générateur de nombres pseudo-aléatoires 
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 \llbracket 1, \mathsf{N} \rrbracket^{p_i}
\rightarrow \mathds{B}^\mathsf{N}$ définie par

$$
F_{f_u,p_i} (x,(u^0, u^1, \hdots, u^{p_i-1}))  \mapsto 
F_{f_u}(\hdots (F_{f_u}(F_{f_u}(x,u^0), u^1), \hdots), u^{p_i-1}).
$$


on construit l'espace 
 $\mathcal{X}_{\mathsf{N},\mathcal{P}}=  \mathds{B}^\mathsf{N} \times \mathds{S}_{\mathsf{N},\mathcal{P}}$, où
$\mathds{S}_{\mathsf{N},\mathcal{P}}=
\llbracket 1, \mathsf{N} \rrbracket^{\Nats}\times 
\mathcal{P}^{\Nats}$. 
Chaque élément de l'espace est une paire où le premier élément est 
un $\mathsf{N}$-uplet de  $\Bool^{\mathsf{N}}$ (comme dans $\mathcal{X}_u$).
Le second élément est aussi une paire $((u^k)_{k \in \Nats},(v^k)_{k \in \Nats})$ de suites infinies.
La suite $(v^k)_{k \in \Nats}$ définit combien d'itérations sont exécutées au temps $k$ entre deux sorties.
La séquence $(u^k)_{k \in \Nats}$ définit quel élément est modifié (toujours au temps $k$).

Définissons la fonction de dé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{itemize}
\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{itemize}
\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{itemize}
\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{itemize}
\item Les $p$ suivants sont $|v^1-\check{v}^1|$, etc.
\end{itemize}
\end{itemize}


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.010004000000000000000000011005 ...$
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{lemma}
$d$ est une distance sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$.
\end{lemma}


\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), 
chaque $u_k$ de la suite 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[height=4cm]{images/h2prng}
        \end{center}
      \end{minipage}
      \label{fig:h2prng}
    }
    \subfigure[$\textsc{giu}_{\{3\}}(h)$]{
      \begin{minipage}{0.40\textwidth}
        \begin{center}
          \includegraphics[height=4cm]{images/h3prng}
        \end{center}
      \end{minipage}
      \label{fig:h3prng}
    }
    \subfigure[$\textsc{giu}_{\{2,3\}}(h)$]{
      \begin{minipage}{0.40\textwidth}
        \begin{center}
          \includegraphics[height=4cm]{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 à celui dans $\mathcal{X}_u$ et dans $\mathcal{X}_g$
est prouvé en annexes~\ref{anx:generateur}.

\begin{theorem}
La fonction $G_{f_u,\mathcal{P}}$ est chaotique sur 
 $(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$ si et seulement si 
graphe d'itération $\textsc{giu}_{\mathcal{P}}(f)$ 
est fortement connexe.
\end{theorem}
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}_{\mathcal{b}}(f)$
  n'est pas fortement connexe.
\end{proof}