Ajout diapos présentation PRNG

[16dcc.git] / prng.tex

diff --git a/prng.tex b/prng.tex
index 4ad9989ba178e8587800b6e3dc0f85ff136d8b13..8925e51326f8ebea7013e5ab1fc7cc5186c11753 100644 (file)
--- a/prng.tex
+++ b/prng.tex
@@ -54,7 +54,7 @@ it preserves this property.
 
 For each number $\mathsf{N}=4,5,6,7,8$ of bits, we have generated 
 the functions according to the method 
 
 For each number $\mathsf{N}=4,5,6,7,8$ of bits, we have generated 
 the functions according to the method 

-given in Sect.~\ref{sec:hamilton}.
+given in Sect.~\ref{sec:SCCfunc} and~\ref{sec:hamilton}. 

 % MENTION FILTRAGE POSSIBLE LORS DE CONSTRUCTION... (SCV) 
 For each $\mathsf{N}$, we have then restricted this evaluation to the function 
 whose Markov Matrix (issued from Eq.~(\ref{eq:Markov:rairo})) 
 % MENTION FILTRAGE POSSIBLE LORS DE CONSTRUCTION... (SCV) 
 For each $\mathsf{N}$, we have then restricted this evaluation to the function 
 whose Markov Matrix (issued from Eq.~(\ref{eq:Markov:rairo})) 


@@ -110,116 +110,63 @@ $\textcircled{c}$&
 %%%%% n= 7
 \hline
 &
 %%%%% n= 7
 \hline
 &

-[111, 124, 93, 120, 122, 90, 113, 88, 115, 126, 125, 84, 123, 98, 
+[111, 124, 93, 120, 122, 114, 89, 121, 87, 126, 125, 84, 123, 82, 

 &&\\
 &&\\

-&112, 96, 109, 106, 77, 110, 99, 74, 104, 72, 71, 100, 117, 116, 
+&112, 80, 79, 106, 105, 110, 75, 107, 73, 108, 119, 100, 117, 116, 

 &&\\
 &&\\

-&103, 102, 65, 97, 31, 86, 95, 28, 27, 91, 121, 92, 119, 118, 69, 
+&103, 102, 101, 97, 31, 86, 95, 94, 83, 26, 88, 24, 71, 118, 69, 

 &&\\
 &&\\

-&68, 87, 114, 89, 81, 15, 76, 79, 108, 107, 10, 105, 8, 7, 6, 101, 
-&&\\
-$\textcircled{d}$&70, 75, 82, 64, 0, 127, 54, 53, 62, 51, 59, 56, 60, 39, 52, 37, 
+&68, 115, 90, 113, 16, 15, 76, 109, 72, 74, 10, 9, 104, 7, 6, 65, 

 &&\\
 &&\\

+$\textcircled{d}$ &70, 99, 98, 64, 96, 127, 54, 53, 62, 51, 59, 56, 60, 39, 52, 37, &7 &99\\

 &36, 55, 58, 57, 49, 63, 44, 47, 40, 42, 46, 45, 41, 35, 34, 33, 
 &&\\
 &36, 55, 58, 57, 49, 63, 44, 47, 40, 42, 46, 45, 41, 35, 34, 33, 
 &&\\

-&38, 43, 50, 32, 48, 29, 94, 61, 24, 26, 18, 17, 25, 19, 30, 85, 
+&38, 43, 50, 32, 48, 29, 28, 61, 92, 91, 18, 17, 25, 19, 30, 85, 

 &&\\
 &&\\

-&22, 83, 2, 16, 80, 13, 78, 9, 14, 3, 11, 73, 12, 23, 4, 21, 20, 
+&22, 27, 2, 81, 0, 13, 78, 77, 14, 3, 11, 8, 12, 23, 4, 21, 20, 

 &&\\
 &67, 66, 5, 1]
 &&\\
 &67, 66, 5, 1]

-
-
-
-
-
-
-
-[111, 94, 93, 116, 122, 90, 125, 88, 115, 126, 119, 84, 123, 98,
-&&\\
-&
- 81, 120, 109, 106, 105, 110, 99, 107, 104, 72, 71, 118,  117, 
- &&\\
-&
-96, 103, 102, 113, 64, 79, 86, 95, 124, 83, 91, 121, 24, 85, 22, 
-&&\\
-69, 20, 19, 114, 17, 112, 77, 76, 13, 108, 74, 10, 9, 73, 67, 66,
-&7 & 99\\
-
-& 
- 101, 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, 87, 30, 
-&&\\
-&
-23, 4, 27, 2, 16, 80, 31, 78, 15, 14, 3, 11, 8, 12, 5, 70, 21, 
-&&\\
-&
-68, 7, 6, 65, 1]

 &&\\
 
 
 %%%%%n=8
 \hline
 &
 &&\\
 
 
 %%%%%n=8
 \hline
 &

-[223, 190, 249, 254, 187, 251, 233, 232, 183, 230, 247, 180, 227, 
+[223, 238, 249, 254, 243, 251, 233, 252, 183, 244, 229, 245, 227, 

 &&\\
 &&\\

-&
-178, 240, 248, 237, 236, 253, 172, 203, 170, 201, 168, 229, 166, 
+&246, 240, 176, 175, 174, 253, 204, 203, 170, 169, 248, 247, 226, 

 &&\\
 &&\\

-&
-165, 244, 163, 242, 241, 192, 215, 220, 205, 216, 218, 222, 221, 
+&228, 164, 163, 162, 161, 192, 215, 220, 205, 216, 155, 222, 221, 

 &&\\
 &&\\

-&
-208, 213, 210, 212, 214, 219, 211, 217, 209, 239, 202, 207, 140, 
+&208, 213, 150, 212, 214, 219, 211, 145, 209, 239, 202, 207, 140, 

 &&\\
 &&\\

-&
-139, 234, 193, 204, 135, 196, 199, 132, 194, 130, 225, 200, 159, 
+&195, 234, 193, 136, 231, 230, 199, 197, 131, 198, 225, 200, 63, 

 &&\\
 &&\\

-&
-62, 185, 252, 59, 250, 169, 56, 191, 246, 245, 52, 243, 50, 176, 
+&188, 173, 184, 186, 250, 57, 168, 191, 178, 180, 52, 187, 242, 

 &&\\
 &&\\

-&
-48, 173, 238, 189, 44, 235, 42, 137, 184, 231, 38, 37, 228, 35,
+&241, 48, 143, 46, 237, 236, 235, 138, 185, 232, 135, 38, 181, 165, 

 &&\\
 &&\\

-&
-226, 177, 224, 151, 156, 141, 152, 154, 158, 157, 144, 149, 146,
+&35, 166, 33, 224, 31, 30, 153, 158, 147, 218, 217, 156, 159, 148, 

 &&\\
 &&\\

-&
-148, 150, 155, 147, 153, 145, 175, 206, 143, 136, 11, 142, 129,
+$\textcircled{e}$&151, 149, 19, 210, 144, 152, 141, 206, 13, 12, 171, 10, 201, 128, 
+&8&109\\
+&133, 130, 132, 196, 3, 194, 137, 0, 255, 124, 109, 120, 122, 106, 

 &&\\
 &&\\

-$\textcircled{e}$&
-8, 7, 198, 197, 4, 195, 2, 161, 160, 255, 124, 109, 108, 122,
-&8&110\\
-&
- 126, 125, 112, 117, 114, 116, 100, 123, 98, 97, 113, 79, 106,
+&125, 104, 103, 114, 116, 118, 123, 98, 97, 113, 79, 126, 111, 110, 

 &&\\
 &&\\

-&
- 111, 110, 99, 74, 121, 120, 71, 118, 103, 101, 115, 66, 65, 
+&99, 74, 121, 72, 71, 70, 117, 101, 115, 102, 65, 112, 127, 90, 89, 

 &&\\
 &&\\

-&
-104, 127, 90, 89, 94, 83, 91, 81, 92, 95, 84, 87, 85, 82, 86,
+&94, 83, 91, 81, 92, 95, 84, 87, 85, 82, 86, 80, 88, 77, 76, 93, 

 &&\\
 &&\\

-&
-80, 88, 77, 76, 93, 72, 107, 78, 105, 64, 69, 102, 68, 70, 75,
+&108, 107, 78, 105, 64, 69, 66, 68, 100, 75, 67, 73, 96, 55, 190, 

 &&\\
 &&\\

-&
-67, 73, 96, 55, 58, 45, 188, 51, 186, 61, 40, 119, 182, 181, 
+&189, 62, 51, 59, 41, 60, 119, 182, 37, 53, 179, 54, 177, 32, 45, 

 &&\\
 &&\\

-&
-53, 179, 54, 33, 49, 15, 174, 47, 60, 171, 46, 57, 32, 167, 6,
+&44, 61, 172, 11, 58, 9, 56, 167, 34, 36, 4, 43, 50, 49, 160, 23, 

 &&\\
 &&\\

-&
- 36, 164, 43, 162, 1, 0, 63, 26, 25, 30, 19, 27, 17, 28, 31, 
+&28, 157, 24, 26, 154, 29, 16, 21, 18, 20, 22, 27, 146, 25, 17, 47, 

 &&\\
 &&\\

-&
-20, 23, 21, 18, 22, 16, 24, 13, 10, 29, 14, 3, 138, 41, 12, 
-&&\\
-&
-39, 134, 133, 5, 131, 34, 9, 128]
+&142, 15, 14, 139, 42, 1, 40, 39, 134, 7, 5, 2, 6, 129, 8]

 &&\\
 \hline
 \end{tabular}
 &&\\
 \hline
 \end{tabular}


@@ -233,46 +180,80 @@ $\textcircled{e}$&
 Let us first discuss about results against the NIST test suite. 
 In our experiments, 100 sequences (s = 100) of 1,000,000 bits are generated and tested.
 If the value $\mathbb{P}_T$ of any test is smaller than 0.0001, the sequences are considered to be not good enough
 Let us first discuss about results against the NIST test suite. 
 In our experiments, 100 sequences (s = 100) of 1,000,000 bits are generated and tested.
 If the value $\mathbb{P}_T$ of any test is smaller than 0.0001, the sequences are considered to be not good enough

-and the generator is unsuitable. Table~\ref{The passing rate} shows $\mathbb{P}_T$ of sequences based on discrete
-chaotic iterations using different schemes. If there are at least two statistical values in a test, this test is
+and the generator is unsuitable. 
+
+Table~\ref{The passing rate} shows $\mathbb{P}_T$ of sequences based 
+on $\chi_{\textit{16HamG}}$ using different functions, namely
+$\textcircled{a}$,\ldots, $\textcircled{e}$.
+In this algorithm implementation, 
+the embedded PRNG \textit{Random} is the default Python PRNG, \textit{i.e.},
+the Mersenne Twister algorithm~\cite{matsumoto1998mersenne}. 
+Implementations for $\mathsf{N}=4, \dots, 8$ of this algorithm is evaluated
+through the NIST test suite and results are given in columns 
+$\textit{MT}_4$, \ldots,  $\textit{MT}_8$.
+If there are at least two statistical values in a test, this test is

 marked with an asterisk and the average value is computed to characterize the statistics.
 marked with an asterisk and the average value is computed to characterize the statistics.

-We can see in Table \ref{The passing rate} that all the rates are greater than 97/100, \textit{i.e.}, all the generators 
-achieve to pass the NIST battery of tests.

 
 

+We first can see in Table \ref{The passing rate} that all the rates 
+are greater than 97/100, \textit{i.e.}, all the generators 
+achieve to pass the NIST battery of tests.
+It can be noticed that adding chaos properties for Mersenne Twister 
+algorithm does not reduce its security against this statistical tests.

 
 
 
 

-\begin{table} 
-\renewcommand{\arraystretch}{1.3}
+\begin{table*} 
+\renewcommand{\arraystretch}{1.1}

 \begin{center}
 \begin{center}

-\begin{scriptsize}
+\begin{tiny}

 \setlength{\tabcolsep}{2pt}
 
 \setlength{\tabcolsep}{2pt}
 

+\begin{tabular}{|l|r|r|r|r|r|}
+ \hline 
+Test & $\textit{MT}_4$ & $\textit{MT}_5$& $\textit{MT}_6$& $\textit{MT}_7$& $\textit{MT}_8$
+ \\ \hline 
+Frequency (Monobit)& 0.924 (1.0)& 0.678 (0.98)& 0.102 (0.97)& 0.213 (0.98)& 0.719 (0.99) \\ \hline 
+Frequency  within a Block& 0.514 (1.0)& 0.419 (0.98)& 0.129 (0.98)& 0.275 (0.99)& 0.455 (0.99)\\ \hline 
+Cumulative Sums (Cusum) *& 0.668 (1.0)& 0.568 (0.99)& 0.881 (0.98)& 0.529 (0.98)& 0.657 (0.995)\\ \hline 
+Runs& 0.494 (0.99)& 0.595 (0.97)& 0.071 (0.97)& 0.017 (1.0)& 0.834 (1.0)\\ \hline 
+Longest Run of Ones in a Block& 0.366 (0.99)& 0.554 (1.0)& 0.042 (0.99)& 0.051 (0.99)& 0.897 (0.97)\\ \hline 
+Binary Matrix Rank& 0.275 (0.98)& 0.494 (0.99)& 0.719 (1.0)& 0.334 (0.98)& 0.637 (0.99)\\ \hline 
+Discrete Fourier Transform (Spectral)& 0.122 (0.98)& 0.108 (0.99)& 0.108 (1.0)& 0.514 (0.99)& 0.534 (0.98)\\ \hline 
+Non-overlapping Template Matching*& 0.483 (0.990)& 0.507 (0.990)& 0.520 (0.988)& 0.494 (0.988)& 0.515 (0.989)\\ \hline 
+Overlapping Template Matching& 0.595 (0.99)& 0.759 (1.0)& 0.637 (1.0)& 0.554 (0.99)& 0.236 (1.0)\\ \hline 
+Maurer's "Universal Statistical"& 0.202 (0.99)& 0.000 (0.99)& 0.514 (0.98)& 0.883 (0.97)& 0.366 (0.99)\\ \hline 
+Approximate Entropy (m=10)& 0.616 (0.99)& 0.145 (0.99)& 0.455 (0.99)& 0.262 (0.97)& 0.494 (1.0)\\ \hline 
+Random Excursions *& 0.275 (1.0)& 0.495 (0.975)& 0.465 (0.979)& 0.452 (0.991)& 0.260 (0.989)\\ \hline 
+Random Excursions Variant *& 0.382 (0.995)& 0.400 (0.994)& 0.417 (0.984)& 0.456 (0.991)& 0.389 (0.991)\\ \hline 
+Serial* (m=10)& 0.629 (0.99)& 0.963 (0.99)& 0.366 (0.995)& 0.537 (0.985)& 0.253 (0.995)\\ \hline 
+Linear Complexity& 0.494 (0.99)& 0.514 (0.98)& 0.145 (1.0)& 0.657 (0.98)& 0.145 (0.99)\\ \hline 
+\end{tabular}

 
 

-\begin{tabular}{|l|l|l|l|l|l|}
-\hline
-Method &$\textcircled{a}$& $\textcircled{b}$ & $\textcircled{c}$ & $\textcircled{d}$ & $\textcircled{e}$   \\ \hline\hline
-Frequency (Monobit)& 0.851 (0.98)& 0.719 (0.99)& 0.699 (0.99)& 0.514 (1.0)& 0.798 (0.99)\\ \hline 
-Frequency (Monobit)& 0.851 (0.98)& 0.719 (0.99)& 0.699 (0.99)& 0.514 (1.0)& 0.798 (0.99)\\ \hline 
-Frequency  within a Block& 0.262 (0.98)& 0.699 (0.98)& 0.867 (0.99)& 0.145 (1.0)& 0.455 (0.99)\\ \hline 
-Cumulative Sums (Cusum) *& 0.301 (0.98)& 0.521 (0.99)& 0.688 (0.99)& 0.888 (1.0)& 0.598 (1.0)\\ \hline 
-Runs& 0.224 (0.97)& 0.383 (0.97)& 0.108 (0.96)& 0.213 (0.99)& 0.616 (0.99)\\ \hline 
-Longest Run of 1s & 0.383 (1.0)& 0.474 (1.0)& 0.983 (0.99)& 0.699 (0.98)& 0.897 (0.96)\\ \hline 
-Binary Matrix Rank& 0.213 (1.0)& 0.867 (0.99)& 0.494 (0.98)& 0.162 (0.99)& 0.924 (0.99)\\ \hline 
-Disc. Fourier Transf. (Spect.)& 0.474 (1.0)& 0.739 (0.99)& 0.012 (1.0)& 0.678 (0.98)& 0.437 (0.99)\\ \hline 
-Unoverlapping Templ. Match.*& 0.505 (0.990)& 0.521 (0.990)& 0.510 (0.989)& 0.511 (0.990)& 0.499 (0.990)\\ \hline 
-Overlapping Temp. Match.& 0.574 (0.98)& 0.304 (0.99)& 0.437 (0.97)& 0.759 (0.98)& 0.275 (0.99)\\ \hline 
-Maurer's Universal Statistical& 0.759 (0.96)& 0.699 (0.97)& 0.191 (0.98)& 0.699 (1.0)& 0.798 (0.97)\\ \hline 
-Approximate Entropy (m=10)& 0.759 (0.99)& 0.162 (0.99)& 0.867 (0.99)& 0.534 (1.0)& 0.616 (0.99)\\ \hline 
-Random Excursions *& 0.666 (0.994)& 0.410 (0.962)& 0.287 (0.998)& 0.365 (0.994)& 0.480 (0.985)\\ \hline 
-Random Excursions Variant *& 0.337 (0.988)& 0.519 (0.984)& 0.549 (0.994)& 0.225 (0.995)& 0.533 (0.993)\\ \hline 
-Serial* (m=10)& 0.630 (0.99)& 0.529 (0.99)& 0.460 (0.99)& 0.302 (0.995)& 0.360 (0.985)\\ \hline 
-Linear Complexity& 0.719 (1.0)& 0.739 (0.99)& 0.759 (0.98)& 0.122 (0.97)& 0.514 (0.99)\\ \hline 
+\begin{tabular}{|l|r|r|r|r|r|}
+ \hline 
+Test  
+&$\textcircled{a}$& $\textcircled{b}$ & $\textcircled{c}$ & $\textcircled{d}$ & $\textcircled{e}$ \\ \hline 
+Frequency (Monobit)&0.129 (1.0)& 0.181 (1.0)& 0.637 (0.99)& 0.935 (1.0)& 0.978 (1.0)\\ \hline 
+Frequency  within a Block& 0.275 (1.0)& 0.534 (0.98)& 0.066 (1.0)& 0.719 (1.0)& 0.366 (1.0)\\ \hline 
+Cumulative Sums (Cusum) *& 0.695 (1.0)& 0.540 (1.0)& 0.514 (0.985)& 0.773 (0.995)& 0.506 (0.99)\\ \hline 
+Runs&  0.897 (0.99)& 0.051 (1.0)& 0.102 (0.98)& 0.616 (0.99)& 0.191 (1.0)\\ \hline 
+Longest Run of Ones in a Block&  0.851 (1.0)& 0.595 (0.99)& 0.419 (0.98)& 0.616 (0.98)& 0.897 (1.0)\\ \hline 
+Binary Matrix Rank& 0.419 (1.0)& 0.946 (0.99)& 0.319 (0.99)& 0.739 (0.97)& 0.366 (1.0)\\ \hline 
+Discrete Fourier Transform (Spectral)&  0.867 (1.0)& 0.514 (1.0)& 0.145 (1.0)& 0.224 (0.99)& 0.304 (1.0)\\ \hline 
+Non-overlapping Template Matching*& 0.542 (0.990)& 0.512 (0.989)& 0.505 (0.990)& 0.494 (0.989)& 0.493 (0.991)\\ \hline 
+Overlapping Template Matching&  0.275 (0.99)& 0.080 (0.99)& 0.574 (0.98)& 0.798 (0.99)& 0.834 (0.99)\\ \hline 
+Maurer's "Universal Statistical"&  0.383 (0.99)& 0.991 (0.98)& 0.851 (1.0)& 0.595 (0.98)& 0.514 (1.0)\\ \hline 
+Approximate Entropy (m=10)&  0.935 (1.0)& 0.719 (1.0)& 0.883 (1.0)& 0.719 (0.97)& 0.366 (0.99)\\ \hline 
+Random Excursions *& 0.396 (0.991)& 0.217 (0.989)& 0.445 (0.975)& 0.743 (0.993)& 0.380 (0.990)\\ \hline 
+Random Excursions Variant *& 0.486 (0.997)& 0.373 (0.981)& 0.415 (0.994)& 0.424 (0.991)& 0.380 (0.991)\\ \hline 
+Serial* (m=10)&0.350 (1.0)& 0.678 (0.995)& 0.287 (0.995)& 0.740 (0.99)& 0.301 (0.98)\\ \hline 
+Linear Complexity& 0.455 (0.99)& 0.867 (1.0)& 0.401 (0.99)& 0.191 (0.97)& 0.699 (1.0)\\ \hline 

 \end{tabular}
 \end{tabular}

-\end{scriptsize}
+
+\end{tiny}

 \end{center}
 \caption{NIST SP 800-22 test results ($\mathbb{P}_T$)}
 \label{The passing rate}
 \end{center}
 \caption{NIST SP 800-22 test results ($\mathbb{P}_T$)}
 \label{The passing rate}

-\end{table}
+\end{table*}

 
 
 %%% Local Variables:
 
 
 %%% Local Variables: