On a vu dans le chapitre précédent que pour avoir
un générateur à sortie
uniforme, il est nécessaire que la matrice d'adjacence du graphe d'itération du
-système soit doublement stochastique. Nous présentons dans cette partie une
-méthode permettant de générer de telles matrices.
-
-Les approches théoriques basées sur la programmation logique par contraintes sur
-domaines finis ne sont pas envisageables en pratique dès que la taille des
-matrices considérées devient suffisamment grande.
-
+système soit doublement stochastique. Nous présentons dans cette partie
+des méthodes effectives permettant de générer de telles matrices.
+La première est basée sur la programmation logique par contraintes
+(Section~\ref{sec:plc}).
+Cependant celle-ci souffre de ne pas passer à l'échelle et ne fournit pas
+une solution en un temps raisonnable dès que la fonction à engendrer
+porte sur un grand nombre de bits.
Une approche plus pragmatique consiste à supprimer un cycle hamiltonien dans le
-graphe d'itérations, ce qui revient à supprimer en chaque n{\oe}ud de ce graphe une
-arête sortante et une arête entrante.
+graphe d'itérations $\textsc{giu}(\neg)$ (section~\ref{sec:hamiltonian}).
+Pour obtenir plus rapidement une distribution uniforme, l'idéal serait
+de supprimer un cycle hamiltonien qui nierait autant de fois chaque bit.
+Cette forme de cycle est dit équilibré. La section~\ref{sub:gray} établit le
+lien avec les codes de Gray équilibrés, étudiés dans la litérature.
+La section suivante présente une démarche de génération automatique de code de Gray équilibré (section~\ref{sec:induction}).
+La vitesse avec laquelle l'algorithme de PRNG converge en interne vers
+une distribution unifiorme est étduiée théoriquement et pratiquement à la
+section~\ref{sec:mixing}.
+L'extension du travail aux itérations généralisées est présenté à la
+section~\ref{sec:prng:gray:general}.
+Finalement, des instances de PRNGS engendrés selon les méthodes détaillées dans
+ce chapitre sont présentés en section~\ref{sec:prng;gray:tests}.
+Les sections~\ref{sec:plc} à~\ref{sub:gray} ont été publiées
+à~\ref{chgw+14:oip}.
% This aim of this section is to show
un générateur les embarquant converge vers la distribution uniforme.
C'est l'objectif de la section suivante.
-\section{Quantifier l'écart par rapport à la distribution uniforme}
+\section{Quantifier l'écart par rapport à la distribution uniforme}\label{sec:mixing}
On considère ici une fonction construite comme à la section précédente.
On s'intéresse ici à étudier de manière théorique les
itérations définies à l'équation~(\ref{eq:asyn}) pour une
-\section{Et les itérations généralisées?}
+\section{Et les itérations généralisées?}\label{sec:prng:gray:general}
Le chaptire précédent a présenté un algorithme de
PRNG construit à partir d'itérations unaires.
On pourrait penser que cet algorithme est peu efficace puisqu'il
-\section{Tests statistiques}
+\section{Tests statistiques}\label{sec:prng;gray:tests}
La qualité des séquences aléatoires produites par
le générateur des itérations unaires ainsi que
\end{table}
-%
+\section{Conclusion}
+Ce chaptitre a montré comment construire un PRNG chaotique, notamment à partir
+de codes de Gray équilibrés. Une méthode completement automatique de
+construction de ce type de codes a été présentée étendant les méthodes
+existantes.
+Dans le cas des itérations unaires,
+l'algorithme qui en découle a un temps de mélange qui a
+une borne sup quadratique de convergence vers la distribution uniforme.
+Pratiquement, ce temps de mélange se rapproche de $N\ln N$.
+Les expérimentations au travers de la batterie de test de NIST ont montré
+que toutes les propriétés statistiques sont obtenues pour
+ $\mathsf{N} = 4, 5, 6, 7, 8$.
+
