à 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 distributionuniforme
+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.
}
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}
la fonction $F_{f_u}$ 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 distributionuniforme 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 decalages 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 a 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
$$\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 probabilite
-et les chaines de Markov.
+vecteur de probabilités
+et les chaînes de Markov.
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 {vecteurDeProbabilite}
+ De plus, si $\pi^0$ est un {vecteur de probabilités}
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 {chaineDeMarkov} $\pi^k$
+ alors la {chaîne de Markov} $\pi^k$
converge vers $\pi$ lorsque $k$ tend vers l'infini.
\end{theorem}
\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}
d'un tel processus
est $M_g = \frac{1}{2} \check{M}_g$,
où $\check{M}_g$ est la matrice d' adjacence donnée en
-figure~\ref{fig:g:incidence} (voir ci-après), et similairement pour $M_h$.
+figure~\ref{fig:g:incidence} (voir ci-après), et de manière similaire pour $M_h$.
\begin{figure}[h]
\begin{center}
le vecteur d’état de la chaîne de Markov
ait une distribution suffisamment proche de la distribution uniforme.
-On énnonce 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 annexes~\ref{anx:generateur}.
-\begin{theorem}
+\begin{theorem}\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
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.
+dont 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
-- autrement dit, où la déviation par rapport à la distribution uniforme --
est inférieure
à $10^{-4}$. En prenant le max pour tous les $e_i$, on obtient une valeur pour
- $b$. Ainsi, on a
-$$
+ $b$.
+Ainsi, on a
+\begin{equation}
b = \max\limits_{i \in \llbracket 1, 2^n \rrbracket}
\{
\min \{
t \mid t \in \Nats, \vectornorm{e_i M_f^t - \pi} < 10^{-4}
\}
\}.
-$$
+\label{eq:mt:ex}
+\end{equation}
+
+\noindent Par la suite, ce nombre sera appelé \emph{temps de mélange}.
+
+
\begin{figure}%[h]
\begin{center}
passent avec succès cette batterie de tests.
Pour conclure cette section, on remarque que le générateur de nombres pseudo-aléatoires
-a été prouvé chaotique pour $b=1$, \textit{i.e.}, lorqu'il y a une sortie pour chaque itération.
-Ceci est difficilement compatible avec la volonté d'avoir une sortie uniformémement distribuée:
+a été prouvé chaotique pour $b=1$, \textit{i.e.}, lorsqu'il y a une sortie pour chaque itération.
+Ceci est difficilement compatible avec la volonté d'avoir une sortie uniformément distribuée:
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.
\section{Un PRNG basé sur des itérations unaires qui est chaotique }
Cette section présente un espace métrique adapté au générateur de nombres pseudo-aléatoires
-pésenté à l'algorithme~\ref{CI Algorithm} et prouve ensuite que la fonction qu'il représente
+présenté à l'algorithme~\ref{CI Algorithm} et prouve ensuite que la fonction qu'il représente
est chaotique sur cet espace.
\subsection{Un espace $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ pour le PRNG de l'algorithme~\ref{CI Algorithm}}
$\mathsf{p}$ vaut 1 et $p_1=b$.
-Cet algorithme peut être vu comme $b$ compostions de la function $F_{f_u}$.
+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
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$).
-Définissons la fonction de décallage $\Sigma$ pour chaque élément de $\mathds{S}_{\mathsf{N},\mathcal{P}}$.
+Définissons la fonction de décalage $\Sigma$ pour chaque élément de $\mathds{S}_{\mathsf{N},\mathcal{P}}$.
$$\begin{array}{cccc}
\Sigma:&\mathds{S}_{\mathsf{N},\mathcal{P}} &\longrightarrow
&\mathds{S}_{\mathsf{N},\mathcal{P}} \\
\end{array}
$$
En d'autres termes, $\Sigma$ reçoit deux suites $u$ et $v$ et
-effectue $v^0$ décallage vers la droite sur la première et un décallage vers la droite
+effectue $v^0$ décalage vers la droite sur la première et un décalage vers la droite
sur la seconde.
suivie par les différences entre $u^{v^0}, u^{v^0+1}, \hdots, u^{v^1-1}$ et
$\check{u}^{\check{v}^0}, \check{u}^{\check{v}^0+1}, \hdots, \check{u}^{\check{v}^1-1}$, etc.
-Plus précisemment, soit
+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}
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 chaine obtenue a $n\times \max{(\mathcal{P})}=22$ éléments, soit:
+la chaîne obtenue a $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
\subsection{Le graphe $\textsc{giu}_{\mathcal{P}}(f)$ étendant $\textsc{giu}(f)$}
A partir de $\mathcal{P}=\{p_1, p_2, \hdots, p_\mathsf{p}\}$, on
-definit le graphe orienté $\textsc{giu}_{\mathcal{P}}(f)$ de la manière suivante:
+définit le graphe orienté $\textsc{giu}_{\mathcal{P}}(f)$ de la manière suivante:
\begin{itemize}
\item les n{\oe}uds sont les $2^\mathsf{N}$ configurations de $\mathds{B}^\mathsf{N}$,
%\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
\subfigure[$\textsc{giu}_{\{2\}}(h)$]{
\begin{minipage}{0.30\textwidth}
\begin{center}
- \includegraphics[height=4cm]{images/h2prng.pdf}
+ \includegraphics[height=4cm]{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.pdf}
+ \includegraphics[height=4cm]{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.pdf}
+ \includegraphics[height=4cm]{images/h23prng}
\end{center}
\end{minipage}
\label{fig:h23prng}
}
\end{center}
- \caption{Graphes d'iterations $\textsc{giu}_{\mathcal{P}}(h)$ pour $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$}
- \label{fig:xplgraphIter}
+ \caption{Graphes d'itérations $\textsc{giu}_{\mathcal{P}}(h)$ pour $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$}
+ %\label{fig:xplgraphIter}
\end{figure}
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}.
-Le premier (repsectivement le second)
+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
\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{}.
+est prouvé en annexes~\ref{anx:generateur}.
\begin{theorem}
La fonction $G_{f_u,\mathcal{P}}$ est chaotique sur
graphe d'itération $\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}
