X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/523864c862215a63c5133568a9771f5b8f60c89e..d33e664452e3655370cbe069e3f6fbd16842c818:/14Secrypt.tex diff --git a/14Secrypt.tex b/14Secrypt.tex index 858a8e5..5e4cafc 100644 --- a/14Secrypt.tex +++ b/14Secrypt.tex @@ -12,7 +12,7 @@ Une approche plus pragmatique consiste à supprimer un cycle hamiltonien dans l 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 +Cette forme de cycle est dite équilibré. La section~\ref{sub:gray} établit le lien avec les codes de Gray équilibrés, étudiés dans la litté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 @@ -55,7 +55,7 @@ la matrice est stochastique à droite; \item pour chaque indice de colonne $j$, $1 \le j\le 2^{\mathsf{N}}$, ${\mathsf{N}} = \sum_{1 \le i\le 2^{\mathsf{N}}} M_{ij}$: la matrice est stochastique à gauche; -\item Toutes les éléments de la somme $\sum_{1\le k\le 2^{\mathsf{N}}}M^k$ sont strictement positif, \textit{i.e.}, le graphe $\textsc{giu}(f)$ est fortement connexe; +\item Tous les éléments de la somme $\sum_{1\le k\le 2^{\mathsf{N}}}M^k$ sont strictement positifs, \textit{i.e.}, le graphe $\textsc{giu}(f)$ est fortement connexe; \end{enumerate} Ce problème s'exprime sur des domaines finis entiers avec des opérateurs arithmétiques simples (sommes et produits). Il pourrait théoriquement être @@ -69,7 +69,7 @@ ici pour $\mathsf{N} = 2$. Dans ce code, \verb+summ(+$X,Y,R$\verb+)+ valent True si et seulement si $R$ est le produit matriciel (ou la somme matricielle) -entre $X$ and $Y$ respectivement. +entre $X$ et $Y$ respectivement. Il n'est pas difficile d'adapter ce code à n'importe quelle valeur entière naturelle $\mathsf{N}$. @@ -120,7 +120,7 @@ Cette approche, basée sur une démarche de type \emph{générer, tester} ne peu pas être retenue pour $n$ de grande taille, même en s'appuyant sur l'efficience de l'algorithme de backtrack natif de PROLOG. -Cependant, pour des valeurs de $n$ petites, nous avons +Cependant, pour des petites valeurs de $n$, nous avons comparé les fonctions non équivalentes selon leur proportion à engendrer des temps de mélange petits (cf. équation~(\ref{eq:mt:ex})). @@ -162,9 +162,9 @@ $$ \end{table} \end{xpl} -Une analyse syntaxique de ces fonctions ne permet pas, à priori, +Une analyse syntaxique de ces fonctions ne permet pas, a priori, de déduire des règles permettant de construire de nouvelles -fonction dont le temps de mélange serait faible. +fonctions dont le temps de mélange serait faible. Cependant, le graphe $\textsc{giu}(f^*)$ (donné à la Figure~\ref{fig:iteration:f*}) est le $3$-cube dans lequel le cycle @@ -320,9 +320,9 @@ hamiltonien $c$. Aucun arc n'appartient à la fois à $r$ et à $c$: en effet, sinon $c$ contiendrait un n{\oe}ud deux fois. Ainsi aucune arête de $r$ n'est enlevée dans $C_1$. -Le cycle $r$ est évidement un cycle hamiltonien et contient tous les n{\oe}uds. -Tous les n{\oe}uds de $C_1$ dans lequel $c$ a été enlevé sont accessibles -depuis n'importe quel n{\oe}ud. Le graphe des itérations $\textsf{giu}$ qui +Le cycle $r$ est évidemment un cycle hamiltonien et contient tous les n{\oe}uds. +Tous les n{\oe}uds de $C_1$ dans lesquels $c$ a été enlevé sont accessibles +depuis n'importe quel n{\oe}ud. Le graphe des itérations $\textsc{giu}$ qui étend le précédent graphe est ainsi fortement connexe. \end{proof} @@ -435,17 +435,17 @@ deux premiers éléments qui ont été intervertis. L'étape~(\ref{item:nondet}) n'est pas constructive: il n'est pas précisé comment sélectionner des sous-séquences qui assurent que le code obtenu est équilibré. -La théorème suivante montre que c'est possible et sa preuve, -donnée en annexes~\ref{anx:generateur}, explique comment le faire. +Le théorème suivant montre que c'est possible et sa preuve, +donnée en annexe~\ref{anx:generateur}, explique comment le faire. \begin{restatable}[Existence d'un code de Gray équilibré]{theorem}{theograyequilibre} \label{prop:balanced} Soit $\mathsf{N}$ dans $\Nats^*$, et $a_{\mathsf{N}}$ défini par $a_{\mathsf{N}}= 2 \left\lfloor \dfrac{2^{\mathsf{N}}}{2\mathsf{N}} \right\rfloor$. -il existe une séquence $l$ dans l'étape~(\ref{item:nondet}) de l'extension -de l'algorithme de \emph{Robinson-Cohn} extension telle que -le nombres de transitions $\textit{TC}_{\mathsf{N}}(i)$ -sont tous $a_{\mathsf{N}}$ ou $a_{\mathsf{N}}+2$ +Il existe une séquence $l$ dans l'étape~(\ref{item:nondet}) de l'extension +de l'algorithme de \emph{Robinson-Cohn} telle que +les nombres de transitions $\textit{TC}_{\mathsf{N}}(i)$ +valent tous $a_{\mathsf{N}}$ ou $a_{\mathsf{N}}+2$ pour chaque $i$, $1 \le i \le \mathsf{N}$. \end{restatable} @@ -461,11 +461,11 @@ stratégie donnée. Tout d'abord, celles-ci peuvent être interprétées comme une marche le long d'un graphe d'itérations $\textsc{giu}(f)$ tel que le choix de tel ou tel arc est donné par la stratégie. -On remarque que ce graphe d'itération est toujours un sous graphe +On remarque que ce graphe d'itérations est toujours un sous graphe du ${\mathsf{N}}$-cube augmenté des boucles sur chaque sommet, \textit{i.e.}, les arcs $(v,v)$ pour chaque $v \in \Bool^{\mathsf{N}}$. -Ainsi, le travail ci dessous répond à la question de +Ainsi, le travail ci-dessous répond à la question de définir la longueur du chemin minimum dans ce graphe pour obtenir une distribution uniforme. Ceci se base sur la théorie des chaînes de Markov. @@ -513,7 +513,7 @@ On remarque que dans cette marche on reste sur place avec une probabilité égal à $\frac{1}{2}+\frac{1}{2\mathsf{N}}$ et l'on passe d'un sommet à son voisin lorsque c'est possible avec une probabilité $\frac{1}{2\mathsf{N}}$. Les probabilités usuelles que l'on appliquerait aux transitions de -l'algorithme~\ref{CI Algorithm} serait quant à elles uniformément égales +l'algorithme~\ref{CI Algorithm} seraient quant à elles uniformément égales à $\frac{1}{\mathsf{N}}$. Cette manière paresseuse d'itérer (puisqu'on reste plus souvent sur place) n'est donc pas équivalente à celle issue de l'algorithme. @@ -530,7 +530,7 @@ $$\tv{\pi-\mu}=\max_{A\subset \Bool^{\mathsf{N}}} |\pi(A)-\mu(A)|.$$ On sait que $$\tv{\pi-\mu}=\frac{1}{2}\sum_{X\in\Bool^{\mathsf{N}}}|\pi(X)-\mu(X)|.$$ De plus, si -$\nu$ est une distribution on $\Bool^{\mathsf{N}}$, on a +$\nu$ est une distribution sur $\Bool^{\mathsf{N}}$, on a $$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}.$$ Soit $P$ une matrice d'une chaîne de Markov sur $\Bool^{\mathsf{N}}$. @@ -545,8 +545,8 @@ et $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$ Intuitivement, $t_{\rm mix}(\varepsilon)$ est le nombre d'itérations nécessaire -pour être proche de la distribution stationnaire à $\varepsilon$ prêt, -peut importe la configuration de départ. On a le théorème suivant démontré en annexes~\ref{anx:generateur}. +pour être proche de la distribution stationnaire à $\varepsilon$ près, +peu importe la configuration de départ. On a le théorème suivant démontré en annexe~\ref{anx:generateur}. \begin{restatable}[Temps de mixage sans chemin hamiltonien]{theorem}{theotpsmix} @@ -577,7 +577,7 @@ pour chaque n{\oe}ud du $\mathsf{N}$-cube un arc entrant et un arc sortant sont supprimés. Le fait qu'on enlève un cycle hamiltonien et que ce dernier soit équilibré n'est pas pris en compte. -En intégrant cette contrainte, ce majorant pourrait être réduite. +En intégrant cette contrainte, ce majorant pourrait être réduit. En effet, le temps de mixage est en $\Theta(N\ln N)$ lors d'une marche aléatoire classique paresseuse dans le $\mathsf{N}$-cube. @@ -596,7 +596,7 @@ résume ces résultats. Dans celle-ci, un cercle représente une approximation $E[\ts]$ pour un $\mathsf{N}$ donné tandis que la courbe est une représentation de la fonction $x \mapsto 2x\ln(2x+8)$. On constate que l'approximation de $E[\ts]$ est largement inférieure -à le majorant quadratique donné au théorème~\ref{prop:stop} et que la conjecture +au majorant quadratique donné au théorème~\ref{prop:stop} et que la conjecture donnée au paragraphe précédent est sensée. @@ -695,8 +695,9 @@ Elle n'est donc pas rappelée. \begin{xpl} On reprend l'exemple donné à la section~\ref{sec:plc}. - Dans le $3$-cube, le cycle hamiltonien défini par la séquence - $000,100,101,001,011,111,110,010,000$ a été supprimé engendrant + On considère le cycle hamiltonien défini par la séquence + $000,100,101,001,011,111,110,010,000$. En supprimant celui-ci dans + le $3$-cube, cela engendre la fonction $f^*$ définie par $$f^*(x_1,x_2,x_3)= (x_2 \oplus x_3, \overline{x_1}.\overline{x_3} + x_1\overline{x_2}, @@ -827,7 +828,7 @@ fonctions qui ont été générées selon la méthode détaillée à la section~\ref{sec:hamiltonian}. Pour chaque nombre $n=3$, $4$, $5$ et $6$, tous les cycles hamiltoniens non isomorphes ont été générés. Pour les -valeur de $n=7$ et $8$, seules $10^{5}$ cycles ont été évalués. Parmi +valeur de $n=7$ et $8$, seuls $10^{5}$ cycles ont été évalués. Parmi toutes les fonctions obtenues en enlevant du $n$-cube ces cycles, n'ont été retenues que celles qui minimisaient le temps de mélange relatif à une valeur de $\epsilon$ fixée à $10^{-8}$ et pour un mode donné. @@ -837,7 +838,7 @@ colonne sous la variable $b$. La variable $b'$ reprend le temps de mélange pour l'algorithme~\ref{CI Algorithm}. On note que pour un nombre $n$ de bits fixé et un mode donné d'itérations, -il peut avoir plusieurs fonctions minimisant ce temps de mélange. De plus, comme ce temps +il peut y avoir plusieurs fonctions minimisant ce temps de mélange. De plus, comme ce temps de mélange est construit à partir de la matrice de Markov et que celle-ci dépend du mode, une fonction peut être optimale pour un mode et ne pas l'être pour l'autre (c.f. pour $n=5$). @@ -901,7 +902,7 @@ $$ \end{array} $$ \caption{Nombre moyen - d'appels à un générateurs binaire par bit généré}\label{table:marchevssaute} + d'appels à un générateur binaire par bit généré}\label{table:marchevssaute} \end{table} @@ -926,7 +927,7 @@ permet de générer la stratégie aléatoire. que la chaîne est considérée comme aléatoire avec une confiance de $99\%$. -Les tableau~\ref{fig:TEST:generalise} donnent +Les tableaux~\ref{fig:TEST:generalise} donnent une vision synthétique de ces expérimentations. Nous avons évalué les fonctions préfixées par $f$ (respectivement $g$) avec les générateurs issus des itérations @@ -936,10 +937,10 @@ générateurs passe avec succès le test de NIST. Interpréter ces résultats en concluant que ces générateurs sont -tous équivalents serait erroné: la meilleur des +tous équivalents serait erroné: la meilleure des méthodes basées sur le mode des itérations généralisées (pour $n=8$ par exemple) -est au moins deux fois plus rapide que la meilleur de celles qui +est au moins deux fois plus rapide que la meilleure de celles qui sont basées sur les itérations unaires.