15

[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 {distributionuniforme} 
La suite de ce document donnera, 
dans le cas où le graphe d'itérations est fortement connexe, 
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 distributionuniforme
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}
 

\subsection{ Générateur de nombres pseudo aléatoires basé sur le chaos}\label{sub:prng:algo}





On peut penser à construire un générateur de nombres pseudo 
aléatoires comme dans l'algorithme~\ref{CI Algorithm} donné ci-dessous.

\begin{algorithm}[h]
%\begin{scriptsize}
\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 + \textit{Random}(b+1)$\;
%$k\leftarrow b + \textit{XORshift}(b+1)$\;
\For{$i=0,\dots,k-1$}
{
$s\leftarrow{\textit{Random}(n)}$\;
%$s\leftarrow{\textit{XORshift}(n)}$\;
$x\leftarrow{F_f(s,x)}$\;
}
return $x$\;
%\end{scriptsize}
\caption{Algorithme de génération de nombres pseudo aléatoires 
à l'aide de la fonction chaotique $G_f$}
\label{CI Algorithm}
\end{algorithm}


Celui-ci prend en entrée: une fonction $f$;
un entier $b$, qui assure que le nombre d'itérations
est compris entre $b+1 $ et  $2b+1$ et une configuration initiale $x^0$.
Il retourne une nouvelle configuration $x$.
En interne, il exploite un algorithme de génération
de nombres pseudo aléatoires
\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 distributionuniforme et utilise 
\textit{XORshift} qui est une classe de générateurs de
nombres pseudo aléatoires
très rapides conçus par George Marsaglia. 

% L'algorithme \textit{XORshift} exploite itérativement
% la fonction \og {xor}\fg{} $\oplus$ (cf. glossaire) 
% sur des nombres obtenus grâce à des pl{decalageDeBits} (cf. glossaire).

L'algorithme \textit{XORshift} 
exploite itérativement l'opérateur $\oplus$  
sur des nombres obtenus grâce à des decalages 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}



Il reste à instancier une fonction $f$ dans 
l'algorithme~\ref{CI Algorithm} 
en adéquation avec  l'approche développée 
en section~\ref{sec:sccg}.
La section suivante montre comment l'uniformité de la distribution a
contraint cette instanciation.

\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 
vecteurDeProbabilite 
et les chaineDeMarkov:


 
\begin{Theo}\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 {vecteurDeProbabilite} 
 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 {chaineDeMarkov} $\pi^k$
  converge vers $\pi$ lorsque $k$ tend vers l'infini.
\end{Theo}


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 a pu déjà 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$.


Comme le générateur \textit{Random} possède une sortie uniformément 
distribuée,  la  stratégie est uniforme sur $\llbracket 1, 2 \rrbracket$,
et donc, 
pour tout sommet de $\Gamma(g)$ et de  $\Gamma(h)$,
chaque arc sortant de ce sommet a, parmi l'ensemble des arcs sortant 
de ce sommet, une probabilité $1/2$ d’être celui qui sera traversé.
En d'autres mots, $\Gamma(g)$ est le graphe orienté d'une chaîne de Markov.
Il est facile de vérifier que la {matriceDeTransitions}
d'un tel processus 
est $M_g   = \frac{1}{2} \check{M}_g$, 
où $\check{M}_g$ est la {matriceDAdjacence}  donnée en 
figure~\ref{fig:g:incidence} (voir ci-après), et similairement pour $M_h$. 

\begin{figure}[h]
  \begin{center}
    \subfloat[$\check{M}_g $.]{
      \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}
    }
    \subfloat[$\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.


Considérons le lemme technique suivant:
\begin{Lemma}\label{lem:stoc}
Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\Gamma(f)$ son graphe d'itérations, $\check{M}$ la matrice d'adjacence de $\Gamma(f)$, et  $M$  la matrice 
$2^n\times 2^n$  définie par
$M = \frac{1}{n}\check{M}$.
Alors $M$ est une matrice stochastique régulière si et seulement si
$\Gamma(f)$ est fortement connexe.
\end{Lemma}

\begin{Proof}  
On remarque tout d'abord que $M$ 
est une matrice stochastique par construction.
Supposons $M$ régulière. 
Il existe donc  $k$ tel que $M_{ij}^k>0$ pour chaque $i,j\in \llbracket
1;  2^n  \rrbracket$. L'inégalité  $\check{M}_{ij}^k>0$  est alors établie.
Puisque $\check{M}_{ij}^k$ est le nombre de chemins de  $i$ à $j$ de longueur $k$
dans $\Gamma(f)$ et puisque ce nombre est positif, alors 
$\Gamma(f)$ est fortement connexe.

Réciproquement si $\Gamma(f)$ 
est fortement connexe, alors pour tous les sommets $i$ et $j$, un chemin peut être construit pour atteindre  $j$  depuis $i$ en au plus $2^n$ étapes.
Il existe donc 
$k_{ij} \in \llbracket 1,  2^n \rrbracket$ tels que $\check{M}_{ij}^{k_{ij}}>0$.  
Comme tous les  multiples $l \times k_{ij}$ de $k_{ij}$ sont tels que 
$\check{M}_{ij}^{l\times  k_{ij}}>0$, 
on peut conclure que, si 
$k$ est le plus petit multiple commun de $\{k_{ij}  \big/ i,j  \in \llbracket 1,  2^n \rrbracket  \}$ alors
$\forall i,j  \in \llbracket  1, 2^n \rrbracket,  \check{M}_{ij}^{k}>0$. 
Ainsi, $\check{M}$ et donc $M$ sont régulières.
\end{Proof}

Ces résultats permettent formuler et de prouver le théorème suivant:

\begin{Theo}
  Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\Gamma(f)$ son 
  graphe d'itérations , $\check{M}$ sa matrice d'adjacence
  et $M$ une matrice  $2^n\times 2^n$  définie comme dans le lemme précédent.
  Si $\Gamma(f)$ est fortement connexe, alors 
  la sortie du générateur de nombres pseudo aléatoires détaillé par 
  l'algorithme~\ref{CI Algorithm} suit une loi qui 
  tend vers la distribution uniforme si 
  et seulement si  $M$ est une matrice doublement stochastique.
\end{Theo}
\begin{Proof}
  $M$ est une matrice stochastique régulière (Lemme~\ref{lem:stoc}) 
  qui a un unique vecteur de probabilités stationnaire
  (Théorème \ref{th}).
  Soit $\pi$  défini par 
  $\pi = \left(\frac{1}{2^n}, \hdots, \frac{1}{2^n} \right)$.
  On a  $\pi M = \pi$ si et seulement si
  la somme des valeurs de chaque colonne de $M$  est 1, 
  \textit{i.e.} si et seulement si 
  $M$ est  doublement  stochastique.
\end{Proof}


\subsection{Expérimentations}

On considère le graphe d'interactions $G(f)$ donné en figure~\ref{fig:G}. 
Il vérifie le théorème~\ref{th:Adrien}: 
toutes les fonctions $f$ possédant un tel graphe d'interactions
ont un graphe d'itérations  $\Gamma(f)$ fortement connexe.
Pratiquement, un algorithme simple de satisfaction de contraintes
a trouvé  520 fonctions $f$ non isomorphes de graphe d'interactions  $G(f)$, 
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é à $\Gamma(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 
$$
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}
\}
\}. 
$$

\begin{figure}%[h]
  \begin{center}
  \subfloat[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
  \subfloat[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).
% Pour les 15 tests, le seuil $\alpha$ est fixé à $1\%$:
% une  valeur  
% qui est plus grande que $1\%$  signifie 
% que la chaîne est considérée comme aléatoire avec une confiance de $99\%$.
% Le tableau~\ref{fig:TEST} donne une vision synthétique de toutes 
% les expérimentations. 
L'expérience a montré notamment que toutes ces fonctions
passent avec succès cette batterie de tests.




% \begin{table}[th]
% \begin{scriptsize}
% \begin{tabular}{|*{17}{c|}}
% \hline
% {Propriété}& $\mathcal{F}_{1}$ &$\mathcal{F}_{2}$ &$\mathcal{F}_{3}$ &$\mathcal{F}_{4}$ &$\mathcal{F}_{5}$ &$\mathcal{F}_{6}$ &$\mathcal{F}_{7}$ &$\mathcal{F}_{8}$ &$\mathcal{F}_{9}$ &$\mathcal{F}_{10}$ &$\mathcal{F}_{11}$ &$\mathcal{F}_{12}$ &$\mathcal{F}_{13}$ &$\mathcal{F}_{14}$ &$\mathcal{F}_{15}$ &$\mathcal{F}_{16}$ \\
% \hline
% Fréquence &77.9 &15.4 &83.4 &59.6 &16.3 &38.4 &20.2 &29.0 &77.9 &21.3 &65.8 &85.1 &51.4 &35.0 &77.9 &92.4 \\ 
%  \hline 
% Fréquence / bloc &88.3 &36.7 &43.7 &81.7 &79.8 &5.9 &19.2 &2.7 &98.8 &1.0 &21.3 &63.7 &1.4 &7.6 &99.1 &33.5 \\ 
%  \hline 
% Somme cummulée &76.4 &86.6 &8.7 &66.7 &2.2 &52.6 &20.8 &80.4 &9.8 &54.0 &73.6 &80.1 &60.7 &79.7 &76.0 &44.7 \\ 
%  \hline 
% Exécution &5.2 &41.9 &59.6 &89.8 &23.7 &76.0 &77.9 &79.8 &45.6 &59.6 &89.8 &2.4 &96.4 &10.9 &72.0 &11.5 \\ 
%  \hline 
% Longue exécution &21.3 &93.6 &69.9 &23.7 &33.5 &30.4 &41.9 &43.7 &30.4 &17.2 &41.9 &51.4 &59.6 &65.8 &11.5 &61.6 \\ 
%  \hline 
% Rang &1.0 &41.9 &35.0 &45.6 &51.4 &20.2 &31.9 &83.4 &89.8 &38.4 &61.6 &4.0 &21.3 &69.9 &47.5 &95.6 \\ 
%  \hline 
% Fourrier Rapide &40.1 &92.4 &97.8 &86.8 &43.7 &38.4 &76.0 &57.5 &36.7 &35.0 &55.4 &57.5 &86.8 &76.0 &31.9 &7.6 \\ 
%  \hline 
% Sans superposition &49.0 &45.7 &50.5 &51.0 &48.8 &51.2 &51.6 &50.9 &50.9 &48.8 &45.5 &47.3 &47.0 &49.2 &48.6 &46.4 \\ 
%  \hline 
% Avec Superposition &27.6 &10.9 &53.4 &61.6 &16.3 &2.7 &59.6 &94.6 &88.3 &55.4 &76.0 &23.7 &47.5 &91.1 &65.8 &81.7 \\ 
%  \hline 
% Universelle &24.9 &35.0 &72.0 &51.4 &20.2 &74.0 &40.1 &23.7 &9.1 &72.0 &4.9 &13.7 &14.5 &1.8 &93.6 &65.8 \\ 
%  \hline 
% Entropie approchée &33.5 &57.5 &65.8 &53.4 &26.2 &98.3 &53.4 &63.7 &38.4 &6.7 &53.4 &19.2 &20.2 &27.6 &67.9 &88.3 \\ 
%  \hline 
% Suite aléatoire &29.8 &35.7 &40.9 &36.3 &54.8 &50.8 &43.5 &46.0 &39.1 &40.8 &29.6 &42.0 &34.8 &33.8 &63.0 &46.3 \\ 
%  \hline 
% Suite aléatoire variante &32.2 &40.2 &23.0 &39.6 &47.5 &37.2 &56.9 &54.6 &53.3 &31.5 &23.0 &38.1 &52.3 &57.1 &47.7 &40.8 \\ 
%  \hline 
% Série &56.9 &58.5 &70.4 &73.2 &31.3 &45.9 &60.8 &39.9 &57.7 &21.2 &6.4 &15.6 &44.7 &31.4 &71.7 &49.1 \\ 
%  \hline 
% Complexité linéaire &24.9 &23.7 &96.4 &61.6 &83.4 &49.4 &49.4 &18.2 &3.5 &76.0 &24.9 &97.2 &38.4 &38.4 &1.1 &8.6 \\ 
%  \hline
% \end{tabular}
% \end{scriptsize}
% \caption{Test de NIST réalisé sur des instances de générateurs}\label{fig:TEST}  
% \end{table}