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 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}
On énonce directement le théorème suivant dont la preuve est donnée en annexes~\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$
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}
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 a la proposition suivante, qui est démontrée en annexes~\ref{anx:generateur}.
-\begin{lemma}
+
+
+\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 théorème suivant, similaire à ceux dans $\mathcal{X}_u$ et dans $\mathcal{X}_g$
est prouvé en annexes~\ref{anx:generateur}.
-\begin{theorem}
+\begin{restatable}[Conditions pour la choticité 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é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}_{\{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.
+
+
