fin des expérimentatios prng

[hdrcouchot.git] / 14Secrypt.tex

diff --git a/14Secrypt.tex b/14Secrypt.tex
index fd6cbaf360a09e028d485be31989a2d0bffbe8a3..597acbb2b0f592bf6d4a6adcec05ff0ed2edf5ff 100644 (file)
--- 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
     & &  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
         \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}
         \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 
 \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
 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
 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ù 
 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
 \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
 \hline

-\textrm{Généralisées}          &  17   & 13             & 11            & 10 & 9\\
+\textrm{Généralisées}    &  17   & 13    & 11   & 10   & 9\\

 \hline
 \end{array}
 $$
 \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).
 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\%$.
 
 
  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 
 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).
 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{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}
 
   \end{scriptsize}
 

-\label{fig:TEST:generalise}
+

 \caption{Test de NIST pour les fonctions 
 \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}
 \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}
 
 
 
 
   \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}
 
 \end{table}
 

+

 %
 %