X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/eb4e301626c295e21a63aa3eb3d42a76e1a90588..6213067fa7f7c7d9f34f6a1ec3964b829b109db1:/14Secrypt.tex

diff --git a/14Secrypt.tex b/14Secrypt.tex
index fd6cbaf..597acbb 100644
--- a/14Secrypt.tex
+++ b/14Secrypt.tex
@@ -713,48 +713,44 @@ la figure~\ref{fig:markov:f*}.
     & &  40, 63, 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22,  & & \\
     & &  16, 24, 13, 12, 29, 8, 10, 42, 41, 0, 5, 2, 4, 6, 11, 34, 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]                       &     &      \\
+         \multirow{9}{0.5cm}{7}            &$f^{*7}$ & [111, 94, 93, 116, 122, 114, 125, 88, 115, 126, 85, 84, 123,     & \multirow{9}{0.5cm}{\textbf{10}}    & \multirow{9}{0.5cm}{\textbf{63}}     \\ 
+                 & & 98, 81, 120, 109, 78, 105, 110, 99, 107, 104, 108, 101, 118,     &     &      \\ 
+                 & & 117, 96, 103, 66, 113, 64, 79, 86, 95, 124, 83, 91, 121, 24,     &     &      \\ 
+                 & & 119, 22, 69, 20, 87, 18, 17, 112, 77, 76, 73, 12, 74, 106, 72,   &     &      \\ 
+                 & & 8, 7, 102, 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, 90, 89, 25, 19, 30, 23, 4, 27, 2, 16, 80, 31, 10, 15, 14,     &     &      \\ 
+                 & & 3, 11, 13, 9, 5, 70, 21, 68, 67, 6, 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]&&\\
+         \multirow{20}{0.5cm}{8}   &        $f^{*8}$  &
+[223, 190, 249, 254, 187, 251, 233, 232, 183, 230, 247, 180,& 
+\multirow{20}{0.5cm}{9}& 
+\multirow{20}{0.5cm}{71}\\ 
+& & 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, 12, 11, 142, 129, 128, 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, 136, 39, 134, 133, 5, 131,& & \\ 
+& & 34, 9, 8]&&\\
         \hline
       \end{tabular}
     \end{scriptsize}
   \end{center}
-\label{table:functions}
-\caption{Fonctions avec matrices DSCC et le plus faible temps de mÃ©lange.}
-
+\caption{Fonctions avec matrices DSCC et le plus faible temps de mÃ©lange}\label{table:functions}
 \end{table}
 
 Le  tableau~\ref{table:functions} reprend  une synthÃ¨se de 
@@ -765,14 +761,19 @@ 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}$.  
+$\epsilon$ fixÃ©e Ã  $10^{-8}$ et pour un mode donnÃ©.  
 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
+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 
+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$).
+
+Un second  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Ã¹ 
@@ -824,9 +825,9 @@ $$
 \hline
 \textrm{ItÃ©rations} & 4 & 5 & 6 & 7 & 8 \\ 
 \hline
-\textrm{Unaires}         &  19.0 & 22.2905097109  & 23.6954895899 & 25.2661942985 & 27.0\\  
+\textrm{Unaires}         &  19.0 & 22.3  & 23.7 & 25.3 & 27.0\\  
 \hline
-\textrm{GÃ©nÃ©ralisÃ©es}          &  17   & 13             & 11            & 10 & 9\\
+\textrm{GÃ©nÃ©ralisÃ©es}    &  17   & 13    & 11   & 10   & 9\\
 \hline
 \end{array}
 $$
@@ -844,18 +845,33 @@ 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).
+En interne, c'est l'implantation de l'algorithme de Mersenne Twister qui
+permet de gÃ©nÃ©rer la stratÃ©gie alÃ©atoire.
+
+
+
+
  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 ces expÃ©rimentations. 
+Les tableau~\ref{fig:TEST:generalise} donnent
+une vision synthÃ©tique de ces expÃ©rimentations. 
 Nous avons Ã©valuÃ© les fonctions prÃ©fixÃ©es par 
-$f$ (respecitvement $g$) avec le gÃ©nÃ©rateur issu des itÃ©rations 
+$f$ (respecitvement $g$) avec les gÃ©nÃ©rateurs issus des itÃ©rations 
 gÃ©nÃ©ralisÃ©es (resp. unaires).
-%L'expÃ©rience a montrÃ© notamment que toutes ces fonctions
-%passent avec succÃ¨s cette batterie de tests. 
+Quelle que soit la mÃ©thode utilisÃ©e, on constate que chacun des 
+gÃ©nÃ©rateurs passe 
+avec succes le test de NIST. 
+
+InterprÃ©ter ces resultats en concluant que ces gÃ©nÃ©rateurs sont 
+tous Ã©quivalents serait erronÃ©: la meilleur 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 
+sont basÃ©es sur les itÃ©rations unaires.
 
 
 
@@ -870,26 +886,104 @@ gÃ©nÃ©ralisÃ©es (resp. unaires).
   \begin{scriptsize}
 
 
-
+\begin{tabular}{|l|r|r|r|r|}
+ \hline 
+Test & $f^{*5}$ &$f^{*6}$ &$f^{*7}$ &$f^{*8}$ \\ \hline 
+FrÃ©quence (Monobit)& 0.401 (0.97)& 0.924 (1.0)& 0.779 (0.98)& 0.883 (0.99)\\ \hline 
+FrÃ©quence ds un bloc& 0.574 (0.98)& 0.062 (1.0)& 0.978 (0.98)& 0.964 (0.98)\\ \hline 
+Somme CumulÃ©*& 0.598 (0.975)& 0.812 (1.0)& 0.576 (0.99)& 0.637 (0.99)\\ \hline 
+ExÃ©cution& 0.998 (0.99)& 0.213 (0.98)& 0.816 (0.98)& 0.494 (1.0)\\ \hline 
+Longue exÃ©cution dans un bloc& 0.085 (0.99)& 0.971 (0.99)& 0.474 (1.0)& 0.574 (0.99)\\ \hline 
+Rang& 0.994 (0.96)& 0.779 (1.0)& 0.191 (0.99)& 0.883 (0.99)\\ \hline 
+Fourier rapide& 0.798 (1.0)& 0.595 (0.99)& 0.739 (0.99)& 0.595 (1.0)\\ \hline 
+Patron sans superposition*& 0.521 (0.987)& 0.494 (0.989)& 0.530 (0.990)& 0.520 (0.989)\\ \hline 
+Patron avec superposition& 0.066 (0.99)& 0.040 (0.99)& 0.304 (1.0)& 0.249 (0.98)\\ \hline 
+Statistiques universelles& 0.851 (0.99)& 0.911 (0.99)& 0.924 (0.96)& 0.066 (1.0)\\ \hline 
+Entropie approchÃ©e (m=10)& 0.637 (0.99)& 0.102 (0.99)& 0.115 (0.99)& 0.350 (0.98)\\ \hline 
+Suite alÃ©atoire *& 0.573 (0.981)& 0.144 (0.989)& 0.422 (1.0)& 0.314 (0.984)\\ \hline 
+Suite alÃ©atoire variante *& 0.359 (0.968)& 0.401 (0.982)& 0.378 (0.989)& 0.329 (0.985)\\ \hline 
+SÃ©rie* (m=10)& 0.469 (0.98)& 0.475 (0.995)& 0.473 (0.985)& 0.651 (0.995)\\ \hline 
+ComplexitÃ© linaire& 0.129 (1.0)& 0.494 (1.0)& 0.062 (1.0)& 0.739 (1.0)\\ \hline 
+
+\end{tabular}
   \end{scriptsize}
 
-\label{fig:TEST:generalise}
+
 \caption{Test de NIST pour les fonctions 
-  du tableau~\ref{table:functions} selon les itÃ©rations gÃ©nÃ©ralisÃ©es}
+  du tableau~\ref{table:functions} selon les itÃ©rations gÃ©nÃ©ralisÃ©es}\label{fig:TEST:generalise}
 \end{table}
 
 
 \begin{table}[ht]
   \centering
   \begin{scriptsize}
+\begin{tabular}{|l|r|r|r|r|}
+\hline 
+Test & $g^{*5}$& $g^{*6}$& $f^{*7}$& $f^{*8}$\\ \hline 
+FrÃ©quence (Monobit)& 0.236 (1.0)& 0.867 (0.99)& 0.437 (0.99)& 0.911 (1.0)\\ \hline 
+FrÃ©quence ds un bloc& 0.129 (0.98)& 0.350 (0.99)& 0.366 (0.96)& 0.657 (1.0)\\ \hline 
+Somme CumulÃ©*& 0.903 (0.995)& 0.931 (0.985)& 0.863 (0.995)& 0.851 (0.995)\\ \hline 
+ExÃ©cution& 0.699 (0.98)& 0.595 (0.99)& 0.181 (1.0)& 0.437 (0.99)\\ \hline 
+Longue exÃ©cution dans un bloc& 0.009 (0.99)& 0.474 (0.97)& 0.816 (1.0)& 0.051 (1.0)\\ \hline 
+Rang& 0.946 (0.96)& 0.637 (0.98)& 0.494 (1.0)& 0.946 (1.0)\\ \hline 
+Fourier rapide& 0.383 (0.99)& 0.437 (1.0)& 0.616 (0.98)& 0.924 (0.99)\\ \hline 
+Patron sans superposition*& 0.466 (0.990)& 0.540 (0.989)& 0.505 (0.990)& 0.529 (0.991)\\ \hline 
+Patron avec superposition& 0.202 (0.96)& 0.129 (0.98)& 0.851 (0.99)& 0.319 (0.98)\\ \hline 
+Statistiques universelles& 0.319 (0.97)& 0.534 (0.99)& 0.759 (1.0)& 0.657 (0.99)\\ \hline 
+Entropie approchÃ©e (m=10)& 0.075 (0.97)& 0.181 (0.99)& 0.213 (0.98)& 0.366 (0.98)\\ \hline 
+Suite alÃ©atoire *& 0.357 (0.986)& 0.569 (0.991)& 0.539 (0.987)& 0.435 (0.992)\\ \hline 
+Suite alÃ©atoire variante *& 0.398 (0.989)& 0.507 (0.986)& 0.668 (0.991)& 0.514 (0.994)\\ \hline 
+SÃ©rie* (m=10)& 0.859 (0.995)& 0.768 (0.99)& 0.427 (0.995)& 0.637 (0.98)\\ \hline 
+ComplexitÃ© linaire& 0.897 (0.99)& 0.366 (0.98)& 0.153 (1.0)& 0.437 (1.0)\\ \hline 
+
+\end{tabular}
+\end{scriptsize}
+
+
+\caption{Test de NIST pour les fonctions 
+  du tableau~\ref{table:functions} selon les itÃ©rations unaires}\label{fig:TEST:unaire}
+\end{table}
+
+
+\begin{table}[ht]
+  \centering
+  \begin{scriptsize}
+
+\begin{tabular}{|l|r|r|r|r|}
+ \hline 
+Test & 5 bits& 6 bits & 7 bits & 8bits  \\ \hline 
+FrÃ©quence (Monobit)& 0.289 (1.0)& 0.437 (1.0)& 0.678 (1.0)& 0.153 (0.99)\\ \hline 
+FrÃ©quence ds un bloc& 0.419 (1.0)& 0.971 (0.98)& 0.419 (0.99)& 0.275 (1.0)\\ \hline 
+Somme CumulÃ©*& 0.607 (0.99)& 0.224 (0.995)& 0.645 (0.995)& 0.901 (0.99)\\ \hline 
+ExÃ©cution& 0.129 (0.99)& 0.005 (0.99)& 0.935 (0.98)& 0.699 (0.98)\\ \hline 
+Longue exÃ©cution dans un bloc& 0.514 (1.0)& 0.739 (0.99)& 0.994 (1.0)& 0.834 (0.99)\\ \hline 
+Rang& 0.455 (0.97)& 0.851 (0.99)& 0.554 (1.0)& 0.964 (0.99)\\ \hline 
+Fourier rapide& 0.096 (0.98)& 0.955 (0.99)& 0.851 (0.97)& 0.037 (1.0)\\ \hline 
+Patron sans superposition*& 0.534 (0.990)& 0.524 (0.990)& 0.508 (0.987)& 0.515 (0.99)\\ \hline 
+Patron avec superposition& 0.699 (0.99)& 0.616 (0.95)& 0.071 (1.0)& 0.058 (1.0)\\ \hline 
+Statistiques universelles& 0.062 (0.99)& 0.071 (1.0)& 0.637 (1.0)& 0.494 (0.98)\\ \hline 
+Entropie approchÃ©e (m=10)& 0.897 (0.99)& 0.383 (0.99)& 0.366 (1.0)& 0.911 (0.99)\\ \hline 
+Suite alÃ©atoire *& 0.365 (0.983)& 0.442 (0.994)& 0.579 (0.992)& 0.296 (0.993)\\ \hline 
+Suite alÃ©atoire variante *& 0.471 (0.978)& 0.559 (0.992)& 0.519 (0.987)& 0.340 (0.995)\\ \hline 
+SÃ©rie* (m=10)& 0.447 (0.985)& 0.298 (0.995)& 0.648 (1.0)& 0.352 (0.995)\\ \hline 
+ComplexitÃ© linaire& 0.005 (0.98)& 0.534 (0.99)& 0.085 (0.97)& 0.996 (1.0)\\ \hline 
+
+\end{tabular}
+
+
+
+
+
+
+
 
 
 
   \end{scriptsize}
 
-\label{fig:TEST:unaire}
-\caption{Test de NIST pour les fonctions 
-  du tableau~\ref{table:functions} selon les itÃ©rations unaires}
+
+\caption{Test de NIST pour l'algorithme de Mersenne Twister}\label{fig:TEST:Mersenne}
 \end{table}
 
+
 %
