-> prng inclus

[hdrcouchot.git] / 14Secrypt.tex

diff --git a/14Secrypt.tex b/14Secrypt.tex
index f1fae6f7f3392a12b0598da4748163708d0769a3..bc59ba13967f60550b0b442444b2f6810296579d 100644 (file)
--- a/14Secrypt.tex
+++ b/14Secrypt.tex
@@ -1,16 +1,29 @@
 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
 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
 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 
 
 
 % This aim of this section is to show 


@@ -442,7 +455,7 @@ Ces fonctions étant générées, on s'intéresse à étudier à quelle vitesse
 un générateur les embarquant converge vers la distribution uniforme.
 C'est l'objectif de la section suivante. 
 
 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 
 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 


@@ -651,7 +664,7 @@ $\textit{fair}\leftarrow\emptyset$\;
 
 
 
 
 
 

-\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 
 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 


@@ -924,7 +937,7 @@ $$
 
 
 
 
 
 

-\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 
 
 La qualité des séquences aléatoires produites par 
 le générateur des itérations unaires ainsi que 


@@ -1072,4 +1085,16 @@ Complexité linaire& 0.005 (0.98)& 0.534 (0.99)& 0.085 (0.97)& 0.996 (1.0)\\ \hl
 \end{table}
 
 
 \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$.
+