X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/523864c862215a63c5133568a9771f5b8f60c89e..44a56c5eb4a1dfdf7dc67735c5c00f478cef2ede:/14Secrypt.tex

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.
 
 
