X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/591062c8359275f37c6528d0fb3909479f6e4a6e..a48fbd2038acfb317a73d3db1fd158f3d4a11820:/14Secrypt.tex?ds=inline

diff --git a/14Secrypt.tex b/14Secrypt.tex
index 0465fcf..435e739 100644
--- a/14Secrypt.tex
+++ b/14Secrypt.tex
@@ -21,7 +21,7 @@ arête sortante et une arête entrante.
 % This part is addressed in the first section. Next, we analyse the first
 % results to provide a generation of DSSC matrices with small mixing times. 
 
-\section{Programmation logique par contraintes sur des domaines finis}
+\section{Programmation logique par contraintes sur des domaines finis}\label{sec:plc}
 Tout d'abord, soit ${\mathsf{N}}$ le nombre d'éléments. 
 Pour éviter d'avoir à gérer des fractions, on peut considérer que 
 les matrices (d'incidence) à générer ont des lignes et des colonnes dont les 
@@ -94,7 +94,7 @@ C'est évidemment une relation d'équivalence.
 
 
 
-\subsection{Analyse de l'approche}\label{sub:prng:ana}
+%\subsection{Analyse de l'approche}\label{sub:prng:ana}
 Exécutée sur un ordinateur personnelle, PROLOG trouve 
 en moins d'une seconde les
 49 solutions pour  $n=2$, 
@@ -235,25 +235,27 @@ M=\dfrac{1}{3} \left(
 
 
 
-\section{Graphes 
-  $\textsc{giu}(f)$ 
-  $\textsc{gig}(f)$ 
-  fortement connexes et doublement stochastiques}\label{sec:gen:dblstc}
-% Secrypt 14
+% section{Graphes 
+%   $\textsc{giu}(f)$ 
+%   $\textsc{gig}(f)$ 
+%   fortement connexes et doublement stochastiques}\label{sec:gen:dblstc}
+% %
+%Secrypt 14
 
 
 
 
-\subsection{Suppression des cycles hamiltoniens}
+\section{Suppression des cycles hamiltoniens}
 \label{sec:hamiltonian}
 
-Dans un premier temps, nous montrons en section~\ref{sub:removing:theory} que la
+Dans un premier temps, nous montrons %en section~\ref{sub:removing:theory} 
+que la
 suppression  d'un  cycle  hamiltonien   produit  bien  des  matrices  doublement
 stochastiques.   Nous  établissons  ensuite  le  lien avec  les  codes  de  Gray
 équilibrés.
 
-\subsubsection{Aspects théoriques}
-\label{sub:removing:theory}
+%\subsubsection{Aspects théoriques}
+%\label{sub:removing:theory}
 
 Nous donnons  deux résultats complémentaires, reliant la  suppression d'un cycle
 hamiltonien  du $n$-cube,  les matrices  doublement stochastiques  et  la forte
@@ -322,7 +324,7 @@ fixe ($n$),  dont les éléments successifs ne  différent que par un  seul bit.
 code  de  Gray est  \emph{cyclique}  si  le premier  élément  et  le dernier  ne
 différent que par un seul bit.
 
-\subsection{Lien avec les codes de Gray cycliques (totalement) équilibrés}
+\section{Lien avec les codes de Gray cycliques (totalement) équilibrés}
 \label{sub:gray}
 
 La borne  inférieure du  nombre de codes  de Gray  ($\left(\frac{n*\log2}{e \log
@@ -375,7 +377,7 @@ vérifiant $\sum_{i=1}^nNT_n(i) = 2^n$.
   ce code est totalement équilibré.
 \end{xpl}
 
-\subsection{Génération de codes de Gray équilibrés par induction}
+\section{Génération de codes de Gray équilibrés par induction}
 \label{sec:induction}
 
 Dans  leur  article de  2004~\cite{ZanSup04},  Zanten  et  Suparta proposent  un
@@ -572,9 +574,9 @@ chaque itération qu'un seul élément de $[n]$.
 On pourrait penser à un algorithme basé sur les itérations généralisées, 
 c'est-à-dire qui modifierait une partie des éléments de $[n]$ à chaque 
 itération.
-C'est l'algorithme~\ref{CI Algorithm:prng:g}.
+C'est l'algorithme~\ref{CI Algorithm:prng:g} donné ci-après.
 
-\begin{algorithm}[h]
+\begin{algorithm}[ht]
 %\begin{scriptsize}
 \KwIn{une fonction $f$, un nombre d'itérations $b$, 
 une configuration initiale $x^0$ ($n$ bits)}
@@ -610,10 +612,10 @@ généralisées.
   correspondante à ce graphe 
   et $M$ une matrice  $2^n\times 2^n$  
   définie par 
-  $M = \dfrac{1}{n} \check{M}$.
+  $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 
-  l'algorithme~\ref{CI Algorithm} suit une loi qui 
+  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.
 \end{theorem}
@@ -623,8 +625,8 @@ Elle n'est donc pas rappelée.
 
 \begin{xpl}
 
-  On reprend l'exemple donné à la section~\ref{sub:prng:ana}:
-  Dans le $3$-cube   cycle hamiltonien défini par la séquence
+  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 
   la fonction $f^*$ définie par 
   $$f^*(x_1,x_2,x_3)=
@@ -639,15 +641,15 @@ la figure~\ref{fig:markov:f*}.
 
 \begin{figure}[ht]
   \begin{center}
-    \subfigure[Graphe des itérations chaotiques de $f^*$.
+    \subfigure[Graphe $\textsc{gig}(f^*)$
     \label{fig:iteration:f*}]{
       \begin{minipage}{0.55\linewidth}
         \centering
         \includegraphics[width=\columnwidth]{images/iter_f}%
       \end{minipage}
     }%
-    \subfigure[Matrice de Markov du graphe d'itérations chaotiques de 
-    $f^*$\label{fig:markov:f*}]{%
+    \subfigure[Matrice de Markov associée au $\textsc{gig}(f^*)$
+    \label{fig:markov:f*}]{%
       \begin{minipage}{0.35\linewidth}
         \begin{scriptsize}
           \begin{center}
@@ -675,15 +677,15 @@ la figure~\ref{fig:markov:f*}.
       \end{minipage}
     }%
     \caption{Représentations de $f^*(x_1,x_2,x_3)=
-      (x_2 \oplus x_3, \overline{x_1}\overline{x_3} + x_1\overline{x_2},
-      \overline{x_1}\overline{x_3} + x_1x_2)$.}\label{fig1}
+      (x_2 \oplus x_3, \overline{x_1}.\overline{x_3} + x_1\overline{x_2},
+      \overline{x_1}.\overline{x_3} + x_1x_2)$.}\label{fig1}
   \end{center}
 \end{figure}
 \end{xpl}
 
 
 
-\begin{table}[table:functions]{Fonctions avec matrices DSCC et le plus faible temps de mélange.}
+\begin{table}[ht]
   \begin{center}
     \begin{scriptsize}
       \begin{tabular}{|c|l|c|c|}
@@ -733,14 +735,17 @@ la figure~\ref{fig:markov:f*}.
       \end{tabular}
     \end{scriptsize}
   \end{center}
+\label{table:functions}
+\caption{Fonctions avec matrices DSCC et le plus faible temps de mélange.}
+
 \end{table}
 
 Le  tableau~\ref{table:functions} reprend  une synthèse de 
 fonctions qui  ont été  générées selon  la méthode détaillée  
-à la  section~\ref{sec:gen:dblstc}.
-Pour  chaque nombre $n=3$,  $4$, $5$
-,$6$, tous  les cycles  hamiltoniens non isomorphes  ont été générés.   Pour les
-valeur de $n=7$ et $8$,  seules $10^{5}$ configurations ont été évaluées.  Parmi
+à 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
 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}$.  
@@ -757,51 +762,54 @@ le nombre d'éléments alors qu'il augmente dans l'approche initiale où
 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 
+de configurations qu'on ne peut pas atteindre en une itération est de: 
 \begin{itemize}
-\item $2^n-n$ en marchant, ce qui représente $\dfrac{2^n-n}{2^n} = 1-\dfrac{n}{2^n}$ 
+\item $2^n-n$ en unaire. Ceci représente un rapport de 
+  $\dfrac{2^n-n}{2^n} = 1-\dfrac{n}{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 suffisantes pour atteinte une déviation faible;
-\item $2^n-2^{n-1}$ en sautant, soit la moitié de toutes les configurations 
+  d'itérations nécessaires pour atteinte une déviation faible;
+\item $2^n-2^{n-1}$ dans le cas généralisé,
+  soit la moitié de toutes les configurations 
   quel que soit $n$; seul 1 bit reste constant tandis que tous les autres peuvent changer. Plus $n$ grandit, plus la proportion de bits constants diminue.
 \end{itemize}
 
-Cependant, dans le cas où l'on saute, chaque itération a une complexité 
-plus élevée puisqu'il est nécessaire d'invoquer un générateur 
-de nombres pseudo-aléatoires entre 1 et $2^{n}$ tandis qu'il suffit 
-d'avoir un générateur entre 1 et $n$ dans le premier cas.
+Cependant, dans le cas généralisé, chaque itération a une complexité 
+plus élevée puisqu'il est nécessaire d'invoquer un générateur
+produisant un nombre pseudo-aléatoire dans $[2^{n}]$ tandis qu'il suffit 
+que celui-ci soit dans $[n]$ dans le cas unaire.
+Pour comparer les deux approches, 
+on considère que le générateur aléatoire embarqué est binaire, \textit{i.e.} ne génère qu'un bit (0 ou 1).
 
-Pour comparer les deux approches, on considère que le générateur aléatoire embarqué est binaire, \textit{i.e.} ne génère qu'un bit (0 ou 1).
-
-Lorsqu'on marche et qu'on effectue $i$ itérations, 
-à chaque itération, la stratégie génère un nombre entre
-$1$ et $n$. 
-Elle fait donc $\ln(n)/\ln(2)$ appels à ce générateur en moyenne. 
-La démarche fait donc au total $i*\ln(n)/\ln(2)$ appels pour $n$ bits et
-donc $i*\ln(n)/(n*\ln(2))$ appels pour 1 bit généré en moyenne.
-Lorsqu'on saute et qu'on effectue $i'$ itérations, 
-à chaque itération, la stratégie génère un nombre entre
+Dans le cas généralisé, si l'on effectue $b$ itérations, 
+à chacune d'elles, la stratégie génère un nombre entre
 $1$ et $2^n$. Elle fait donc $n$ appels à ce générateur.
-On fait donc au total $i'*n$ appels pour $n$ bits et
-donc $i'$ appels pour 1 bit généré en moyenne.
+On fait donc au total $b*n$ appels pour $n$ bits et
+donc $b$ appels pour 1 bit généré en moyenne.
+Dans le cas unaire, si l'on effectue $b'$ itérations, 
+à chacune d'elle, la stratégie génère un nombre entre
+$1$ et $n$. 
+Elle fait donc $\ln(n)/\ln(2)$ appels à ce générateur binaire en moyenne. 
+La démarche fait donc au total $b'*\ln(n)/\ln(2)$ appels pour $n$ bits et
+donc $b'*\ln(n)/(n*\ln(2))$ appels pour 1 bit généré en moyenne.
 Le tableau~\ref{table:marchevssaute} donne des instances de 
 ces valeurs pour $n \in\{4,5,6,7,8\}$ et les fonctions  
-données au tableau~\ref{table:fonctions}.
-On constate que le nombre d'appels par bit généré décroit avec $n$ dans la 
-seconde démarche et est toujours plus faible que celui de la première.   
+données au tableau~\ref{table:functions}.
+On constate que le nombre d'appels par bit généré décroit avec $n$ dans le 
+cas des itérations généralisées et est toujours plus faible
+que celui des itérations unaires.
 
 
 
-\begin{table}
+\begin{table}[ht]
 $$
 \begin{array}{|l|l|l|l|l|l|}
 \hline
-\textrm{Algorithme} & 4 & 5 & 6 & 7 & 8 \\ 
+\textrm{Itérations} & 4 & 5 & 6 & 7 & 8 \\ 
 \hline
-\textrm{marchant}         &  19.0 & 22.2905097109  & 23.6954895899 & 25.2661942985 & 27.0\\  
+\textrm{Unaires}         &  19.0 & 22.2905097109  & 23.6954895899 & 25.2661942985 & 27.0\\  
 \hline
-\textrm{sautant}          &  17   & 13             & 11            & 10 & 9\\
+\textrm{Généralisées}          &  17   & 13             & 11            & 10 & 9\\
 \hline
 \end{array}
 $$
@@ -812,25 +820,35 @@ $$
 
 
 
-La qualité des séquences aléatoires a été évaluée à travers la suite 
-de tests statistiques développée pour les générateurs de nombres 
-pseudo-aléatoires par le 
+\section{Tests statistiques}
+
+La qualité des séquences aléatoires produites par 
+le générateur des itérations unaires ainsi que 
+celles issues des itérations généralisées a été évaluée à travers la suite 
+de tests statistiques développée par le 
 \emph{National Institute of Standards and Technology} (NIST).
  Pour les 15 tests, le seuil $\alpha$ est fixé à $1\%$:
  une  valeur  
  qui est plus grande que $1\%$  signifie 
  que la chaîne est considérée comme aléatoire avec une confiance de $99\%$.
+
+
+
+
  Le tableau~\ref{fig:TEST} donne une vision synthétique de toutes 
- les expérimentations. 
+ ces expérimentations. 
 L'expérience a montré notamment que toutes ces fonctions
 passent avec succès cette batterie de tests. 
 
+
+
+
 %%%%%%%%% Relancer pour n=6, n=7, n=8
 %%%%%%%%% Recalculer le MT
 %%%%%%%%% Regenerer les 10^6 bits
 %%%%%%%%% Evaluer sur NIST
  
-\begin{table}[fig:TEST]{Test de NIST réalisé sur les fonctions $f^*$ détaillées au tableau~\label{table:functions}.}
+\begin{table}[ht]
   \centering
   \begin{scriptsize}
     \begin{tabular}{|*{5}{c|}}
@@ -853,6 +871,9 @@ Série* (m=10)                 & 0.595 (0.995) & 0.289 (0.975) & 0.660 (0.995) &
 Complexité linaire            & 0.816 (1.0)   & 0.897 (0.98)  & 0.080 (0.98)  & 0.798 (1.0)   \\ \hline
     \end{tabular}
   \end{scriptsize}
+
+\label{fig:TEST}
+\caption{Test de NIST réalisé sur les fonctions $f^*$ détaillées au tableau~\label{table:functions}}
 \end{table}
 
 %