X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/22c2a9bec00707660df698103219bde5268c6ef3..8defa47ac283c6ce000d76eba1c1ad62b4a8bd38:/15RairoGen.tex?ds=inline diff --git a/15RairoGen.tex b/15RairoGen.tex index 0519ecb..f2b9243 100644 --- a/15RairoGen.tex +++ b/15RairoGen.tex @@ -1 +1,461 @@ - \ No newline at end of file +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} + + +