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}
\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}
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.
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 a ce générateur embarqué.
+Notre approche vise a donner des propriétés de chaos à ce générateur embarqué.
% \textit{Random}$(l)$.
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}
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.
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}
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}\label{thm:prng:u}
+\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$
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.
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}
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
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
$$
$$
-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$).
$\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})$.
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
$\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
$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:
\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
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 annexes~\ref{anx:generateur}.
-\begin{lemma}
+On a la proposition suivante, qui est démontrée en annexe~\ref{anx:generateur}.
+
+
+\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)$}
%\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)$.
\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}
\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}
\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}
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.
+
+
