ajout de fichiers

[16dcc.git] / prng.tex

diff --git a/prng.tex b/prng.tex
index ce720a1739eee61fc0a89dba599bccbd6f8171e7..2d1d7f28a3f5ccb9931caa4b8eafec913fd219f4 100644 (file)
--- a/prng.tex
+++ b/prng.tex
@@ -6,7 +6,7 @@ a PRNG \textit{Random},
 an integer $b$ that corresponds to an iteration number (\textit{i.e.}, the length of the walk), and 
 an initial configuration $x^0$. 
 Starting from $x^0$, the algorithm repeats $b$ times 
 an integer $b$ that corresponds to an iteration number (\textit{i.e.}, the length of the walk), and 
 an initial configuration $x^0$. 
 Starting from $x^0$, the algorithm repeats $b$ times 

-a random choice of which edge to follow, and traverses this edge 
+a random choice of which edge to follow, and crosses this edge 

 provided it is allowed to do so, \textit{i.e.}, 
 when $\textit{Random}(1)$ is not null. 
 The final configuration is thus outputted.
 provided it is allowed to do so, \textit{i.e.}, 
 when $\textit{Random}(1)$ is not null. 
 The final configuration is thus outputted.


@@ -46,7 +46,7 @@ Sect.~\ref{sec:hypercube}.
 
 
 Notice that the chaos property of $G_f$ given in Sect.\ref{sec:proofOfChaos}
 
 
 Notice that the chaos property of $G_f$ given in Sect.\ref{sec:proofOfChaos}

-only requires that the graph $\Gamma_{\{b\}}(f)$ is strongly connected.
+only requires the graph $\Gamma_{\{b\}}(f)$ to be  strongly connected.

 Since the $\chi_{\textit{16HamG}}$ algorithm 
 only adds probability constraints on existing edges, 
 it preserves this property. 
 Since the $\chi_{\textit{16HamG}}$ algorithm 
 only adds probability constraints on existing edges, 
 it preserves this property. 


@@ -54,14 +54,14 @@ 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})) 
 has the smallest practical mixing time.
 Such functions are 
 given in Table~\ref{table:nc}.
 % 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})) 
 has the smallest practical mixing time.
 Such functions are 
 given in Table~\ref{table:nc}.

-In this table, let us consider for instance 
+In this table, let us consider, for instance, 

 the function $\textcircled{a}$ from $\Bool^4$ to $\Bool^4$
 defined by the following images : 
 $[13, 10, 9, 14, 3, 11, 1, 12, 15, 4, 7, 5, 2, 6, 0, 8]$.
 the function $\textcircled{a}$ from $\Bool^4$ to $\Bool^4$
 defined by the following images : 
 $[13, 10, 9, 14, 3, 11, 1, 12, 15, 4, 7, 5, 2, 6, 0, 8]$.


@@ -71,7 +71,7 @@ the  second  list (namely~14).
 
 In this table the column that is labeled with $b$ %(respectively by $E[\tau]$)
 gives the practical mixing time 
 
 In this table the column that is labeled with $b$ %(respectively by $E[\tau]$)
 gives the practical mixing time 

-where the deviation to the standard distribution is lesser than $10^{-6}$.
+where the deviation to the standard distribution is inferior than $10^{-6}$.

 %(resp. the theoretical upper bound of stopping time as described in Sect.~\ref{sec:hypercube}).
 
 
 %(resp. the theoretical upper bound of stopping time as described in Sect.~\ref{sec:hypercube}).
 
 


@@ -110,55 +110,22 @@ $\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]

 &&\\
 
 
 &&\\
 
 


@@ -205,7 +172,7 @@ $\textcircled{e}$&151, 149, 19, 210, 144, 152, 141, 206, 13, 12, 171, 10, 201, 1
 \end{tabular}
 \end{scriptsize}
 \end{center}
 \end{tabular}
 \end{scriptsize}
 \end{center}

-\caption{Functions with DSCC Matrix and smallest MT\label{table:nc}}
+\caption{Functions with DSCC Matrix and smallest MT}\label{table:nc}

 \end{table*}
 
 
 \end{table*}
 
 


@@ -213,46 +180,80 @@ $\textcircled{e}$&151, 149, 19, 210, 144, 152, 141, 206, 13, 12, 171, 10, 201, 1
 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: