ajout de fichiers

[16dcc.git] / prng.tex

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

 which is based on random walks in $\Gamma_{\{b\}}(f)$. 
 More precisely, let be given a Boolean map $f:\Bool^{\mathsf{N}} \rightarrow 
 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}$,
+\Bool^{\mathsf{N}}$,

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

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


@@ -16,19 +16,19 @@ This PRNG is formalized in Algorithm~\ref{CI Algorithm:2}.
 
 \begin{algorithm}[ht]
 %\begin{scriptsize}
 
 \begin{algorithm}[ht]
 %\begin{scriptsize}

-\KwIn{a function $f$, an iteration number $b$, an initial configuration $x^0$ ($n$ bits)}
-\KwOut{a configuration $x$ ($n$ bits)}
+\KwIn{a function $f$, an iteration number $b$, an initial configuration $x^0$ ($\mathsf{N}$ bits)}
+\KwOut{a configuration $x$ ($\mathsf{N}$ bits)}

 $x\leftarrow x^0$\;
 \For{$i=0,\dots,b-1$}
 {
 \If{$\textit{Random}(1) \neq 0$}{
 $x\leftarrow x^0$\;
 \For{$i=0,\dots,b-1$}
 {
 \If{$\textit{Random}(1) \neq 0$}{

-$s\leftarrow{\textit{Random}(n)}$\;
-$x\leftarrow{F_f(s,x)}$\;
+$s^0\leftarrow{\textit{Random}(\mathsf{N})}$\;
+$x\leftarrow{F_f(x,s^0)}$\;

 }
 }
 return $x$\;
 %\end{scriptsize}
 }
 }
 return $x$\;
 %\end{scriptsize}

-\caption{Pseudo Code of the $\chi_{\textit{15Rairo}}$ PRNG}
+\caption{Pseudo Code of the $\chi_{\textit{16HamG}}$ PRNG}

 \label{CI Algorithm:2}
 \end{algorithm}
 
 \label{CI Algorithm:2}
 \end{algorithm}
 


@@ -46,21 +46,22 @@ 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.
-Since the $\chi_{\textit{15Rairo}}$ algorithm 
+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. 
 
 
 For each number $\mathsf{N}=4,5,6,7,8$ of bits, we have generated 
 the functions according to the method 
 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 
 the functions according to the method 

-given in Sect.~\ref{sec:SCCfunc}.
+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}.
 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]$.


@@ -68,142 +69,110 @@ In other words,  the image of $3~(0011)$ by $\textcircled{a}$ is $14~(1110)$:
 it is obtained as  the  binary  value  of  the  fourth element  in  
 the  second  list (namely~14).  
 
 it is obtained as  the  binary  value  of  the  fourth element  in  
 the  second  list (namely~14).  
 

-In this table the column 
-that is labeled with $b$ (respectively by $E[\tau]$)
+In this table the column 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 lesser than $10^{-6}$
-(resp. the theoretical upper bound of stopping time as described in 
-Sect.~\ref{sec:hypercube}).
+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}).

 
 
 
 \begin{table*}[t]
 \begin{center}
 \begin{scriptsize}
 
 
 
 \begin{table*}[t]
 \begin{center}
 \begin{scriptsize}

-\begin{tabular}{|c|c|c|c|c|}
+\begin{tabular}{|c|c|c|c|}

 \hline
 Function $f$ & $f(x)$, for $x$ in $(0,1,2,\hdots,2^n-1)$ & $\mathsf{N}$ & $b$ 
 \hline
 Function $f$ & $f(x)$, for $x$ in $(0,1,2,\hdots,2^n-1)$ & $\mathsf{N}$ & $b$ 

-&$E[\tau]$\\ 
+\\ 

 \hline
 %%%%% n= 4
 \hline
 %%%%% n= 4

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

 \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 & 236\\
+[29, 22, 25, 30, 19, 27, 24, 16, 21, 6, 5, 28, 23, 26, 1, 17, & 5 & 78 \\

 &
  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]

-&&&\\
+&&\\

 %%%%% n= 6
 \hline
 &
 [55, 60, 45, 44, 58, 62, 61, 48, 53, 50, 52, 36, 59, 34, 33, 49,
 %%%%% n= 6
 \hline
 &
 [55, 60, 45, 44, 58, 62, 61, 48, 53, 50, 52, 36, 59, 34, 33, 49,

-&&&\\
+&&\\

 &
  15, 42, 47, 46, 35, 10, 57, 56, 7, 54, 39, 37, 51, 2, 1, 40, 63,
 &
  15, 42, 47, 46, 35, 10, 57, 56, 7, 54, 39, 37, 51, 2, 1, 40, 63,

-&&&\\
+&&\\

 $\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&335\\
+&6&88\\

 &
 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]

-&&&\\
+&&\\

 %%%%% n= 7
 \hline
 &
 %%%%% n= 7
 \hline
 &

-[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, 
-&&&\\
-$\textcircled{d}$& 
-69, 20, 19, 114, 17, 112, 77, 76, 13, 108, 74, 10, 9, 73, 67, 66,
-&7 & 99&450\\
-
-& 
- 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]
-&&&\\
+[111, 124, 93, 120, 122, 114, 89, 121, 87, 126, 125, 84, 123, 82, 
+&&\\
+&112, 80, 79, 106, 105, 110, 75, 107, 73, 108, 119, 100, 117, 116, 
+&&\\
+&103, 102, 101, 97, 31, 86, 95, 94, 83, 26, 88, 24, 71, 118, 69, 
+&&\\
+&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, 
+&&\\
+&38, 43, 50, 32, 48, 29, 28, 61, 92, 91, 18, 17, 25, 19, 30, 85, 
+&&\\
+&22, 27, 2, 81, 0, 13, 78, 77, 14, 3, 11, 8, 12, 23, 4, 21, 20, 
+&&\\
+&67, 66, 5, 1]
+&&\\

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

-[223, 190, 249, 254, 187, 251, 233, 232, 183, 230, 247, 180, 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,
-&&&\\
-$\textcircled{e}$&
-8, 7, 198, 197, 4, 195, 2, 161, 160, 255, 124, 109, 108, 122,
-&8&110&582\\
-&
- 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]
-&&&\\
+[223, 238, 249, 254, 243, 251, 233, 252, 183, 244, 229, 245, 227, 
+&&\\
+&246, 240, 176, 175, 174, 253, 204, 203, 170, 169, 248, 247, 226, 
+&&\\
+&228, 164, 163, 162, 161, 192, 215, 220, 205, 216, 155, 222, 221, 
+&&\\
+&208, 213, 150, 212, 214, 219, 211, 145, 209, 239, 202, 207, 140, 
+&&\\
+&195, 234, 193, 136, 231, 230, 199, 197, 131, 198, 225, 200, 63, 
+&&\\
+&188, 173, 184, 186, 250, 57, 168, 191, 178, 180, 52, 187, 242, 
+&&\\
+&241, 48, 143, 46, 237, 236, 235, 138, 185, 232, 135, 38, 181, 165, 
+&&\\
+&35, 166, 33, 224, 31, 30, 153, 158, 147, 218, 217, 156, 159, 148, 
+&&\\
+$\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, 
+&&\\
+&125, 104, 103, 114, 116, 118, 123, 98, 97, 113, 79, 126, 111, 110, 
+&&\\
+&99, 74, 121, 72, 71, 70, 117, 101, 115, 102, 65, 112, 127, 90, 89, 
+&&\\
+&94, 83, 91, 81, 92, 95, 84, 87, 85, 82, 86, 80, 88, 77, 76, 93, 
+&&\\
+&108, 107, 78, 105, 64, 69, 66, 68, 100, 75, 67, 73, 96, 55, 190, 
+&&\\
+&189, 62, 51, 59, 41, 60, 119, 182, 37, 53, 179, 54, 177, 32, 45, 
+&&\\
+&44, 61, 172, 11, 58, 9, 56, 167, 34, 36, 4, 43, 50, 49, 160, 23, 
+&&\\
+&28, 157, 24, 26, 154, 29, 16, 21, 18, 20, 22, 27, 146, 25, 17, 47, 
+&&\\
+&142, 15, 14, 139, 42, 1, 40, 39, 134, 7, 5, 2, 6, 129, 8]
+&&\\

 \hline
 \end{tabular}
 \end{scriptsize}
 \end{center}
 \hline
 \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*}
 
 


@@ -211,45 +180,85 @@ $\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:
+%%% mode: latex
+%%% TeX-master: "main"
+%%% ispell-dictionary: "american"
+%%% mode: flyspell
+%%% End: