-
\ No newline at end of file
+ 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 \gls{distributionuniforme}
+(cf. glossaire) 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.
+
+
+\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 \gls{distributionuniforme} (cf. glossaire) 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 \gls{xor}\fg{} $\oplus$ (cf. glossaire)
+% sur des nombres obtenus grâce à des \glspl{decalageDeBits} (cf. glossaire).
+
+L'algorithme \textit{XORshift}
+exploite itérativement l'opérateur $\oplus$
+sur des nombres obtenus grâce à des \glspl{decalageDeBits} (cf. glossaire).
+Cet opérateur, défini dans $\Bool^{n}$,
+applique la fonction \og \gls{xor} \fg{} (cf. glossaire)
+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
+\glspl{vecteurDeProbabilite} (cf. glossaire)
+et les \glspl{chaineDeMarkov} (cf. glossaire):
+
+
+
+\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 \gls{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 \gls{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 \gls{matriceDeTransitions} (cf. glossaire)
+d'un tel processus
+est $M_g = \frac{1}{2} \check{M}_g$,
+où $\check{M}_g$ est la \gls{matriceDAdjacence} (cf. glossaire) 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}
+
+
+
