X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/523864c862215a63c5133568a9771f5b8f60c89e..fcbc9202a51285ff17060f4d330eca0d57b2a3c1:/14Secrypt.tex?ds=inline diff --git a/14Secrypt.tex b/14Secrypt.tex index 858a8e5..b499f1b 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 @@ -20,10 +20,11 @@ une distribution uniforme est étudiée théoriquement et pratiquement à la section~\ref{sec:mixing}. L'extension du travail aux itérations généralisées est présentée à 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 +Finalement, des instances de PRNGs engendrés selon les méthodes détaillées dans +ce chapitre sont présentées en section~\ref{sec:prng;gray:tests}. +Les sections~\ref{sec:plc} à~\ref{sub:gray} ont été publiées à~\cite{chgw+14:oip}. +La section~\ref{sec:mixing} est publiée dans~\cite{ccgh16}. % This aim of this section is to show @@ -49,13 +50,13 @@ On cherche ainsi toutes les matrices $M$ de taille $2^{\mathsf{N}}\times 2^{\ma configuration $i$ est inférieur à ${\mathsf{N}}$; \item pour $j \neq i$, $0 \le M_{ij} \le 1$: on construit l'arc de $i$ à $j$ -si et seulement si $M_{ij}$ vaut 1 (et 0 sinon) +si et seulement si $M_{ij}$ vaut 1 (et 0 sinon); \item pour chaque indice de ligne $i$, $1 \le i\le 2^{\mathsf{N}}$, ${\mathsf{N}} = \sum_{1 \le j\le 2^{\mathsf{N}}} M_{ij}$: 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 +70,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 +121,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 +163,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 +321,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} @@ -407,7 +408,7 @@ Enfin, les auteurs de~\cite{ZanSup04} présentent une extension de l'algorithme principalement de prouver que si $\mathsf{N}$ est une puissance de 2, le code de Gray équilibré engendré par l'extension est toujours totalement équilibré et que $S_{\mathsf{N}}$ est la séquence de transition d'un code de Gray de $\mathsf{N}$ bits -si $S_{\mathsf{N}-2}$ l'est aussi.. +si $S_{\mathsf{N}-2}$ l'est aussi. Cependant les auteurs ne prouvent pas que leur approche fournit systématiquement un code de Gray (totalement) équilibré. Cette section montre que ceci est vrai en rappelant tout d'abord @@ -435,17 +436,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 +462,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 +514,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 +531,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 +546,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} @@ -565,7 +566,10 @@ p(e) \left\{ La chaîne de Markov associée converge vers la distribution uniforme et \[ -\forall \varepsilon >0,\, t_{\rm mix}(\varepsilon) \le 32 {\mathsf{N}}^2+ 16{\mathsf{N}}\ln ({\mathsf{N}}+1) = O(N^2). +\forall \varepsilon >0,\, t_{\rm mix}(\varepsilon) \le +x +\leq \lceil\log_2(\varepsilon^{-1}) +(32 {\mathsf{N}}^2+ 16{\mathsf{N}}\ln ({\mathsf{N}}+1)) \] \end{restatable} @@ -577,7 +581,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 +600,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. @@ -620,7 +624,7 @@ $\textit{fair}\leftarrow\emptyset$\; } \Return{$\textit{nbit}$}\; %\end{scriptsize} -\caption{Pseudo Code pour évaluer le temps d'arrêt} +\caption{Pseudo-code pour évaluer le temps d'arrêt} \label{algo:stop} \end{algorithm} @@ -683,7 +687,7 @@ généralisées. définie par $M = \dfrac{1}{2^n} \check{M}$. Si $\textsc{gig}(f)$ est fortement connexe, alors - la sortie du générateur de nombres pseudo aléatoires détaillé par + la sortie du générateur de nombres pseudo-aléatoires détaillé par l'algorithme~\ref{CI Algorithm:prng:g} suit une loi qui tend vers la distribution uniforme si et seulement si $M$ est une matrice doublement stochastique. @@ -695,8 +699,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 +832,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 +842,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$). @@ -851,8 +856,8 @@ l'on marche. Cela s'explique assez simplement. Depuis une configuration initiale, le nombre de configurations qu'on ne peut pas atteindre en une itération est de: \begin{itemize} -\item $2^n-n$ en unaire. Ceci représente un rapport de - $\dfrac{2^n-n}{2^n} = 1-\dfrac{n}{2^n}$ +\item $2^n-n-1$ en unaire. Ceci représente un rapport de + $\dfrac{2^n-n-1}{2^n} = 1-\dfrac{n-1}{2^n}$ de toutes les configurations; plus $n$ est grand, plus ce nombre est proche de $1$, et plus grand devient le nombre d'itérations nécessaires pour atteinte une déviation faible; @@ -901,7 +906,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 +931,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 +941,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.