X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/d69000ebda300fc836232f34cebb88ddfce4ac98..75aa438e61284f634375e2c1e62c79f2af12678f:/15RairoGen.tex diff --git a/15RairoGen.tex b/15RairoGen.tex index a950d85..06f84b1 100644 --- a/15RairoGen.tex +++ b/15RairoGen.tex @@ -5,15 +5,17 @@ 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 + +Ce chapitre présente une application directe +de la théorie développée ci-avant +à la génération de nombres pseudo aléatoires. + + 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 @@ -33,16 +35,15 @@ L'approche est évaluée dans la dernière section. \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)} +une configuration initiale $x^0$ (${\mathsf{N}}$ bits)} +\KwOut{une configuration $x$ (${\mathsf{N}}$ bits)} $x\leftarrow x^0$\; -$k\leftarrow b $\; %$k\leftarrow b + \textit{XORshift}(b+1)$\; -\For{$i=1,\dots,k$} +\For{$i=1,\dots,b$} { -$s\leftarrow{\textit{Random}(n)}$\; +$s\leftarrow{\textit{Random}({\mathsf{N}})}$\; %$s\leftarrow{\textit{XORshift}(n)}$\; -$x\leftarrow{F_{f_u}(s,x)}$\; +$x\leftarrow{F_{f_u}(x,s)}$\; } return $x$\; %\end{scriptsize} @@ -56,11 +57,11 @@ 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$) +un entier $b$, qui est le nombre d'itérations à effectuer entre deux sorties 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 +la fonction $F_{f_u}$ (équation~\ref{eq:iterations:unaires} +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. @@ -105,10 +106,13 @@ Notre approche vise a donner des propriétés de chaos a ce générateur embarqu 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. +est 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. + +Pour simuler au mieux l'aléa, un bon générateur de nombre pseudo-aléatoires +se doit de fournir des nombres selon une distribution uniforme. +Regardons comment l'uniformité de la distribution +contraint la fonction $f$ à itérer. \subsection{Un générateur à sortie uniformément distribuée}\label{sub:prng:unif} @@ -121,7 +125,7 @@ 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 +On énonce le théorème classique suivant liant les vecteur de probabilités et les chaînes de Markov. @@ -316,10 +320,12 @@ On énonce directement le théorème suivant dont la preuve est donnée en annex \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. +On considère le graphe d'interactions $\Gamma(f)$ donné +en figure~\ref{fig:G}. C'est le même qui a été présenté +à la section~\ref{sec:11FCT}. +On a vu qu'il y avait 520 fonctions $f$ non isomorphes de graphe d'interactions $\Gamma(f)$. +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. @@ -343,11 +349,11 @@ ce vecteur au vecteur $\pi=(\frac{1}{2^n},\ldots,\frac{1}{2^n})$ Ainsi, on a \begin{equation} b = \max\limits_{i \in \llbracket 1, 2^n \rrbracket} -\{ -\min \{ +\left\{ +\min \left\{ t \mid t \in \Nats, \vectornorm{e_i M_f^t - \pi} < 10^{-4} -\} -\}. +\right\} +\right\}. \label{eq:mt:ex} \end{equation} @@ -444,7 +450,7 @@ Ceci est difficilement compatible avec la volonté d'avoir une sortie uniformém 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 +Montrer que les sous-séquences de suites chaotiques ainsi générées demeurent chaotiques est l'objectif de la section suivante. @@ -464,15 +470,14 @@ 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} +$F_{{f_u},p_i} : \mathds{B}^\mathsf{N} \times [\mathsf{N}]^{p_i} \rightarrow \mathds{B}^\mathsf{N}$ définie par $$ @@ -484,11 +489,11 @@ $$ 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 +[\mathsf{N}]^{\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. +Le second élément est 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$). @@ -529,7 +534,7 @@ 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} +\begin{enumerate} \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 @@ -544,7 +549,7 @@ $\check{u}^{\check{v}^0}, \check{u}^{\check{v}^0+1}, \hdots, \check{u}^{\check{v 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} +\begin{enumerate} \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 @@ -552,7 +557,7 @@ $n = \lfloor \log_{10}{(\mathsf{N})}\rfloor +1$. $\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} +\begin{enumerate} \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 @@ -563,10 +568,10 @@ $p+n\times \max{(\mathcal{P})}$ éléments. é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} +\end{enumerate} \item Les $p$ suivants sont $|v^1-\check{v}^1|$, etc. -\end{itemize} -\end{itemize} +\end{enumerate} +\end{enumerate} La fonction $d$ peut se formaliser comme suit: @@ -606,8 +611,10 @@ $\check{s}=\left\{ \check{v}=2,1,... \end{array} \right.$. - -Ainsi $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.010004000000000000000000011005 ...$ +Ainsi +\[ +d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = +0.01~0004000000000000000000~01~1005 \dots\] 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 @@ -621,35 +628,35 @@ la chaîne obtenue a $n\times \max{(\mathcal{P})}=22$ éléments, soit: 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 à +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. -$$ +% \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} +% 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} @@ -668,8 +675,9 @@ définit le graphe orienté $\textsc{giu}_{\mathcal{P}}(f)$ de la manière suiva %\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 +$\mathcal{P}$ (\textit{i.e.}, on peut itérer $p_i$ fois), et pour chaque +$k$, $0 \le k \le p_i-1$, on a + $u_k$ qui apaprtient à $[\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)$. @@ -683,7 +691,7 @@ Il n'est pas difficile de constater que $\textsc{giu}_{\{1\}}(f)$ est $\textsc{g \subfigure[$\textsc{giu}_{\{2\}}(h)$]{ \begin{minipage}{0.30\textwidth} \begin{center} - \includegraphics[height=4cm]{images/h2prng} + \includegraphics[scale=0.5]{images/h2prng} \end{center} \end{minipage} \label{fig:h2prng} @@ -691,7 +699,7 @@ Il n'est pas difficile de constater que $\textsc{giu}_{\{1\}}(f)$ est $\textsc{g \subfigure[$\textsc{giu}_{\{3\}}(h)$]{ \begin{minipage}{0.40\textwidth} \begin{center} - \includegraphics[height=4cm]{images/h3prng} + \includegraphics[scale=0.5]{images/h3prng} \end{center} \end{minipage} \label{fig:h3prng} @@ -699,7 +707,7 @@ Il n'est pas difficile de constater que $\textsc{giu}_{\{1\}}(f)$ est $\textsc{g \subfigure[$\textsc{giu}_{\{2,3\}}(h)$]{ \begin{minipage}{0.40\textwidth} \begin{center} - \includegraphics[height=4cm]{images/h23prng} + \includegraphics[scale=0.5]{images/h23prng} \end{center} \end{minipage} \label{fig:h23prng} @@ -732,7 +740,7 @@ Le dernier donnerait le comportement d'un générateur qui s'autoriserait \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$ +Le théorème suivant, similaire à ceux dans $\mathcal{X}_u$ et dans $\mathcal{X}_g$ est prouvé en annexes~\ref{anx:generateur}. \begin{theorem} @@ -751,7 +759,7 @@ On alors corollaire suivant \end{corollary} \begin{proof} Dans cet algorithme, $\mathcal{P}$ est le singleton $\{b\}$. - Que $b$ soit pair ou impair, $\textsc{giu}_{\mathcal{b}}(f)$ + Que $b$ soit pair ou impair, $\textsc{giu}_{\{b\}}(f)$ n'est pas fortement connexe. \end{proof}