ajout espace bib

[rairo15.git] / prng.tex

diff --git a/prng.tex b/prng.tex
index 0667ccaacfa4bc2ce21fc3284634768b8a2b0edc..5025b4eca7a9d1115ab01749ab0afe33f06660bf 100644 (file)
--- a/prng.tex
+++ b/prng.tex
@@ -1,16 +1,16 @@
-Let us finally present the pseudorandom number generator $\chi_{\textit{15Rairo}}$
+Let us finally present the pseudorandom number generator $\chi_{\textit{15Rairo}}$,

 which is based on random walks in $\Gamma_{\{b\}}(f)$. 
 More precisely, let be given a Boolean map $f:\Bool^{\mathsf{N}} \rightarrow 
 \Bool^\mathsf{N}$,
 a PRNG \textit{Random},
 which is based on random walks in $\Gamma_{\{b\}}(f)$. 
 More precisely, let be given a Boolean map $f:\Bool^{\mathsf{N}} \rightarrow 
 \Bool^\mathsf{N}$,
 a PRNG \textit{Random},

-an integer $b$ that corresponds an iteration number (\textit{i.e.}, the length of the walk), and 
+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 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 
-provided it is allowed to traverse it, \textit{i.e.}, 
+a random choice of which edge to follow, and traverses 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.
 when $\textit{Random}(1)$ is not null. 
 The final configuration is thus outputted.

-This PRNG is formalized in Algorithm~\ref{CI Algorithm}.
+This PRNG is formalized in Algorithm~\ref{CI Algorithm:2}.

 
 
 
 
 
 


@@ -29,7 +29,7 @@ $x\leftarrow{F_f(s,x)}$\;
 return $x$\;
 %\end{scriptsize}
 \caption{Pseudo Code of the $\chi_{\textit{15Rairo}}$ PRNG}
 return $x$\;
 %\end{scriptsize}
 \caption{Pseudo Code of the $\chi_{\textit{15Rairo}}$ PRNG}

-\label{CI Algorithm}
+\label{CI Algorithm:2}

 \end{algorithm}
 
 
 \end{algorithm}
 
 


@@ -47,14 +47,14 @@ Sect.~\ref{sec:hypercube}.
 
 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.
 
 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.

-Since the $\chi_{\textit{15Rairo}}$ algorithme 
-only adds propbability constraints on existing edges, 
+Since the $\chi_{\textit{15Rairo}}$ algorithm 
+only adds probability constraints on existing edges, 

 it preserves this property. 
 
 
 For each number $\mathsf{N}=4,5,6,7,8$ of bits, we have generated 
 it preserves this property. 
 
 
 For each number $\mathsf{N}=4,5,6,7,8$ of bits, we have generated 

-the functions according the method 
-given in Sect.~\ref{sec:SCCfunc} .
+the functions according to the method 
+given in Sect.~\ref{sec:SCCfunc}.

 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.
 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.


@@ -69,10 +69,10 @@ it is obtained as  the  binary  value  of  the  fourth element  in
 the  second  list (namely~14).  
 
 In this table the column 
 the  second  list (namely~14).  
 
 In this table the column 

-which is labeled with $b$ (respectively by $E[\tau]$)
+that is labeled with $b$ (respectively by $E[\tau]$)

 gives the practical mixing time 
 gives the practical mixing time 

-where the deviation to the standard distribution is less than $10^{-6}$
-(resp. the theoretical upper bound ofstopping time as described in 
+where the deviation to the standard distribution is lesser than $10^{-6}$
+(resp. the theoretical upper bound of stopping time as described in 

 Sect.~\ref{sec:hypercube}).
 
 
 Sect.~\ref{sec:hypercube}).
 
 


@@ -86,11 +86,11 @@ Function $f$ & $f(x)$, for $x$ in $(0,1,2,\hdots,2^n-1)$ & $\mathsf{N}$ & $b$
 &$E[\tau]$\\ 
 \hline
 %%%%% n= 4
 &$E[\tau]$\\ 
 \hline
 %%%%% n= 4

-$\textcircled{a}$&[13,10,9,14,3,11,1,12,15,4,7,5,2,6,0,8]&4&64&\\
+$\textcircled{a}$&[13,10,9,14,3,11,1,12,15,4,7,5,2,6,0,8]&4&64&154\\

 \hline
 %%%%% n= 5
 $\textcircled{b}$& 
 \hline
 %%%%% n= 5
 $\textcircled{b}$& 

-[29, 22, 25, 30, 19, 27, 24, 16, 21, 6, 5, 28, 23, 26, 1, 17, & 5 & 78 & \\
+[29, 22, 25, 30, 19, 27, 24, 16, 21, 6, 5, 28, 23, 26, 1, 17, & 5 & 78 & 236\\

 &
  31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 7, 20, 11, 18, 0, 4]
 &&&\\
 &
  31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 7, 20, 11, 18, 0, 4]
 &&&\\


@@ -104,7 +104,7 @@ $\textcircled{b}$&
 &&&\\
 $\textcircled{c}$&
  26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, 16, 24, 13, 
 &&&\\
 $\textcircled{c}$&
  26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, 16, 24, 13, 

-&6&88&\\
+&6&88&335\\

 &
 12, 29, 8, 43, 14, 41, 0, 5, 38, 4, 6, 11, 3, 9, 32]
 &&&\\
 &
 12, 29, 8, 43, 14, 41, 0, 5, 38, 4, 6, 11, 3, 9, 32]
 &&&\\


@@ -121,7 +121,7 @@ $\textcircled{c}$&
 &&&\\
 $\textcircled{d}$& 
 69, 20, 19, 114, 17, 112, 77, 76, 13, 108, 74, 10, 9, 73, 67, 66,
 &&&\\
 $\textcircled{d}$& 
 69, 20, 19, 114, 17, 112, 77, 76, 13, 108, 74, 10, 9, 73, 67, 66,

-&7 & 99&\\
+&7 & 99&450\\

 
 & 
  101, 100, 75, 82, 97, 0, 127, 54, 57, 62, 51, 59, 56, 48, 53, 38,
 
 & 
  101, 100, 75, 82, 97, 0, 127, 54, 57, 62, 51, 59, 56, 48, 53, 38,


@@ -171,7 +171,7 @@ $\textcircled{d}$&
 &&&\\
 $\textcircled{e}$&
 8, 7, 198, 197, 4, 195, 2, 161, 160, 255, 124, 109, 108, 122,
 &&&\\
 $\textcircled{e}$&
 8, 7, 198, 197, 4, 195, 2, 161, 160, 255, 124, 109, 108, 122,

-&8&110&\\
+&8&110&582\\

 &
  126, 125, 112, 117, 114, 116, 100, 123, 98, 97, 113, 79, 106,
 &&&\\
 &
  126, 125, 112, 117, 114, 116, 100, 123, 98, 97, 113, 79, 106,
 &&&\\


@@ -214,7 +214,9 @@ If the value $\mathbb{P}_T$ of any test is smaller than 0.0001, the sequences ar
 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
 marked with an asterisk and the average value is computed to characterize the statistics.
 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
 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 pass the NIST test.
+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.
+

 
 
 \begin{table} 
 
 
 \begin{table} 


@@ -224,6 +226,26 @@ We can see in Table \ref{The passing rate} that all the rates are greater than 9
 \setlength{\tabcolsep}{2pt}
 
 
 \setlength{\tabcolsep}{2pt}
 
 

+\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 
+\end{tabular}

 \end{scriptsize}
 \end{center}
 \caption{NIST SP 800-22 test results ($\mathbb{P}_T$)}
 \end{scriptsize}
 \end{center}
 \caption{NIST SP 800-22 test results ($\mathbb{P}_T$)}