X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/78cd1e6fef0e2664357da1584c958f06b0820a88..9e9f22c16917d3bf287f5e1f0df739200c392594:/14Secrypt.tex

diff --git a/14Secrypt.tex b/14Secrypt.tex
index f1fae6f..bc59ba1 100644
--- 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
-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 
@@ -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. 
 
-\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 
@@ -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 
@@ -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 
@@ -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}
 
 
-%
+\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$.
+
