X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/78cd1e6fef0e2664357da1584c958f06b0820a88..9e9f22c16917d3bf287f5e1f0df739200c392594:/14Secrypt.tex?ds=inline 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$. +