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 
\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 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.
This PRNG is formalized in Algorithm~\ref{CI Algorithm:2}.



\begin{algorithm}[ht]
%\begin{scriptsize}
\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$}{
$s^0\leftarrow{\textit{Random}(\mathsf{N})}$\;
$x\leftarrow{F_f(x,s^0)}$\;
}
}
return $x$\;
%\end{scriptsize}
\caption{Pseudo Code of the $\chi_{\textit{16HamG}}$ PRNG}
\label{CI Algorithm:2}
\end{algorithm}


This PRNG is slightly different from $\chi_{\textit{14Secrypt}}$
recalled in Algorithm~\ref{CI Algorithm}.
As this latter, the length of the random 
walk of our algorithm is always constant (and is equal to $b$). 
However, in the current version, we add the constraint that   
the probability to execute the function $F_f$ is equal to 0.5 since
the output of $\textit{Random(1)}$ is uniform in $\{0,1\}$.  
This constraint is added to match the theoretical framework of 
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.
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 
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}.
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]$.
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).  

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}$.
%(resp. the theoretical upper bound of stopping time as described in Sect.~\ref{sec:hypercube}).



\begin{table*}[t]
\begin{center}
\begin{scriptsize}
\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
%%%%% n= 4
$\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}$& 
[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]
&&\\
%%%%% 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,
&&\\
$\textcircled{c}$&
 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, 16, 24, 13, 
&6&88\\
&
12, 29, 8, 43, 14, 41, 0, 5, 38, 4, 6, 11, 3, 9, 32]
&&\\
%%%%% n= 7
\hline
&
[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
&
[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}
\caption{Functions with DSCC Matrix and smallest MT\label{table:nc}}
\end{table*}



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

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 aginst this statistical tests.


\begin{table*} 
\renewcommand{\arraystretch}{1.3}
\begin{center}
\begin{tiny}
\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 
\begin{tabular}{|l|r|r|r|r|r||r|r|r|r|r|}
 \hline 
Test & $\textit{MT}_4$ & $\textit{MT}_5$& $\textit{MT}_6$& $\textit{MT}_7$& $\textit{MT}_8$
&$\textcircled{a}$& $\textcircled{b}$ & $\textcircled{c}$ & $\textcircled{d}$ & $\textcircled{e}$ \\ \hline 
Frequency (Monobit)& 0.924 (1.0)& 0.678 (0.98)& 0.102 (0.97)& 0.213 (0.98)& 0.719 (0.99)& 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.514 (1.0)& 0.419 (0.98)& 0.129 (0.98)& 0.275 (0.99)& 0.455 (0.99)& 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.668 (1.0)& 0.568 (0.99)& 0.881 (0.98)& 0.529 (0.98)& 0.657 (0.995)& 0.695 (1.0)& 0.540 (1.0)& 0.514 (0.985)& 0.773 (0.995)& 0.506 (0.99)\\ \hline 
Runs& 0.494 (0.99)& 0.595 (0.97)& 0.071 (0.97)& 0.017 (1.0)& 0.834 (1.0)& 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.366 (0.99)& 0.554 (1.0)& 0.042 (0.99)& 0.051 (0.99)& 0.897 (0.97)& 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.275 (0.98)& 0.494 (0.99)& 0.719 (1.0)& 0.334 (0.98)& 0.637 (0.99)& 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.122 (0.98)& 0.108 (0.99)& 0.108 (1.0)& 0.514 (0.99)& 0.534 (0.98)& 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.483 (0.990)& 0.507 (0.990)& 0.520 (0.988)& 0.494 (0.988)& 0.515 (0.989)& 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.595 (0.99)& 0.759 (1.0)& 0.637 (1.0)& 0.554 (0.99)& 0.236 (1.0)& 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.202 (0.99)& 0.000 (0.99)& 0.514 (0.98)& 0.883 (0.97)& 0.366 (0.99)& 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.616 (0.99)& 0.145 (0.99)& 0.455 (0.99)& 0.262 (0.97)& 0.494 (1.0)& 0.935 (1.0)& 0.719 (1.0)& 0.883 (1.0)& 0.719 (0.97)& 0.366 (0.99)\\ \hline 
Random Excursions *& 0.275 (1.0)& 0.495 (0.975)& 0.465 (0.979)& 0.452 (0.991)& 0.260 (0.989)& 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.382 (0.995)& 0.400 (0.994)& 0.417 (0.984)& 0.456 (0.991)& 0.389 (0.991)& 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.629 (0.99)& 0.963 (0.99)& 0.366 (0.995)& 0.537 (0.985)& 0.253 (0.995)& 0.350 (1.0)& 0.678 (0.995)& 0.287 (0.995)& 0.740 (0.99)& 0.301 (0.98)\\ \hline 
Linear Complexity& 0.494 (0.99)& 0.514 (0.98)& 0.145 (1.0)& 0.657 (0.98)& 0.145 (0.99)& 0.455 (0.99)& 0.867 (1.0)& 0.401 (0.99)& 0.191 (0.97)& 0.699 (1.0)\\ \hline 
\end{tabular}
\end{tiny}
\end{center}
\caption{NIST SP 800-22 test results ($\mathbb{P}_T$)}
\label{The passing rate}
\end{table*}


%%% Local Variables:
%%% mode: latex
%%% TeX-master: "main"
%%% ispell-dictionary: "american"
%%% mode: flyspell
%%% End:
