On peut penser à exploiter une de ces fonctions $G_f$
comme un générateur aléatoire.
-Ce chapitre présente une application directe
+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.
+à la génération de nombres pseudo-aléatoires.
+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}.
-La suite de ce document donnera
-une condition nécessaire est suffisante pour que
-cette propriété soit satisfaite.
-
-
-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}
-
-
-\section{ Nombres pseudo aléatoires construits par itérations unaires}\label{sub:prng:algo}
+\section{ Nombres pseudo-aléatoires construits par itérations unaires}\label{sub:prng:algo}
\end{algorithm}
\subsection{Algorithme d'un générateur}
-On peut penser à construire un générateur de nombres pseudo
-aléatoires comme dans l'algorithme~\ref{CI Algorithm} donné ci-dessous.
+On peut penser à construire un générateur de nombres
+pseudo-aléatoires comme dans l'algorithme~\ref{CI Algorithm} donné ci-dessous.
Celui-ci prend en entrée: une fonction $f$;
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.
+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)$
+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}$.
-Pour simuler au mieux l'aléa, un bon générateur de nombre pseudo-aléatoires
+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.
$$\exists k \in \mathds{N}^\ast, \forall i,j \in \llbracket 1; n \rrbracket, M_{ij}^k>0.$$
On énonce le théorème classique suivant liant les
-vecteur de probabilités
+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$
+nombres pseudo-aléatoires est uniformément distribuée ou non.
+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}
sont donc fortement connexes, ce que l'on peut 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
+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$.
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
+Ainsi la chaîne de Markov associée à $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.
+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
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$
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
+ 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}
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}}$.
+Soit $e_i$ le $i^{\textrm{ème}}$ vecteur de 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
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
+pseudo-aléatoires par le
\emph{National Institute of Standards and Technology} (NIST).
L'expérience a montré notamment que toutes ces fonctions
passent avec succès cette batterie de tests.
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 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}}=
[\mathsf{N}]^{\Nats}\times
\mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket} \times \mathcal{S}_\mathcal{P}$.
\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})$.
$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{enumerate}
\item Les $p$ suivants sont $|v^1-\check{v}^1|$, etc.
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
-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 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), et pour chaque
$k$, $0 \le k \le p_i-1$, on a
- $u_k$ qui apaprtient à $[\mathsf{N}]$ et
+ $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)$.
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 à ceux dans $\mathcal{X}_u$ et dans $\mathcal{X}_g$
-est prouvé en annexes~\ref{anx:generateur}.
+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}_{\{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.
+
+
