X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/103fee06d77ee199f8956ccb0747b45676c834e5..d33e664452e3655370cbe069e3f6fbd16842c818:/15RairoGen.tex?ds=sidebyside diff --git a/15RairoGen.tex b/15RairoGen.tex index fe1c034..a57e19f 100644 --- a/15RairoGen.tex +++ b/15RairoGen.tex @@ -5,23 +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 -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 +Ce chapitre présente donc 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 -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} - +La section~\ref{sub:prng:algo} +présente tout d'abord l'algorithme de PRNG. La contrainte de +distribution uniforme de la sortie est discutée dans cette section. +La chaoticité du générateur est ensuite étudiée en +section~\ref{prng:unaire:chaos}. +La section~\ref{sub:prng:algo} a été publiée à ~\cite{bcgw11:ip,bcgr11:ip}. + \section{ Nombres pseudo aléatoires construits par itérations unaires}\label{sub:prng:algo} @@ -33,21 +27,19 @@ 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} -\caption{Algorithme de génération de nombres pseudo aléatoires -à l'aide de la fonction chaotique $G_f$} +\caption{PRNG basé sur les itérations unaires.} \label{CI Algorithm} \end{algorithm} @@ -57,54 +49,62 @@ 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 -\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 distribution uniforme et utilise -\textit{XORshift} qui est une classe de générateurs de -nombres pseudo aléatoires conçus par George Marsaglia. - - -L'algorithme \textit{XORshift} -exploite itérativement l'opérateur $\oplus$ -sur des nombres obtenus grâce à des décalages 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} +de nombres pseudo aléatoires donné en paramètre. +Cela peut être n'importe quel PRNG (XORshift, Mersenne-Twister) dont la +sortie est uniformément distribuée. +Notre approche vise a donner des propriétés de chaos à ce générateur embarqué. + + +% \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 distribution uniforme et utilise +% \textit{XORshift} qui est une classe de générateurs de +% nombres pseudo aléatoires conçus par George Marsaglia. + + +% L'algorithme \textit{XORshift} +% exploite itérativement l'opérateur $\oplus$ +% sur des nombres obtenus grâce à des décalages 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} 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. +si et seulement si le graphe d'itérations $\textsc{giu}(f)$ +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 nombres 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} @@ -117,8 +117,8 @@ 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 -vecteur de probabilités +On énonce le théorème classique suivant liant les +vecteurs de probabilités et les chaînes de Markov. @@ -140,7 +140,7 @@ et les chaînes de Markov. 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$ +Soient 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} @@ -178,7 +178,8 @@ que cela l'est pour $h$. \end{minipage} \label{fig:h:iter} } \end{center} - \caption{Graphes d'itérations de fonctions booléennes dans $\Bool^2$} + \caption{Graphes des itérations unaires + de fonctions booléennes dans $\Bool^2$} \label{fig:xplgraphIter} \end{figure} @@ -293,26 +294,30 @@ 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. -On énonce directement le théorème suivant dont la preuve est donnée en annexes~\ref{anx:generateur}. +On énonce directement le théorème suivant dont la preuve est donnée en annexe~\ref{anx:generateur}. -\begin{theorem} +\begin{restatable}[Uniformité de la sortie de l'algorithme~\ref{CI Algorithm}]{theorem}{PrngCIUniforme}\label{thm:prng:u} Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\textsc{giu}(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. + et $M$ une matrice $2^n\times 2^n$ + définie par + $M = \dfrac{1}{n} \check{M}$. Si $\textsc{giu}(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{theorem} +\end{restatable} \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. @@ -336,11 +341,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} @@ -437,11 +442,11 @@ 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. -\section{Un PRNG basé sur des itérations unaires qui est chaotique } +\section{Un PRNG basé sur des itérations unaires qui est chaotique }\label{prng:unaire:chaos} Cette section présente un espace métrique adapté au générateur de nombres pseudo-aléatoires présenté à l'algorithme~\ref{CI Algorithm} et prouve ensuite que la fonction qu'il représente @@ -457,15 +462,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 $$ @@ -474,14 +478,14 @@ F_{f_u}(\hdots (F_{f_u}(F_{f_u}(x,u^0), u^1), \hdots), u^{p_i-1}). $$ -on construit l'espace +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$). @@ -522,9 +526,9 @@ 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 +La distance de Hamming $d_{\mathds{B}^\mathsf{N}}$ entre les décompositions binaires de $e$ et de $\check{e}$ (\textit{i.e.}, le le nombre de bits qu'elles ont de différent) constitue la partie entière de $d(X,\check{X})$. @@ -537,7 +541,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 @@ -545,7 +549,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 @@ -554,12 +558,12 @@ jusqu'à atteindre $p+n\times \max{(\mathcal{P})}$ éléments. \item Si $v^0<\check{v}^0$, alors les $ \max{(\mathcal{P})}$ blocs de $n$ é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. +$\check{u}^{v^0}$ (sur $n$ éléments), ..., $\check{u}^{\check{v}^0-1}$ (sur $n$ éléments), suivis 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: @@ -599,8 +603,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 @@ -609,47 +615,49 @@ On prend alors le $v^0=1$ premier terme de $u$, chaque terme étant codé sur $n=2$ éléments, soit 06. Comme on itère au plus $\max{(\mathcal{P})}$ fois, on complète cette valeur par des 0 de sorte que -la chaîne obtenue a $n\times \max{(\mathcal{P})}=22$ éléments, soit: +la chaîne obtenue ait $n\times \max{(\mathcal{P})}=22$ éléments, soit: 0600000000000000000000. 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} +On a la proposition suivante, qui est démontrée en annexe~\ref{anx:generateur}. -On a la proposition suivante, qui est démontrée en annexes~\ref{anx:generateur}. -\begin{lemma} + +\begin{restatable}[Une distance dans $\mathcal{X}_{\mathsf{N},\mathcal{P}}$]{theorem}{distancedsxnp} $d$ est une distance sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$. -\end{lemma} +\end{restatable} \subsection{Le graphe $\textsc{giu}_{\mathcal{P}}(f)$ étendant $\textsc{giu}(f)$} @@ -661,8 +669,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 appartient à $[\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)$. @@ -676,7 +685,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} @@ -684,7 +693,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} @@ -692,7 +701,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} @@ -713,39 +722,48 @@ $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$ déjà détail Le graphe $\textsc{giu}_{\{1\}}(h)$ a déjà été donné à la figure~\ref{fig:h:iter}. Les graphes $\textsc{giu}_{\{2\}}(h)$, $\textsc{giu}_{\{3\}}(h)$ et -$\textsc{giu}_{\{2,3\}}(h)$ sont respectivement donnés aux figure~\ref{fig:h2prng}, ~\ref{fig:h3prng} et ~\ref{fig:h23prng}. +$\textsc{giu}_{\{2,3\}}(h)$ sont respectivement donnés aux figures~\ref{fig:h2prng}, ~\ref{fig:h3prng} et ~\ref{fig:h23prng}. Le premier (respectivement le second) illustre le comportement du générateur lorsque qu'on itère exactement 2 fois (resp. 3 fois) puis qu'on affiche le résultat. Le dernier donnerait le comportement d'un générateur qui s'autoriserait -à itérer en interne systématiquement 2 ou trois fois avant de retourner un résultat. +à itérer en interne systématiquement 2 ou 3 fois avant de retourner un résultat. \end{xpl} \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$ -est prouvé en annexes~\ref{anx:generateur}. +Le théorème suivant, similaire à ceux dans $\mathcal{X}_u$ et dans $\mathcal{X}_g$ +est prouvé en annexe~\ref{anx:generateur}. -\begin{theorem} +\begin{restatable}[Conditions pour la chaoticité de $G_{f_u,\mathcal{P}}$]{theorem}{thmchoticitgfp} La fonction $G_{f_u,\mathcal{P}}$ est chaotique sur $(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$ si et seulement si -graphe d'itération $\textsc{giu}_{\mathcal{P}}(f)$ +le graphe d'itérations $\textsc{giu}_{\mathcal{P}}(f)$ est fortement connexe. -\end{theorem} -On alors corollaire suivant - -\begin{corollary} - Le générateur de nombre pseudo aléatoire détaillé - à l'algorithme~\ref{CI Algorithm} - n'est pas chaotique - sur $(\mathcal{X}_{\mathsf{N},\{b\}},d)$ pour la fonction négation. -\end{corollary} -\begin{proof} - Dans cet algorithme, $\mathcal{P}$ est le singleton $\{b\}$. - Que $b$ soit pair ou impair, $\textsc{giu}_{\mathcal{b}}(f)$ - n'est pas fortement connexe. -\end{proof} - +\end{restatable} +% On alors corollaire suivant + +% \begin{corollary} +% Le générateur de nombre pseudo aléatoire détaillé +% à l'algorithme~\ref{CI Algorithm} +% n'est pas chaotique +% sur $(\mathcal{X}_{\mathsf{N},\{b\}},d)$ pour la fonction négation. +% \end{corollary} +% \begin{proof} +% Dans cet algorithme, $\mathcal{P}$ est le singleton $\{b\}$. +% Que $b$ soit pair ou impair, $\textsc{giu}_{\{b\}}(f)$ +% n'est pas fortement connexe. +% \end{proof} + + +\section{Conclusion} +Ce chapitre a proposé un algorithme permettant de construire un +PRNG chaotique à partir d'un PRNG existant. Pour ce faire, il est nécessaire +et suffisant que la fonction $f$ qui est itérée un nombre $b$ de fois +possède un $\textsc{giu}_{\{b\}}(f)$ fortement connexe et que sa matrice de Markov associée soit doublement stochastique. +Le chapitre suivant montre comment construire une telle fonction. + +