-Pour décrire un peu plus précisément le principe de
-la génération pseudo-aléatoire, considérons l'espace booléen
-$\Bool=\{0,1\}$
-muni des lois \og +\fg{}, \og . \fg{} et \og $\overline{\mathstrut\enskip}$ \fg{}
-définies par les tableaux ci-dessous:
-
-\begin{minipage}{0.33\textwidth}
- \begin{center}
- \begin{tabular}{|c|c|c|}
- \hline
- + & 0& 1 \\
- \hline
- 0 & 0& 1 \\
- \hline
- 1 & 1& 1 \\
- \hline
- \end{tabular}
-\end{center}
-\end{minipage}
-\begin{minipage}{0.33\textwidth}
- \begin{center}
- \begin{tabular}{|c|c|c|}
- \hline
- . & 0& 1 \\
- \hline
- 0 & 0& 0 \\
- \hline
- 1 & 0& 1 \\
- \hline
- \end{tabular}
-\end{center}
-\end{minipage}
-\begin{minipage}{0.32\textwidth}
- \begin{center}
- \begin{tabular}{|c|c|c|}
- \hline
- & 0& 1 \\
- \hline
- $\overline{\mathstrut\enskip}$ & 1& 0 \\
- \hline
- \end{tabular}
-\end{center}
-\end{minipage}
-
-
-La fonction itérée est
-une fonction $f$ de $\Bool^n$ dans lui-même qui à
-un mot binaire $x = (x_1,\ldots,x_n)$
-associe le mot $(f_1(x),\ldots, f_n(x))$.
-Un exemple de fonction de $\Bool^n$ dans lui-même
-est la fonction négation
-définie par
-$\neg(x)=(\overline{x_1},\dots,\overline{x_n})$.
-
-Le principe itératif est le suivant:
-à chaque itération $t$, on choisit un indice $i$ entre $1$ et $n$,
-et le mot $x^t = (x_1^t,\ldots,x_n^t)$ est remplacé par
-$x^{t+1} = (x_1^t,\ldots , x_{i-1}^t, f_i(x^t), x_{i+1}^t,\ldots, x_n^t)$.
-
-Au bout d'un nombre $N$ d'itérations,
-si la fonction, notée $G_f$ dans ce document,
-que l'on peut associer à l'algorithme décrit ci-dessus
+Au bout d'un nombre $b$ d'itérations,
+si la fonction, notée $G_{f_u}$ (ou bien $G_{f_g}$)
+présentée au chapitre~\ref{chap:carachaos},
a de \og bonnes\fg{} propriétés chaotiques,
-le mot $x^N$ doit être \og très différent\fg{} de $x^0$
-de façon à même sembler ne plus dépendre de $x_0$:
-pour un générateur aléatoire, il faut que la structure de
-$x^N$ semble être due au hasard;
-pour une application cryptographique, il faut qu'il
-soit matériellement impossible (dans les conditions techniques actuelles)
-de retrouver $x^0$ à partir de $x^N$.
-
-Tous les mots de
-$\Bool^n$ peuvent constituer les
-$2^n$ sommets d'un \gls{graphoriente} (cf. glossaire)
-dans lequel un arc relie deux sommets $x$ et $x'$
-s'il existe une itération de l'algorithme
-de génération qui permet de passer de $x$ à $x'$.
-Ce graphe est appelé le graphe d'itérations et
-ce document montre que si l'on a un \gls{graphfortementconnexe} (cf. glossaire),
-alors la fonction $G_f$ est transitive, donc chaotique.
-
+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 \gls{distributionuniforme} (cf. glossaire).
-La dernière partie de ce document donnera,
-dans le cas où le graphe d'itérations est fortement connexe,
+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
-à la génération de nombres pseudo aléatoires. On présente tout d'abord le générateur
+Cette section présente 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 \gls{distributionuniforme}
-(cf. glossaire) de la sortie
+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}
-\subsection{ Générateur de nombres pseudo aléatoires basé sur le chaos}\label{sub:prng:algo}
+\section{ Nombres pseudo aléatoires construits par itérations unaires}\label{sub:prng:algo}
-On peut penser à construire un générateur de nombres pseudo
-aléatoires comme dans l'algorithme~\ref{CI Algorithm} donné ci-dessous.
\begin{algorithm}[h]
%\begin{scriptsize}
une configuration initiale $x^0$ ($n$ bits)}
\KwOut{une configuration $x$ ($n$ bits)}
$x\leftarrow x^0$\;
-$k\leftarrow b + \textit{Random}(b+1)$\;
+$k\leftarrow b $\;
%$k\leftarrow b + \textit{XORshift}(b+1)$\;
-\For{$i=0,\dots,k-1$}
+\For{$i=1,\dots,k$}
{
$s\leftarrow{\textit{Random}(n)}$\;
%$s\leftarrow{\textit{XORshift}(n)}$\;
-$x\leftarrow{F_f(s,x)}$\;
+$x\leftarrow{F_{f_u}(s,x)}$\;
}
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}
+\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.
+
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 une configuration initiale $x^0$.
-Il retourne une nouvelle configuration $x$.
+est compris entre $b+1 $ et $2b+1$ (et donc supérieur à $b$)
+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
+à 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 \gls{distributionuniforme} (cf. glossaire) et utilise
-\textit{XORshift} qui est une classe de générateurs de
-nombres pseudo aléatoires
-très rapides conçus par George Marsaglia.
-
-% L'algorithme \textit{XORshift} exploite itérativement
-% la fonction \og \gls{xor}\fg{} $\oplus$ (cf. glossaire)
-% sur des nombres obtenus grâce à des \glspl{decalageDeBits} (cf. glossaire).
-
-L'algorithme \textit{XORshift}
-exploite itérativement l'opérateur $\oplus$
-sur des nombres obtenus grâce à des \glspl{decalageDeBits} (cf. glossaire).
-Cet opérateur, défini dans $\Bool^{n}$,
-applique la fonction \og \gls{xor} \fg{} (cf. glossaire)
-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}
-
-
-
-Il reste à instancier une fonction $f$ dans
-l'algorithme~\ref{CI Algorithm}
-en adéquation avec l'approche développée
-en section~\ref{sec:sccg}.
-La section suivante montre comment l'uniformité de la distribution a
-contraint cette instanciation.
+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
+$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.
+Pour $b=1$, l'algorithme itère la fonction $F_{f_u}$.
+Regardons comment l'uniformité de la distribution a
+contraint la fonction.
\subsection{Un générateur à sortie uniformément distribuée}\label{sub:prng:unif}
$$\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
-\glspl{vecteurDeProbabilite} (cf. glossaire)
-et les \glspl{chaineDeMarkov} (cf. glossaire):
+vecteur de probabilités
+et les chaînes de Markov.
-\begin{Theo}\label{th}
+
+\begin{theorem}\label{th}
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 \gls{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 \gls{chaineDeMarkov} $\pi^k$
+ alors la {chaîne de Markov} $\pi^k$
converge vers $\pi$ lorsque $k$ tend vers l'infini.
-\end{Theo}
+\end{theorem}
Montrons sur un exemple jouet à deux éléments
Leurs graphes d'interactions donnés en figure \ref{fig:g:inter} et \ref{fig:h:inter}
vérifient les hypothèses du théorème~\ref{th:Adrien}.
Leurs graphes d'itérations
-sont donc fortement connexes, ce que l'on a pu déjà vérifier aux figures
-\ref{fig:g:iter} et \ref{fig:h:iter}.
+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
que cela l'est pour $h$.
+
+
+
+
+
+
+
+\begin{figure}%[t]
+ \begin{center}
+ \subfigure[$g(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}) $]{
+ \begin{minipage}{0.40\textwidth}
+ \begin{center}
+ \includegraphics[height=4cm]{images/g.pdf}
+ \end{center}
+ \end{minipage}
+ \label{fig:g:iter}
+ }
+ \subfigure[$h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$]{
+ \begin{minipage}{0.40\textwidth}
+ \begin{center}
+ \includegraphics[height=4cm]{images/h.pdf}
+ \end{center}
+ \end{minipage}
+ \label{fig:h:iter}
+ } \end{center}
+ \caption{Graphes des itérations unaires
+ de fonctions booléennes dans $\Bool^2$}
+ \label{fig:xplgraphIter}
+ \end{figure}
+
+
+
+
+
+
+
+
+
+\begin{figure}%[t]
+ \begin{center}
+ \subfigure[$g(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}) $]{
+ \begin{minipage}{0.40\textwidth}
+ \begin{center}
+ \includegraphics[height=3cm]{images/gp.pdf}
+ \end{center}
+ \end{minipage}
+ \label{fig:g:inter}
+ }
+ \subfigure[$h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$]{
+ \begin{minipage}{0.40\textwidth}
+ \begin{center}
+ \includegraphics[height=3cm]{images/hp.pdf}
+ \end{center}
+ \end{minipage}
+ \label{fig:h:inter}
+ } \end{center}
+ \caption{Graphes d'interactions de fonctions booléennes dans $\Bool^2$}
+ \label{fig:xplgraphInter}
+ \end{figure}
+
+
+
+
+
+
Comme le générateur \textit{Random} possède une sortie uniformément
distribuée, la stratégie est uniforme sur $\llbracket 1, 2 \rrbracket$,
et donc,
-pour tout sommet de $\Gamma(g)$ et de $\Gamma(h)$,
+pour tout sommet de $\textsc{giu}(g)$ et de $\textsc{giu}(h)$,
chaque arc sortant de ce sommet a, parmi l'ensemble des arcs sortant
de ce sommet, une probabilité $1/2$ d’être celui qui sera traversé.
-En d'autres mots, $\Gamma(g)$ est le graphe orienté d'une chaîne de Markov.
-Il est facile de vérifier que la \gls{matriceDeTransitions} (cf. glossaire)
+En d'autres mots, $\textsc{giu}(g)$ est le graphe orienté d'une chaîne de Markov.
+Il est facile de vérifier que la matrice de transitions
d'un tel processus
est $M_g = \frac{1}{2} \check{M}_g$,
-où $\check{M}_g$ est la \gls{matriceDAdjacence} (cf. glossaire) donnée en
-figure~\ref{fig:g:incidence} (voir ci-après), et similairement pour $M_h$.
+où $\check{M}_g$ est la matrice d' adjacence donnée en
+figure~\ref{fig:g:incidence} (voir ci-après), et de manière similaire pour $M_h$.
\begin{figure}[h]
\begin{center}
- \subfloat[$\check{M}_g $.]{
+ \subfigure[$\check{M}_g $.]{
\begin{minipage}{0.25\textwidth}
\begin{center}
% \vspace{-3cm}
\end{minipage}
\label{fig:g:incidence}
}
- \subfloat[$\check{M}_h $.]{
+ \subfigure[$\check{M}_h $.]{
\begin{minipage}{0.25\textwidth}
\begin{center}
$\left(
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}.
-Considérons le lemme technique suivant:
-\begin{Lemma}\label{lem:stoc}
-Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\Gamma(f)$ son graphe d'itérations, $\check{M}$ la matrice d'adjacence de $\Gamma(f)$, et $M$ la matrice
-$2^n\times 2^n$ définie par
-$M = \frac{1}{n}\check{M}$.
-Alors $M$ est une matrice stochastique régulière si et seulement si
-$\Gamma(f)$ est fortement connexe.
-\end{Lemma}
-
-\begin{Proof}
-On remarque tout d'abord que $M$
-est une matrice stochastique par construction.
-Supposons $M$ régulière.
-Il existe donc $k$ tel que $M_{ij}^k>0$ pour chaque $i,j\in \llbracket
-1; 2^n \rrbracket$. L'inégalité $\check{M}_{ij}^k>0$ est alors établie.
-Puisque $\check{M}_{ij}^k$ est le nombre de chemins de $i$ à $j$ de longueur $k$
-dans $\Gamma(f)$ et puisque ce nombre est positif, alors
-$\Gamma(f)$ est fortement connexe.
-
-Réciproquement si $\Gamma(f)$
-est fortement connexe, alors pour tous les sommets $i$ et $j$, un chemin peut être construit pour atteindre $j$ depuis $i$ en au plus $2^n$ étapes.
-Il existe donc
-$k_{ij} \in \llbracket 1, 2^n \rrbracket$ tels que $\check{M}_{ij}^{k_{ij}}>0$.
-Comme tous les multiples $l \times k_{ij}$ de $k_{ij}$ sont tels que
-$\check{M}_{ij}^{l\times k_{ij}}>0$,
-on peut conclure que, si
-$k$ est le plus petit multiple commun de $\{k_{ij} \big/ i,j \in \llbracket 1, 2^n \rrbracket \}$ alors
-$\forall i,j \in \llbracket 1, 2^n \rrbracket, \check{M}_{ij}^{k}>0$.
-Ainsi, $\check{M}$ et donc $M$ sont régulières.
-\end{Proof}
-
-Ces résultats permettent formuler et de prouver le théorème suivant:
-
-\begin{Theo}
- Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\Gamma(f)$ son
+\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.
- Si $\Gamma(f)$ est fortement connexe, alors
+ 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{Theo}
-\begin{Proof}
- $M$ est une matrice stochastique régulière (Lemme~\ref{lem:stoc})
- qui a un unique vecteur de probabilités stationnaire
- (Théorème \ref{th}).
- Soit $\pi$ défini par
- $\pi = \left(\frac{1}{2^n}, \hdots, \frac{1}{2^n} \right)$.
- On a $\pi M = \pi$ si et seulement si
- la somme des valeurs de chaque colonne de $M$ est 1,
- \textit{i.e.} si et seulement si
- $M$ est doublement stochastique.
-\end{Proof}
-
-
-\subsection{Expérimentations}
-
-On considère le graphe d'interactions $G(f)$ donné en figure~\ref{fig:G}.
-Il vérifie le théorème~\ref{th:Adrien}:
-toutes les fonctions $f$ possédant un tel graphe d'interactions
-ont un graphe d'itérations $\Gamma(f)$ fortement connexe.
-Pratiquement, un algorithme simple de satisfaction de contraintes
-a trouvé 520 fonctions $f$ non isomorphes de graphe d'interactions $G(f)$,
-dont seulement 16 d'entre elles possédent une matrice doublement stochastique.
+\end{theorem}
+
+
+\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.
La figure~\ref{fig:listfonction} explicite ces 16 fonctions en
définissant les images des éléments de la liste
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
-associé à $\Gamma(f)$ en partant de la configuration $i$.
+associé à $\textsc{giu}(f)$ en partant de la configuration $i$.
Le nombre $\min \{
t \mid t \in \Nats, \vectornorm{e_i M_f^t - \pi} < 10^{-4}
\}$ représente le plus petit nombre d'itérations où la distance de
-- 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}
- \subfloat[Graphe d'interactions]{
+ \subfigure[Graphe d'interactions]{
\begin{minipage}{0.20\textwidth}
\begin{center}
\includegraphics[width=3.5cm]{images/Gi.pdf}
\end{minipage}
\label{fig:G}
}\hfill
- \subfloat[Fonctions doublement stochastiques]{
+ \subfigure[Fonctions doublement stochastiques]{
\begin{minipage}{0.75\textwidth}
\begin{scriptsize}
\begin{center}
de tests statistiques développée pour les générateurs de nombres
pseudo aléatoires par le
\emph{National Institute of Standards and Technology} (NIST).
-% Pour les 15 tests, le seuil $\alpha$ est fixé à $1\%$:
-% une valeur
-% qui est plus grande que $1\%$ signifie
-% que la chaîne est considérée comme aléatoire avec une confiance de $99\%$.
-% Le tableau~\ref{fig:TEST} donne une vision synthétique de toutes
-% les expérimentations.
L'expérience a montré notamment que toutes ces fonctions
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.}, 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.
+Montrer 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 }
+
+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
+est chaotique sur cet espace.
+
+\subsection{Un espace $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ pour le PRNG de l'algorithme~\ref{CI Algorithm}}
+
+
+
+Introduisons tout d'abord $\mathcal{P} \subset \mathds{N}$ un ensemble fini non vide de cardinalité
+$\mathsf{p} \in \mathds{N}^\ast$.
+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}
+\rightarrow \mathds{B}^\mathsf{N}$ définie par
+
+$$
+F_{f_u,p_i} (x,(u^0, u^1, \hdots, u^{p_i-1})) \mapsto
+F_{f_u}(\hdots (F_{f_u}(F_{f_u}(x,u^0), u^1), \hdots), u^{p_i-1}).
+$$
+
+
+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
+\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.
+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é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}} \\
+& \left((u^k)_{k \in \mathds{N}},(v^k)_{k \in \mathds{N}}\right) & \longmapsto & \left(\sigma^{v^0}\left((u^k)_{k \in \mathds{N}}\right),\sigma\left((v^k)_{k \in \mathds{N}}\right)\right).
+\end{array}
+$$
+En d'autres termes, $\Sigma$ reçoit deux suites $u$ et $v$ et
+effectue $v^0$ décalage vers la droite sur la première et un décalage vers la droite
+sur la seconde.
+
+
+Ainsi, les sorties $(y^0, y^1, \hdots )$ produites par le générateur détaillé dans
+l'algorithme~\ref{CI Algorithm}
+sont les premiers composants des itérations $X^0 = (x^0, (u,v))$ et $\forall n \in \mathds{N},
+X^{n+1} = G_{f_u,\mathcal{P}}(X^n)$ dans $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ où
+$G_{f_u,\mathcal{P}}$ est définie par:
+
+
+
+
+\begin{equation}
+\begin{array}{cccc}
+G_{f_u,\mathcal{P}} :& \mathcal{X}_{\mathsf{N},\mathcal{P}} & \longrightarrow & \mathcal{X}_{\mathsf{N},\mathcal{P}}\\
+ & (e,(u,v)) & \longmapsto & \left( F_{f,v^0}\left( e, (u^0, \hdots, u^{v^0-1}\right), \Sigma (u,v) \right) .
+\end{array}
+\end{equation}
+
+
+
+\subsection{Une distance sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$}
+
+On définit la fonction $d$ sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ comme suit:
+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}
+\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
+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})$.
+\item la partie décimale est construite à partir des différences entre
+$v^0$ et $\check{v}^0$, suivie des différences entre les séquences finies
+$u^0, u^1, \hdots, u^{v^0-1}$ et $\check{u}^0, \check{u}^1, \hdots, \check{u}^{\check{v}^0-1}$, suivie par les différences entre $v^1$ et $\check{v}^1$,
+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écisément, soit
+$p = \lfloor \log_{10}{(\max{\mathcal{P}})}\rfloor +1$ et
+$n = \lfloor \log_{10}{(\mathsf{N})}\rfloor +1$.
+\begin{itemize}
+\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
+ à évaluer de combien $u^0, u^1, \hdots, u^{v^0-1}$ diffère de
+ $\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}
+\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
+partie décimale de $d(X,\check{X})$ est complétée par des 0
+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.
+\item Le cas $v^0>\check{v}^0$ est similaire, et donc omis
+\end{itemize}
+\item Les $p$ suivants sont $|v^1-\check{v}^1|$, etc.
+\end{itemize}
+\end{itemize}
+
+
+La fonction $d$ peut se formaliser comme suit:
+$$d(x,\check{x})=d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})+d_{\mathds{B}^\mathsf{N}}(e,\check{e}),$$
+où: % $p=\max \mathcal{P}$ and:
+\begin{itemize}
+\item $d_{\mathds{B}^\mathsf{N}}$ est la distance de Hamming,
+\item $\forall s=(u,v), \check{s}=(\check{u},\check{v}) \in \mathcal{S}_{\mathsf{N},\mathcal{P}}$,\newline
+$$\begin{array}{rcl}
+ d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) &= &
+ \sum_{k=0}^\infty \dfrac{1}{10^{(k+1)p+kn\max{(\mathcal{P})}}}
+ \bigg(|v^k - \check{v}^k| \\
+ & & + \left| \sum_{l=0}^{v^k-1}
+ \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{(l+1)n}} -
+ \sum_{l=0}^{\check{v}^k-1}
+ \dfrac{\check{u}^{\sum_{m=0}^{k-1} \check{v}^m +l}}{ 10^{(l+1)n}} \right| \bigg)
+\end{array}
+$$ %\left| \sum_{l=0}^{v^k-1} \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{l}} - \sum_{l=0}^{\check{v}^k-1} \dfrac{\check{u}^{\sum_{m=0}^{k-1} \check{v}^m +l}}{ 10^{l}}\right|\right)}.$$
+\end{itemize}
+
+
+
+\begin{xpl}
+On considère par exemple
+$\mathsf{N}=13$, $\mathcal{P}=\{1,2,11\}$ ($\mathsf{p}$ vaut ainsi $3$),
+et
+$s=\left\{
+\begin{array}{l}
+u=\underline{6,} ~ \underline{11,5}, ...\\
+v=1,2,...
+\end{array}
+\right.$
+avec
+$\check{s}=\left\{
+\begin{array}{l}
+\check{u}=\underline{6,4} ~ \underline{1}, ...\\
+\check{v}=2,1,...
+\end{array}
+\right.$.
+
+Ainsi $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.010004000000000000000000011005 ...$
+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
+(Comme $\mathcal{P}=\{1,2,11\}$, cette différence peut valoir 10).
+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:
+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 à
+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.
+$$
+
+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}
+$d$ est une distance sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$.
+\end{lemma}
+
+
+\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
+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
+% 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
+$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)$.
+
+
+
+
+
+\begin{figure}%[t]
+ \begin{center}
+ \subfigure[$\textsc{giu}_{\{2\}}(h)$]{
+ \begin{minipage}{0.30\textwidth}
+ \begin{center}
+ \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}
+ \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}
+ \end{center}
+ \end{minipage}
+ \label{fig:h23prng}
+ }
+
+ \end{center}
+ \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}
+
+
+
+
+\begin{xpl}
+On reprend l'exemple où $\mathsf{N}=2$ et
+$h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$ déjà détaillé
+à la section~\ref{sub:prng:unif}.
+
+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 (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.
+
+\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}.
-% \begin{table}[th]
-% \begin{scriptsize}
-% \begin{tabular}{|*{17}{c|}}
-% \hline
-% {Propriété}& $\mathcal{F}_{1}$ &$\mathcal{F}_{2}$ &$\mathcal{F}_{3}$ &$\mathcal{F}_{4}$ &$\mathcal{F}_{5}$ &$\mathcal{F}_{6}$ &$\mathcal{F}_{7}$ &$\mathcal{F}_{8}$ &$\mathcal{F}_{9}$ &$\mathcal{F}_{10}$ &$\mathcal{F}_{11}$ &$\mathcal{F}_{12}$ &$\mathcal{F}_{13}$ &$\mathcal{F}_{14}$ &$\mathcal{F}_{15}$ &$\mathcal{F}_{16}$ \\
-% \hline
-% Fréquence &77.9 &15.4 &83.4 &59.6 &16.3 &38.4 &20.2 &29.0 &77.9 &21.3 &65.8 &85.1 &51.4 &35.0 &77.9 &92.4 \\
-% \hline
-% Fréquence / bloc &88.3 &36.7 &43.7 &81.7 &79.8 &5.9 &19.2 &2.7 &98.8 &1.0 &21.3 &63.7 &1.4 &7.6 &99.1 &33.5 \\
-% \hline
-% Somme cummulée &76.4 &86.6 &8.7 &66.7 &2.2 &52.6 &20.8 &80.4 &9.8 &54.0 &73.6 &80.1 &60.7 &79.7 &76.0 &44.7 \\
-% \hline
-% Exécution &5.2 &41.9 &59.6 &89.8 &23.7 &76.0 &77.9 &79.8 &45.6 &59.6 &89.8 &2.4 &96.4 &10.9 &72.0 &11.5 \\
-% \hline
-% Longue exécution &21.3 &93.6 &69.9 &23.7 &33.5 &30.4 &41.9 &43.7 &30.4 &17.2 &41.9 &51.4 &59.6 &65.8 &11.5 &61.6 \\
-% \hline
-% Rang &1.0 &41.9 &35.0 &45.6 &51.4 &20.2 &31.9 &83.4 &89.8 &38.4 &61.6 &4.0 &21.3 &69.9 &47.5 &95.6 \\
-% \hline
-% Fourrier Rapide &40.1 &92.4 &97.8 &86.8 &43.7 &38.4 &76.0 &57.5 &36.7 &35.0 &55.4 &57.5 &86.8 &76.0 &31.9 &7.6 \\
-% \hline
-% Sans superposition &49.0 &45.7 &50.5 &51.0 &48.8 &51.2 &51.6 &50.9 &50.9 &48.8 &45.5 &47.3 &47.0 &49.2 &48.6 &46.4 \\
-% \hline
-% Avec Superposition &27.6 &10.9 &53.4 &61.6 &16.3 &2.7 &59.6 &94.6 &88.3 &55.4 &76.0 &23.7 &47.5 &91.1 &65.8 &81.7 \\
-% \hline
-% Universelle &24.9 &35.0 &72.0 &51.4 &20.2 &74.0 &40.1 &23.7 &9.1 &72.0 &4.9 &13.7 &14.5 &1.8 &93.6 &65.8 \\
-% \hline
-% Entropie approchée &33.5 &57.5 &65.8 &53.4 &26.2 &98.3 &53.4 &63.7 &38.4 &6.7 &53.4 &19.2 &20.2 &27.6 &67.9 &88.3 \\
-% \hline
-% Suite aléatoire &29.8 &35.7 &40.9 &36.3 &54.8 &50.8 &43.5 &46.0 &39.1 &40.8 &29.6 &42.0 &34.8 &33.8 &63.0 &46.3 \\
-% \hline
-% Suite aléatoire variante &32.2 &40.2 &23.0 &39.6 &47.5 &37.2 &56.9 &54.6 &53.3 &31.5 &23.0 &38.1 &52.3 &57.1 &47.7 &40.8 \\
-% \hline
-% Série &56.9 &58.5 &70.4 &73.2 &31.3 &45.9 &60.8 &39.9 &57.7 &21.2 &6.4 &15.6 &44.7 &31.4 &71.7 &49.1 \\
-% \hline
-% Complexité linéaire &24.9 &23.7 &96.4 &61.6 &83.4 &49.4 &49.4 &18.2 &3.5 &76.0 &24.9 &97.2 &38.4 &38.4 &1.1 &8.6 \\
-% \hline
-% \end{tabular}
-% \end{scriptsize}
-% \caption{Test de NIST réalisé sur des instances de générateurs}\label{fig:TEST}
-% \end{table}
+\begin{theorem}
+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)$
+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}
