à 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
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
}
\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)$}
+ \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
