X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/d3ea167453c701385858e4db6c3dcd9df216701d..8defa47ac283c6ce000d76eba1c1ad62b4a8bd38:/15RairoGen.tex?ds=sidebyside diff --git a/15RairoGen.tex b/15RairoGen.tex index 3c49eb6..f2b9243 100644 --- a/15RairoGen.tex +++ b/15RairoGen.tex @@ -1,99 +1,27 @@ -Pour décrire un peu plus précisément le principe de -la génération pseudo-aléatoire, considérons l'espace booléen -$\Bool=\{0,1\}$ -muni des lois \og +\fg{}, \og . \fg{} et \og $\overline{\mathstrut\enskip}$ \fg{} -définies par les tableaux ci-dessous: - -\begin{minipage}{0.33\textwidth} - \begin{center} - \begin{tabular}{|c|c|c|} - \hline - + & 0& 1 \\ - \hline - 0 & 0& 1 \\ - \hline - 1 & 1& 1 \\ - \hline - \end{tabular} -\end{center} -\end{minipage} -\begin{minipage}{0.33\textwidth} - \begin{center} - \begin{tabular}{|c|c|c|} - \hline - . & 0& 1 \\ - \hline - 0 & 0& 0 \\ - \hline - 1 & 0& 1 \\ - \hline - \end{tabular} -\end{center} -\end{minipage} -\begin{minipage}{0.32\textwidth} - \begin{center} - \begin{tabular}{|c|c|c|} - \hline - & 0& 1 \\ - \hline - $\overline{\mathstrut\enskip}$ & 1& 0 \\ - \hline - \end{tabular} -\end{center} -\end{minipage} - - -La fonction itérée est -une fonction $f$ de $\Bool^n$ dans lui-même qui à -un mot binaire $x = (x_1,\ldots,x_n)$ -associe le mot $(f_1(x),\ldots, f_n(x))$. -Un exemple de fonction de $\Bool^n$ dans lui-même -est la fonction négation -définie par -$\neg(x)=(\overline{x_1},\dots,\overline{x_n})$. - -Le principe itératif est le suivant: -à chaque itération $t$, on choisit un indice $i$ entre $1$ et $n$, -et le mot $x^t = (x_1^t,\ldots,x_n^t)$ est remplacé par -$x^{t+1} = (x_1^t,\ldots , x_{i-1}^t, f_i(x^t), x_{i+1}^t,\ldots, x_n^t)$. - -Au bout d'un nombre $N$ d'itérations, -si la fonction, notée $G_f$ dans ce document, -que l'on peut associer à l'algorithme décrit ci-dessus +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^N$ doit être \og très différent\fg{} de $x^0$ -de façon à même sembler ne plus dépendre de $x_0$: -pour un générateur aléatoire, il faut que la structure de -$x^N$ semble être due au hasard; -pour une application cryptographique, il faut qu'il -soit matériellement impossible (dans les conditions techniques actuelles) -de retrouver $x^0$ à partir de $x^N$. - -Tous les mots de -$\Bool^n$ peuvent constituer les -$2^n$ sommets d'un \gls{graphoriente} (cf. glossaire) -dans lequel un arc relie deux sommets $x$ et $x'$ -s'il existe une itération de l'algorithme -de génération qui permet de passer de $x$ à $x'$. -Ce graphe est appelé le graphe d'itérations et -ce document montre que si l'on a un \gls{graphfortementconnexe} (cf. glossaire), -alors la fonction $G_f$ est transitive, donc chaotique. - +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 \gls{distributionuniforme} (cf. glossaire). -La dernière partie de ce document donnera, +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 +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 +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} @@ -137,20 +65,20 @@ de nombres pseudo aléatoires 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 +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 \gls{xor}\fg{} $\oplus$ (cf. glossaire) -% sur des nombres obtenus grâce à des \glspl{decalageDeBits} (cf. glossaire). +% 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 \glspl{decalageDeBits} (cf. glossaire). +sur des nombres obtenus grâce à des decalages de bits. Cet opérateur, défini dans $\Bool^{n}$, -applique la fonction \og \gls{xor} \fg{} (cf. glossaire) +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. @@ -190,8 +118,8 @@ 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): +vecteurDeProbabilite +et les chaineDeMarkov: @@ -199,11 +127,11 @@ et les \glspl{chaineDeMarkov} (cf. glossaire): 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} + 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 \gls{chaineDeMarkov} $\pi^k$ + alors la {chaineDeMarkov} $\pi^k$ converge vers $\pi$ lorsque $k$ tend vers l'infini. \end{Theo} @@ -231,10 +159,10 @@ 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) +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 \gls{matriceDAdjacence} (cf. glossaire) donnée en +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]