ajout de compartif sauter marcher

diff --git a/14Secrypt.tex b/14Secrypt.tex
index a04c11e1ecd22083d519676152f5147904105f76..0465fcf11ad89af128d3156c80e11744b5fdccc0 100644 (file)
--- a/14Secrypt.tex
+++ b/14Secrypt.tex
@@ -94,7 +94,7 @@ C'est évidemment une relation d'équivalence.
 
 
 
 
 
 

-\subsection{Analyse de l'approche}
+\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$, 
 Exécutée sur un ordinateur personnelle, PROLOG trouve 
 en moins d'une seconde les
 49 solutions pour  $n=2$, 


@@ -114,7 +114,7 @@ comparé les fonctions non équivalentes selon leur proportion
 
 
 
 
 
 

-\begin{xpl}
+\begin{xpl}\label{xpl:mixing:3}

 Le tableau~\ref{table:mixing:3} fournit les 5 fonctions booléennes 
 qui ont les temps de mélange les plus petits pour $\varepsilon=10^{-5}$. 
 \begin{table}[ht]
 Le tableau~\ref{table:mixing:3} fournit les 5 fonctions booléennes 
 qui ont les temps de mélange les plus petits pour $\varepsilon=10^{-5}$. 
 \begin{table}[ht]


@@ -126,13 +126,13 @@ $$
 \hline
 f^a &  (x_2 \oplus x_3, x_1 \oplus \overline{x_3},\overline{x_3})  &  16   \\
 \hline
 \hline
 f^a &  (x_2 \oplus x_3, x_1 \oplus \overline{x_3},\overline{x_3})  &  16   \\
 \hline

-f^*  &  (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)  &  17   \\
+f^*  &  (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)  &  17   \\

 \hline
 \hline

-f^b  &  (\overline{x_1}(x_2+x_3) + x_2x_3,\overline{x_1}(\overline{x_2}+\overline{x_3}) + \overline{x_2}\overline{x_3}, &  \\
+f^b  &  (\overline{x_1}(x_2+x_3) + x_2x_3,\overline{x_1}(\overline{x_2}+\overline{x_3}) + \overline{x_2}.\overline{x_3}, &  \\

 & \qquad \overline{x_3}(\overline{x_1}+x_2) + \overline{x_1}x_2)  &  26   \\
 \hline
 & \qquad \overline{x_3}(\overline{x_1}+x_2) + \overline{x_1}x_2)  &  26   \\
 \hline

-f^c  &  (\overline{x_1}(x_2+x_3) + x_2x_3,\overline{x_1}(\overline{x_2}+\overline{x_3}) + \overline{x_2}\overline{x_3}, & \\
+f^c  &  (\overline{x_1}(x_2+x_3) + x_2x_3,\overline{x_1}(\overline{x_2}+\overline{x_3}) + \overline{x_2}.\overline{x_3}, & \\

 & \overline{x_3}(\overline{x_1}+x_2) + \overline{x_1}x_2)  &  29   \\
 \hline
 f^d  &  (x_1\oplus x_2,x_3(\overline{x_1}+\overline{x_2}),\overline{x_3})  &  30   \\
 & \overline{x_3}(\overline{x_1}+x_2) + \overline{x_1}x_2)  &  29   \\
 \hline
 f^d  &  (x_1\oplus x_2,x_3(\overline{x_1}+\overline{x_2}),\overline{x_3})  &  30   \\


@@ -182,32 +182,53 @@ On s'intéresse  par la suite à la génération de ce genre de cycles.
       \begin{minipage}{0.35\linewidth}
         \begin{scriptsize}
           \begin{center}
       \begin{minipage}{0.35\linewidth}
         \begin{scriptsize}
           \begin{center}

-            $ \dfrac{1}{4} \left(
-              \begin{array}{cccccccc}
-                1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
+
+\[
+M=\dfrac{1}{3} \left(
+\begin{array}{llllllll}
+1&1&1&0&0&0&0&0 \\
+1&1&0&0&0&1&0&0 \\
+0&0&1&1&0&0&1&0 \\
+0&1&1&1&0&0&0&0 \\
+1&0&0&0&1&0&1&0 \\
+0&0&0&0&1&1&0&1 \\
+0&0&0&0&1&0&1&1 \\
+0&0&0&1&0&1&0&1 
+\end{array}
+\right)
+\]
+
+
+
+            % $ \dfrac{1}{4} \left(
+            %   \begin{array}{cccccccc}
+            %     1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\

               
               

-                1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\
+            %     1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\

               
               

-                0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\
+            %     0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\

               
               

-                1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
+            %     1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\

               
               

-                1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\
+            %     1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\

               
               

-                0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
+            %     0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\

               
               

-                0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
+            %     0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\

               
               

-                0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\
+            %     0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\

               
               

-              \end{array}            \right) $
+            %   \end{array}            \right) $
+
+
+

           \end{center}
         \end{scriptsize}
       \end{minipage}
     }%
     \caption{Représentations de $f^*(x_1,x_2,x_3)=
           \end{center}
         \end{scriptsize}
       \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{center}
 \end{figure}
 


@@ -217,7 +238,7 @@ On s'intéresse  par la suite à la génération de ce genre de cycles.
 \section{Graphes 
   $\textsc{giu}(f)$ 
   $\textsc{gig}(f)$ 
 \section{Graphes 
   $\textsc{giu}(f)$ 
   $\textsc{gig}(f)$ 

-  fortement connexes et doublement stochastiques}
+  fortement connexes et doublement stochastiques}\label{sec:gen:dblstc}

 % Secrypt 14
 
 
 % Secrypt 14
 
 


@@ -293,8 +314,8 @@ depuis n'importe quel n{\oe}ud. Le graphe des itérations $\textsf{giu}$ qui
 
 
 
 
 
 

-Les preuves, relativement directes, sont  laissées en exercices au lecteur.  Par
-contre, ce qui  est moins aisé est la génération de  cycles hamiltoniens dans le
+%Les preuves, relativement directes, sont  laissées en exercices au lecteur.  
+La génération de  cycles hamiltoniens dans le

 $n$-cube,  ce qui  revient à  trouver des  \emph{codes de  Gray  cycliques}.  On
 rappelle que  les codes de  Gray sont des  séquences de mots binaires  de taille
 fixe ($n$),  dont les éléments successifs ne  différent que par un  seul bit. Un
 $n$-cube,  ce qui  revient à  trouver des  \emph{codes de  Gray  cycliques}.  On
 rappelle que  les codes de  Gray sont des  séquences de mots binaires  de taille
 fixe ($n$),  dont les éléments successifs ne  différent que par un  seul bit. Un


@@ -524,11 +545,24 @@ $\ov{h}(\ov{h}(X))\neq X$, alors
 $E[\ts]\leq 8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1)$. 
 \end{theorem}
 
 $E[\ts]\leq 8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1)$. 
 \end{theorem}
 

-Sans entrer dans les détails de la preuve, on remarque que le calcul 
-de cette borne ne tient pas en compte le fait qu'on préfère enlever des 
+Sans entrer dans les détails de la preuve, on remarque tout d'abord 
+que le calcul 
+de cette borne n'intègre pas le fait qu'on préfère enlever des 

 chemins hamiltoniens équilibrés. 
 En intégrant cette contrainte, la borne supérieure pourrait être réduite.
 
 chemins hamiltoniens équilibrés. 
 En intégrant cette contrainte, la borne supérieure pourrait être réduite.
 

+On remarque ensuite 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 ${1}{n}$.
+Cette version, qui reste davantage sur place que l'algorithme original,
+a été introduite pour simplifier le calcul de la borne sup 
+du temps d'arrêt.   
+
+
+
+

 \section{Et les itérations généralisées?}
 Le chaptire précédent a présenté un algorithme de 
 PRNG construit à partir d'itérations unaires. 
 \section{Et les itérations généralisées?}
 Le chaptire précédent a présenté un algorithme de 
 PRNG construit à partir d'itérations unaires. 


@@ -567,4 +601,258 @@ Par exemple, pour $n=3$, l'ensemble $\textit{Set}(6)$ vaudraitt $\{3,2\}$.
 On remarque aussi que l'argument de la fonction  $\textit{Random}$
 passe de $n$ à $2^n$.
 
 On remarque aussi que l'argument de la fonction  $\textit{Random}$
 passe de $n$ à $2^n$.
 

+On a le théorème suivant qui étend le théorème~\ref{thm:prng:u} aux itérations
+généralisées.
+
+\begin{theorem}\label{thm:prng:g}
+  Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\textsc{gig}(f)$ son 
+  graphe des itérations généralisées, $\check{M}$ la matrice d'adjacence
+  correspondante à ce graphe 
+  et $M$ une matrice  $2^n\times 2^n$  
+  définie par 
+  $M = \dfrac{1}{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 
+  tend vers la distribution uniforme si 
+  et seulement si  $M$ est une matrice doublement stochastique.
+\end{theorem}
+
+La preuve de ce théorème est la même que celle du théorème~\ref{thm:prng:u}.
+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
+  $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)=
+  (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).
+$$ 
+
+Le graphe  $\textsc{gig}(f^*)$  est représenté à la 
+Figure~\ref{fig:iteration:f*}.
+La matrice de Markov $M$ correspondante est donnée à 
+la figure~\ref{fig:markov:f*}.
+
+\begin{figure}[ht]
+  \begin{center}
+    \subfigure[Graphe des itérations chaotiques de $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*}]{%
+      \begin{minipage}{0.35\linewidth}
+        \begin{scriptsize}
+          \begin{center}
+            $ \dfrac{1}{4} \left(
+              \begin{array}{cccccccc}
+                1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
+              
+                1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\
+              
+                0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\
+              
+                1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
+              
+                1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\
+              
+                0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
+              
+                0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
+              
+                0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\
+              
+              \end{array}            \right) $
+          \end{center}
+        \end{scriptsize}
+      \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}
+  \end{center}
+\end{figure}
+\end{xpl}
+
+
+
+\begin{table}[table:functions]{Fonctions avec matrices DSCC et le plus faible temps de mélange.}
+  \begin{center}
+    \begin{scriptsize}
+      \begin{tabular}{|c|l|c|c|}
+        \hline
+        fonction  & $f(x)$, $f(x)$ pour $x \in [0,1,2,\hdots,2^n-1]$                 & $b$ & $b'$ \\ 
+        \hline
+        $f^{*4}$  & [13,10,9,14,3,11,1,12,15,4,7,5,2,6,0,8]                          & 17  & 38   \\
+        \hline
+        $f^{*5}$  & [29, 22, 25, 30, 19, 27, 24, 16, 21, 6, 5, 28, 23, 26, 1,        & 13  & 48   \\
+                  & 17, 31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 7, 20, 11, 18, 0, 4]     &     &      \\
+        \hline
+        $f^{*6}$  & [55, 60, 45, 44, 58, 62, 61, 48, 53, 50, 52, 36, 59, 34, 33,     & 11   & 55   \\
+                  & 49, 15, 42, 47, 46, 35, 10, 57, 56, 7, 54, 39, 37, 51, 2, 1,     &     &      \\
+                  & 40, 63, 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22,      &     &      \\
+                  & 16, 24, 13, 12, 29, 8, 43, 14, 41, 0, 5, 38, 4, 6, 11, 3, 9, 32] &     &      \\
+         \hline
+         $f^{*7}$ & [111, 94, 93, 116, 122, 114, 125, 88, 87, 126, 119, 84, 123,     & 10   & 63   \\
+                  & 98, 81, 120, 109, 106, 105, 110, 99, 107, 104, 108, 101, 70,     &     &      \\ 
+                  & 117, 96, 67, 102, 113, 64, 79, 30, 95, 124, 83, 91, 121, 24,     &     &      \\ 
+                  & 23, 118, 69, 20, 115, 90, 17, 112, 77, 14, 73, 78, 74, 10, 72,   &     &      \\ 
+                  & 76, 103, 6, 71, 100, 75, 82, 97, 0, 127, 54, 57, 62, 51, 59,     &     &      \\ 
+                  & 56, 48, 53, 38, 37, 60, 55, 58, 33, 49, 63, 44, 47, 40, 42,      &     &      \\ 
+                  & 46, 45, 41, 35, 34, 39, 52, 43, 50, 32, 36, 29, 28, 61, 92,      &     &      \\ 
+                  & 26, 18, 89, 25, 19, 86, 85, 4, 27, 2, 16, 80, 31, 12, 15, 8,     &     &      \\ 
+                  & 3, 11, 13, 9, 5, 22, 21, 68, 7, 66, 65, 1]                       &     &      \\
+        \hline
+        $f^{*8}$  &[223, 190, 249, 254, 187, 251, 233, 232, 183, 230, 247, 180,&        9 & 72    \\
+                 & 227, 178, 240, 248, 237, 236, 253, 172, 203, 170, 201, 168, &&\\
+                 & 229, 166, 165, 244, 163, 242, 241, 192, 215, 220, 205, 216, &&\\
+                 & 218, 222, 221, 208, 213, 210, 212, 214, 219, 211, 217, 209, &&\\
+                 & 239, 202, 207, 140, 139, 234, 193, 204, 135, 196, 199, 132, &&\\
+                 & 194, 130, 225, 200, 159, 62, 185, 252, 59, 250, 169, 56, 191,&&\\
+                 & 246, 245, 52, 243, 50, 176, 48, 173, 238, 189, 44, 235, 42, &&\\
+                 & 137, 184, 231, 38, 37, 228, 35, 226, 177, 224, 151, 156, 141,&&\\
+                 & 152, 154, 158, 157, 144, 149, 146, 148, 150, 155, 147, 153, &&\\
+                 & 145, 175, 206, 143, 136, 11, 142, 129, 8, 7, 198, 197, 4, 195, &&\\
+                 & 2, 161, 160, 255, 124, 109, 108, 122, 126, 125, 112, 117, 114, &&\\
+                 & 116, 100, 123, 98, 97, 113, 79, 106, 111, 110, 99, 74, 121, 120,&&\\
+                 & 71, 118, 103, 101, 115, 66, 65, 104, 127, 90, 89, 94, 83, 91, 81,&&\\
+                 & 92, 95, 84, 87, 85, 82, 86, 80, 88, 77, 76, 93, 72, 107, 78, 105, &&\\
+                 & 64, 69, 102, 68, 70, 75, 67, 73, 96, 55, 58, 45, 188, 51, 186, 61, &&\\
+                 & 40, 119, 182, 181, 53, 179, 54, 33, 49, 15, 174, 47, 60, 171, && \\
+                 & 46, 57, 32, 167, 6, 36, 164, 43, 162, 1, 0, 63, 26, 25, 30, 19,&&\\
+                 & 27, 17, 28, 31, 20, 23, 21, 18, 22, 16, 24, 13, 10, 29, 14, 3, &&\\
+                 &138, 41, 12, 39, 134, 133, 5, 131, 34, 9, 128]&&\\
+        \hline
+      \end{tabular}
+    \end{scriptsize}
+  \end{center}
+\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
+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}$.  
+Ce  nombre d'itérations (\textit{i.e.}, ce temps de mélange) 
+est stocké dans la troisième
+colonne sous la variable $b$.  
+La variable $b'$ reprend le temps de mélange pour
+l'algorithme~\ref{CI Algorithm}.
+
+Un premier  résultat est  que ce nouvel  algorithme réduit grandement  le nombre
+d'itérations  suffisant pour  obtenir une  faible  déviation par  rapport à  une
+distribution uniforme.  On constate de  plus que ce nombre décroit avec
+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 
+\begin{itemize}
+\item $2^n-n$ en marchant, ce qui représente $\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 
+  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.
+
+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
+$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.
+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.   
+
+
+
+\begin{table}
+$$
+\begin{array}{|l|l|l|l|l|l|}
+\hline
+\textrm{Algorithme} & 4 & 5 & 6 & 7 & 8 \\ 
+\hline
+\textrm{marchant}         &  19.0 & 22.2905097109  & 23.6954895899 & 25.2661942985 & 27.0\\  
+\hline
+\textrm{sautant}          &  17   & 13             & 11            & 10 & 9\\
+\hline
+\end{array}
+$$
+\caption{Nombre moyen 
+  d'appels à un générateurs binaire par bit généré}\label{table:marchevssaute}
+\end{table}
+
+
+
+
+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 
+\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. 
+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}.}
+  \centering
+  \begin{scriptsize}
+    \begin{tabular}{|*{5}{c|}}
+      \hline
+Test                          & $f^{*4}$      & $f^{*5}$      & $f^{*6}$      & $f^{*7}$      \\ \hline
+Fréquence (Monobit)           & 0.025 (0.99)  & 0.066 (1.0)   & 0.319 (0.99)  & 0.001 (1.0)   \\ \hline  
+Fréquence / bloc              & 0.401 (0.99)  & 0.867 (1.0)   & 0.045 (0.99)  & 0.085 (0.99)  \\ \hline
+Somme Cumulé*                 & 0.219 (0.995) & 0.633 (1.0)   & 0.635 (1.0)   & 0.386 (0.99)  \\ \hline 
+Exécution                     & 0.964 (0.98)  & 0.699 (0.99)  & 0.181 (0.99)  & 0.911 (0.98)  \\ \hline 
+Longue exécution dans un bloc & 0.137 (0.99)  & 0.964 (1.0)   & 0.145 (0.99)  & 0.162 (0.98)  \\ \hline 
+Rang                          & 0.616 (0.99)  & 0.678 (1.0)   & 0.004 (1.0)   & 0.816 (1.0)   \\ \hline 
+Fourier rapide                & 0.048 (0.99)  & 0.637 (0.97)  & 0.366 (0.99)  & 0.162 (0.99)  \\ \hline 
+Patron sans superposition*    & 0.479 (0.988) & 0.465 (0.989) & 0.535 (0.989) & 0.499 (0.989) \\ \hline 
+Patron avec superposition     & 0.897 (1.0)   & 0.657 (0.97)  & 0.897 (0.98)  & 0.236 (0.99)  \\ \hline 
+Statistiques universelles     & 0.991 (0.98)  & 0.657 (0.98)  & 0.102 (0.98)  & 0.719 (0.98)  \\ \hline 
+Entropie approchée (m=10)     & 0.455 (1.0)   & 0.964 (1.0)   & 0.162 (1.0)   & 0.897 (0.98)  \\ \hline 
+Suite aléatoire *             & 0.372 (0.993) & 0.494 (0.986) & 0.243 (0.992) & 0.258 (0.993) \\ \hline 
+Suite aléatoire variante *    & 0.496 (0.989) & 0.498 (0.992) & 0.308 (0.983) & 0.310 (0.999) \\ \hline 
+Série* (m=10)                 & 0.595 (0.995) & 0.289 (0.975) & 0.660 (0.995) & 0.544 (0.99)  \\ \hline 
+Complexité linaire            & 0.816 (1.0)   & 0.897 (0.98)  & 0.080 (0.98)  & 0.798 (1.0)   \\ \hline
+    \end{tabular}
+  \end{scriptsize}
+\end{table}

 
 

+%

diff --git a/15RairoGen.tex b/15RairoGen.tex
index a1b6b23f593a237557b641262d875ad73b252370..f85d8b8c2dc4a2dba0a2f172144eda81be72723d 100644 (file)
--- a/15RairoGen.tex
+++ b/15RairoGen.tex
@@ -177,7 +177,8 @@ que cela l'est pour $h$.
       \end{minipage}
       \label{fig:h:iter}
     }    \end{center}
       \end{minipage}
       \label{fig:h:iter}
     }    \end{center}

-    \caption{Graphes d'itérations de fonctions booléennes dans $\Bool^2$}
+    \caption{Graphes des itérations unaires 
+      de fonctions booléennes dans $\Bool^2$}

     \label{fig:xplgraphIter}
   \end{figure}
 
     \label{fig:xplgraphIter}
   \end{figure}
 


@@ -294,10 +295,12 @@ ait une distribution suffisamment proche de la distribution uniforme.
 
 On énonce directement le théorème suivant dont la preuve est donnée en annexes~\ref{anx:generateur}.
 
 
 On énonce directement le théorème suivant dont la preuve est donnée en annexes~\ref{anx:generateur}.
 

-\begin{theorem}
+\begin{theorem}\label{thm:prng:u}

   Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\textsc{giu}(f)$ son 
   graphe d'itérations , $\check{M}$ sa matrice d'adjacence
   Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\textsc{giu}(f)$ son 
   graphe d'itérations , $\check{M}$ sa matrice d'adjacence

-  et $M$ une matrice  $2^n\times 2^n$  définie comme dans le lemme précédent.
+  et $M$ une matrice  $2^n\times 2^n$  
+  définie par 
+  $M = \dfrac{1}{n} \check{M}$.

   Si $\textsc{giu}(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 
   Si $\textsc{giu}(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 

diff --git a/demandeInscription/fiche-navette-autorisation-inscription-hdr.doc b/demandeInscription/fiche-navette-autorisation-inscription-hdr.doc
index 16da0fbd9b415e1b58d10cd953e508d0126a5439..851505e284a667ab6fef2f122d7f4775227bdf6a 100644 (file)
Binary files a/demandeInscription/fiche-navette-autorisation-inscription-hdr.doc and b/demandeInscription/fiche-navette-autorisation-inscription-hdr.doc differ

diff --git a/demandeInscription/synthese.tex b/demandeInscription/synthese.tex
index 2fbc80e7b2dc2a53e42913ccc816b877bd010e9b..791646a6f10450fead6f8dcfa52ff6049dfb8589 100755 (executable)
--- a/demandeInscription/synthese.tex
+++ b/demandeInscription/synthese.tex
@@ -148,7 +148,9 @@ Je suis membre de l'équipe Algorithmique Numérique Distribuée (AND) du
 Département d'Informatique des Systèmes Complexes (DISC)
 du laboratoire FEMTO-ST. 
 Je relève de l'école doctorale 37 Sciences Pour l'Ingénieur et Microtechniques (SPIM) de l'UFC.
 Département d'Informatique des Systèmes Complexes (DISC)
 du laboratoire FEMTO-ST. 
 Je relève de l'école doctorale 37 Sciences Pour l'Ingénieur et Microtechniques (SPIM) de l'UFC.

-Les avis du directeur de recherche, du directeur de l'équipe, du directeur de l'école doctorale et du directeur du département sont donnés en annexes. 
+Mon directeur de recherche pour cette HDR est Pr. J. {\sc Bahi} 
+du département DISC. Son avis, ainsi que celui du directeur de l'équipe (Pr. R. {\sc Couturier}, du directeur de l'école doctorale (PR. P. {\sc Lutz}) 
+et du directeur du département (Pr. O. {\sc Kouchnarenko}) sont donnés en annexes. 

 
 
 % \subsection{Avis du directeur de l'équipe}\label{sec:avis:directeur:equipe}
 
 
 % \subsection{Avis du directeur de l'équipe}\label{sec:avis:directeur:equipe}


@@ -158,7 +160,7 @@ Les avis du directeur de recherche, du directeur de l'équipe, du directeur de l
 % \subsection{Avis du directeur de l'école doctorale}\label{sec:avis:directeur:spim}
 
 
 % \subsection{Avis du directeur de l'école doctorale}\label{sec:avis:directeur:spim}
 
 

-\newpage
+

 \section{Résumé de la thématique de la thèse d'université}
 On considère en entrée de la démarche une description
 mathématique d'un programme: par exemple une fonction enrichie avec  
 \section{Résumé de la thématique de la thèse d'université}
 On considère en entrée de la démarche une description
 mathématique d'un programme: par exemple une fonction enrichie avec  


@@ -261,7 +263,7 @@ Jean-Fran\c{c}ois Couchot.
 
 
 
 
 
 

-\newpage
+%\newpage

 \section{Exposé des recherches réalisées au cours de la période postdoctorale}
 
 Entre avril 2006 et aujourd'hui, les recherches réalisées ont concerné plusieurs domaines synthétisés ci-après. Le premier travail (Sec.~\ref{sub:verif}) 
 \section{Exposé des recherches réalisées au cours de la période postdoctorale}
 
 Entre avril 2006 et aujourd'hui, les recherches réalisées ont concerné plusieurs domaines synthétisés ci-après. Le premier travail (Sec.~\ref{sub:verif}) 


@@ -660,7 +662,7 @@ le doctorat de B. Alkindy.
 
 
 
 
 
 

-\newpage
+%\newpage

 \section{Perspectives de recherche}
 Les trois sections suivantes présentent quelques perspectives de recherche 
 autour de la thématique des systèmes dynamiques discrets. 
 \section{Perspectives de recherche}
 Les trois sections suivantes présentent quelques perspectives de recherche 
 autour de la thématique des systèmes dynamiques discrets. 


@@ -792,7 +794,7 @@ Ceci se réalisera notamment au travers du doctorat de Y. Fadil.
 
 
 
 
 
 

-\newpage
+%\newpage

 \section{Insertion dans l'équipe de recherche} 
 Cette section donne quelques éléments factuels 
 permettent d'apprécier mon insertion au sein  de cette équipe de recherche.
 \section{Insertion dans l'équipe de recherche} 
 Cette section donne quelques éléments factuels 
 permettent d'apprécier mon insertion au sein  de cette équipe de recherche.


@@ -816,8 +818,11 @@ les conférences reconnues suivantes:
 
 \subsection{Appels à projet}
 
 
 \subsection{Appels à projet}
 

-Christophe Guyeux a répondu avec succès à l'appel à projet jeune 
-chercheur de l'UFC, projet dont je faisais partie. 
+
+En 2014 (les dates a verifier), j'ai participé 
+au projet Jeune chercheur de l'UFC porté par
+Christophe Guyeux dont le thème était 
+\og la sécurisation numérique par chaos\fg{}.

 
 J'ai répondu avec succès à l'appel à projets de la région de 
 Franche-Comté en 2015: j'ai participé à l'élaboration du  
 
 J'ai répondu avec succès à l'appel à projets de la région de 
 Franche-Comté en 2015: j'ai participé à l'élaboration du  


@@ -841,6 +846,9 @@ avec l'I3S, le LORIA et le LIF de MArseille.
 \item participant à un  projet PHC Cedre 2015: \og 
 méthodes et outils pour concevoir, évaluer et déployer des réseaux de capteurs 
 pour l'agriculture au liban\fg{} avec l'Université Libanaise.
 \item participant à un  projet PHC Cedre 2015: \og 
 méthodes et outils pour concevoir, évaluer et déployer des réseaux de capteurs 
 pour l'agriculture au liban\fg{} avec l'Université Libanaise.

+\item participant au projet PEPS JCJC INS2I 2015, sur 
+\og Prédiction bio-informatique de l'évolution des génomes\fg{} avec le
+LMB et le l'université de Neuchâtel en Suisse. 

 \end{itemize}
 
 \subsection{Collaborations}
 \end{itemize}
 
 \subsection{Collaborations}


@@ -927,7 +935,7 @@ où j'ai présenté \og Steganography: secure and robust algorithms \fg{} et en
 
 
 
 
 
 

-\newpage
+%\newpage

 \section{Encadrement et co-encadrement d'étudiants} 
 
 \subsection{Thèse d'université}
 \section{Encadrement et co-encadrement d'étudiants} 
 
 \subsection{Thèse d'université}


@@ -996,7 +1004,7 @@ Le stage a commencé le 01 avril 2015 et sera soutenu le 31 août 2015.
 \end{itemize}
 
 
 \end{itemize}
 
 

-\newpage
+%\newpage

 \section{Participation à des tâches d'intérêt collectif}
 
 \subsection{Tâches d'enseignement} 
 \section{Participation à des tâches d'intérêt collectif}
 
 \subsection{Tâches d'enseignement} 


@@ -1062,7 +1070,7 @@ Je suis régulièrement membre de jury des épreuves TIPE, épreuves communes
 
 
 
 
 
 

-\newpage
+%\newpage

 \section{Publications après la thèse}\label{sec:publi}
 Le tableau de la figure~\ref{fig:bilan} donné 
 ci dessous synthétise les références détaillées ci-après.
 \section{Publications après la thèse}\label{sec:publi}
 Le tableau de la figure~\ref{fig:bilan} donné 
 ci dessous synthétise les références détaillées ci-après.


@@ -1186,6 +1194,7 @@ Au DISC à FEMTO-ST&
 
 \subsection{Journaux internationaux avec comité de sélection}
 
 
 \subsection{Journaux internationaux avec comité de sélection}
 

+\vspace{-2em}

 \begin{thebibliography}{CHG{\etalchar{+}}14b}
 
 \makeatletter
 \begin{thebibliography}{CHG{\etalchar{+}}14b}
 
 \makeatletter


@@ -1235,6 +1244,7 @@ Jean-Fran\c{c}ois Couchot, Karine Deschinkel, and Michel Salomon.
 
 \subsection{Journaux internationaux avec comité de sélection (en cours de soumission)}
 
 
 \subsection{Journaux internationaux avec comité de sélection (en cours de soumission)}
 

+\vspace{-2em}

 \begin{thebibliography}{CHG{\etalchar{+}}14b}
 
 \makeatletter
 \begin{thebibliography}{CHG{\etalchar{+}}14b}
 
 \makeatletter


@@ -1274,7 +1284,7 @@ Mohammed Bakiri, Christophe Guyeux, Jean-Fran\c{c}cois Couchot, and
 \end{thebibliography}
 
 \subsection{Conférences internationales avec comité de sélection}
 \end{thebibliography}
 
 \subsection{Conférences internationales avec comité de sélection}

-
+\vspace{-2em}

 \begin{thebibliography}{CHG{\etalchar{+}}14b}
 \makeatletter
 \addtocounter{\@listctr}{14}
 \begin{thebibliography}{CHG{\etalchar{+}}14b}
 \makeatletter
 \addtocounter{\@listctr}{14}


@@ -1458,6 +1468,7 @@ J'ai été invité:
 \end{itemize}
 
 \subsection{Communications diverses}
 \end{itemize}
 
 \subsection{Communications diverses}

+\vspace{-2em}

 \begin{thebibliography}{CHG{\etalchar{+}}14b}
 
 \makeatletter
 \begin{thebibliography}{CHG{\etalchar{+}}14b}
 
 \makeatletter

diff --git a/main.tex b/main.tex
index 4ef11c8fc3caee8b3a3514d3ce6ce2d6eb325365..327136e24719cb89f110bdb6290401f6165ef870 100644 (file)
--- a/main.tex
+++ b/main.tex
@@ -225,7 +225,10 @@ On montre qu'on a des résultats similaires.
 \input{14Secrypt}
 
 
 \input{14Secrypt}
 
 

-\chapter{Quelques expérimentations}
+%\chapter{Quelques expérimentations}
+
+
+\part{Application au masquage d'information}