-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,
+fournir des nombres selon une {distributionuniforme}
+La suite de ce document donnera,
dans le cas où le graphe d'itérations est fortement connexe,
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 distributionuniforme
+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}
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
+selon une distributionuniforme 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).
+% la fonction \og {xor}\fg{} $\oplus$ (cf. glossaire)
+% sur des nombres obtenus grâce à des pl{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).
+sur des nombres obtenus grâce à des decalages de bits.
Cet opérateur, défini dans $\Bool^{n}$,
-applique la fonction \og \gls{xor} \fg{} (cf. glossaire)
+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.
$$\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):
+vecteurDeProbabilite
+et les chaineDeMarkov:
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 {vecteurDeProbabilite}
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 {chaineDeMarkov} $\pi^k$
converge vers $\pi$ lorsque $k$ tend vers l'infini.
\end{Theo}
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)
+Il est facile de vérifier que la {matriceDeTransitions}
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
+où $\check{M}_g$ est la {matriceDAdjacence} donnée en
figure~\ref{fig:g:incidence} (voir ci-après), et similairement pour $M_h$.
\begin{figure}[h]
