X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/01003216d61845263ad195f3ecf7334817d60407..c1f6ce3a24b92bfb8dd4da3d9092666c73adbcc9:/14Secrypt.tex?ds=inline diff --git a/14Secrypt.tex b/14Secrypt.tex index e36720b..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} @@ -371,7 +372,7 @@ plus, comme dans tout code de Gray cyclique, $\textit{TC}_n(i)$ est pair $\forall i\in\{1,...,n\}$, alors les systèmes ayant un nombre d'éléments différent de $2^k$, ne peuvent avoir que des codes de Gray équilibrés avec $\textit{TC}_n(i)=\lfloor\frac{2^n}{n}\rfloor$ ou -$\textit{NT}_n(i)=\lceil\frac{2^n}{n}\rceil, \forall i\in\{1,...,n\}$ et +$\textit{TC}_n(i)=\lceil\frac{2^n}{n}\rceil, \forall i\in\{1,...,n\}$ et vérifiant $\sum_{i=1}^n\textit{TC}_n(i) = 2^n$. \begin{xpl} @@ -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. @@ -509,10 +510,17 @@ P=\dfrac{1}{6} \left( \] \end{xpl} -On remarque que dans cette marche on reste sur place avec une probabilité - - +On remarque que dans cette marche on reste sur place avec une probabilité égale +à $\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} 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. +Cependant, l'étude théorique de référence~\cite{LevinPeresWilmer2006} +considère cette marche comme cadre. S'inspirant de +celle-ci, le travail suivant se replace donc dans ce cadre théorique. Tout d'abord, soit $\pi$ et $\mu$ deux distributions sur @@ -523,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}}$. @@ -536,73 +544,35 @@ $$d(t)=\max_{X\in\Bool^{\mathsf{N}}}\tv{P^t(X,\cdot)-\pi}$$ et $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$ - -Un résultat classique est - -$$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$ - - - - -Soit $(X_t)_{t\in \mathbb{N}}$ une suite de variables aléatoires de -$\Bool^{\mathsf{N}}$. -Une variable aléatoire $\tau$ dans $\mathbb{N}$ est un -\emph{temps d'arrêt} pour la suite -$(X_i)$ si pour chaque $t$ il existe $B_t\subseteq -(\Bool^{\mathsf{N}})^{t+1}$ tel que -$\{\tau=t\}=\{(X_0,X_1,\ldots,X_t)\in B_t\}$. -En d'autres termes, l'événement $\{\tau = t \}$ dépend uniquement des valeurs -de -$(X_0,X_1,\ldots,X_t)$, et non de celles de $X_k$ pour $k > t$. - -Soit $(X_t)_{t\in \mathbb{N}}$ une chaîne de Markov et -$f(X_{t-1},Z_t)$ une représentation fonctionnelle de celle-ci. -Un \emph{temps d'arrêt aléatoire} pour la chaîne de -Markov est un temps d'arrêt pour -$(Z_t)_{t\in\mathbb{N}}$. -Si la chaîne de Markov est irréductible et a $\pi$ -comme distribution stationnaire, alors un -\emph{temps stationnaire} $\tau$ est temps d'arrêt aléatoire -(qui peut dépendre de la configuration initiale $X$), -tel que la distribution de $X_\tau$ est $\pi$: -$$\P_X(X_\tau=Y)=\pi(Y).$$ - - -Un temps d'arrêt $\tau$ est qualifié de \emph{fort} si $X_{\tau}$ -est indépendant de $\tau$. On a les deux théorèmes suivants, dont les -démonstrations sont données en annexes~\ref{anx:generateur}. +Intuitivement, $t_{\rm mix}(\varepsilon)$ est le nombre d'itérations nécessaire +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{theorem} -Si $\tau$ est un temps d'arrêt fort, alors $d(t)\leq \max_{X\in\Bool^{\mathsf{N}}} -\P_X(\tau > t)$. -\end{theorem} - - -Soit alors $\ov{h} : \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ la fonction -telle que pour $X \in \Bool^{\mathsf{N}} $, -$(X,\ov{h}(X)) \in E$ et $X\oplus\ov{h}(X)=0^{{\mathsf{N}}-h(X)}10^{h(X)-1}$. -La fonction $\ov{h}$ est dite {\it anti-involutive} si pour tout $X\in \Bool^{\mathsf{N}}$, -$\ov{h}(\ov{h}(X))\neq X$. +\begin{restatable}[Temps de mixage sans chemin hamiltonien]{theorem}{theotpsmix} +\label{theo:tmps:mix} +On considère un $\mathsf{N}$-cube dans lequel un chemin hamiltonien a été supprimé et la fonction de +probabilités $p$ définie sur l'ensemble des arcs comme suit: +\[ +p(e) \left\{ +\begin{array}{ll} += \frac{1}{2} + \frac{1}{2\mathsf{N}} \textrm{ si $e=(v,v)$ avec $v \in \Bool^{\mathsf{N}}$,}\\ += \frac{1}{2\mathsf{N}} \textrm{ sinon.} +\end{array} +\right. +\] +La chaîne de Markov associée converge vers la distribution uniforme et -\begin{restatable}[Majoration du temps d'arrêt]{theorem}{theostopmajorant} -\label{prop:stop} -Si $\ov{h}$ est bijective et anti involutive -$\ov{h}(\ov{h}(X))\neq X$, alors -$E[\ts]\leq 8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1)$. +\[ +\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} -Les détails de la preuve sont donnés en annexes~\ref{anx:generateur}. -On remarque tout d'abord que la chaîne de Markov proposée ne suit pas exactement -l'algorithme~\ref{CI Algorithm}. En effet dans la section présente, -la probabilité de rester dans une configuration donnée -est fixée à $\frac{1}{2}+\frac{1}{2n}$. -Dans l'algorithme initial, celle-ci est de $\frac{1}{n}$. -Cette version, qui reste davantage sur place que l'algorithme original, -a été introduite pour simplifier le calcul d'un majorant -du temps d'arrêt. Sans entrer dans les détails de la preuve, on remarque aussi @@ -611,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. @@ -620,7 +590,7 @@ dans le contexte du $\mathsf{N}$-cube privé d'un chemin hamiltonien. On peut évaluer ceci pratiquement: pour une fonction $f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ et une graine initiale -$x^0$, le code donné à l'algorithme ~\ref{algo:stop} retourne le +$x^0$, le code donné à l'algorithme~\ref{algo:stop} retourne le nombre d'itérations suffisant tel que tous les éléments $\ell\in \llbracket 1,{\mathsf{N}} \rrbracket$ sont équitables. Il permet de déduire une approximation de $E[\ts]$ en l'instanciant un grand nombre de fois: pour chaque nombre $\mathsf{N}$, $ 3 \le \mathsf{N} \le 16$, 10 fonctions ont été générées comme dans @@ -630,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. @@ -654,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} @@ -717,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. @@ -729,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}, @@ -861,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é. @@ -871,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$). @@ -885,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; @@ -935,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} @@ -960,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 @@ -970,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. @@ -1090,7 +1061,7 @@ Complexité linaire& 0.005 (0.98)& 0.534 (0.99)& 0.085 (0.97)& 0.996 (1.0)\\ \hl \section{Conclusion} -Ce chaptitre a montré comment construire un PRNG chaotique, notamment à partir +Ce chapitre a montré comment construire un PRNG chaotique, notamment à partir de codes de Gray équilibrés. Une méthode complètement automatique de construction de ce type de codes a été présentée étendant les méthodes existantes.