ajout de quelques tex

[hdrcouchot.git] / 14Secrypt.tex

diff --git a/14Secrypt.tex b/14Secrypt.tex
index 5e4cafc4272a23dbcf3348975b5b5cec818ea973..b499f1b1975fcc6b7e925e6a21ca9d535721fe8c 100644 (file)
--- a/14Secrypt.tex
+++ b/14Secrypt.tex
@@ -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}.
 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}.
 à~\cite{chgw+14:oip}.

+La section~\ref{sec:mixing} est publiée dans~\cite{ccgh16}.

 
 
 % This aim of this section is to show 
 
 
 % This aim of this section is to show 


@@ -49,7 +50,7 @@ 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$ 
 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$, 
 \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$, 


@@ -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 
 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
 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


@@ -565,7 +566,10 @@ p(e) \left\{
 La chaîne de Markov associée converge vers la distribution uniforme et 
 
 \[
 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}
 
 \] 
 \end{restatable}
 


@@ -620,7 +624,7 @@ $\textit{fair}\leftarrow\emptyset$\;
 }
 \Return{$\textit{nbit}$}\;
 %\end{scriptsize}
 }
 \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}
 
 \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 
   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.
   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.


@@ -852,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}
 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;
   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;