1 Let us finally present the pseudorandom number generator $\chi_{\textit{15Rairo}}$,
2 which is based on random walks in $\Gamma_{\{b\}}(f)$.
3 More precisely, let be given a Boolean map $f:\Bool^{\mathsf{N}} \rightarrow
5 a PRNG \textit{Random},
6 an integer $b$ that corresponds to an iteration number (\textit{i.e.}, the length of the walk), and
7 an initial configuration $x^0$.
8 Starting from $x^0$, the algorithm repeats $b$ times
9 a random choice of which edge to follow, and traverses this edge
10 provided it is allowed to do so, \textit{i.e.},
11 when $\textit{Random}(1)$ is not null.
12 The final configuration is thus outputted.
13 This PRNG is formalized in Algorithm~\ref{CI Algorithm:2}.
19 \KwIn{a function $f$, an iteration number $b$, an initial configuration $x^0$ ($n$ bits)}
20 \KwOut{a configuration $x$ ($n$ bits)}
24 \If{$\textit{Random}(1) \neq 0$}{
25 $s\leftarrow{\textit{Random}(n)}$\;
26 $x\leftarrow{F_f(s,x)}$\;
31 \caption{Pseudo Code of the $\chi_{\textit{15Rairo}}$ PRNG}
32 \label{CI Algorithm:2}
36 This PRNG is slightly different from $\chi_{\textit{14Secrypt}}$
37 recalled in Algorithm~\ref{CI Algorithm}.
38 As this latter, the length of the random
39 walk of our algorithm is always constant (and is equal to $b$).
40 However, in the current version, we add the constraint that
41 the probability to execute the function $F_f$ is equal to 0.5 since
42 the output of $\textit{Random(1)}$ is uniform in $\{0,1\}$.
43 This constraint is added to match the theoretical framework of
44 Sect.~\ref{sec:hypercube}.
48 Notice that the chaos property of $G_f$ given in Sect.\ref{sec:proofOfChaos}
49 only requires that the graph $\Gamma_{\{b\}}(f)$ is strongly connected.
50 Since the $\chi_{\textit{15Rairo}}$ algorithm
51 only adds probability constraints on existing edges,
52 it preserves this property.
55 For each number $\mathsf{N}=4,5,6,7,8$ of bits, we have generated
56 the functions according to the method
57 given in Sect.~\ref{sec:SCCfunc}.
58 For each $\mathsf{N}$, we have then restricted this evaluation to the function
59 whose Markov Matrix (issued from Eq.~(\ref{eq:Markov:rairo}))
60 has the smallest practical mixing time.
62 given in Table~\ref{table:nc}.
63 In this table, let us consider for instance
64 the function $\textcircled{a}$ from $\Bool^4$ to $\Bool^4$
65 defined by the following images :
66 $[13, 10, 9, 14, 3, 11, 1, 12, 15, 4, 7, 5, 2, 6, 0, 8]$.
67 In other words, the image of $3~(0011)$ by $\textcircled{a}$ is $14~(1110)$:
68 it is obtained as the binary value of the fourth element in
69 the second list (namely~14).
71 In this table the column
72 that is labeled with $b$ (respectively by $E[\tau]$)
73 gives the practical mixing time
74 where the deviation to the standard distribution is lesser than $10^{-6}$
75 (resp. the theoretical upper bound of stopping time as described in
76 Sect.~\ref{sec:hypercube}).
83 \begin{tabular}{|c|c|c|c|c|}
85 Function $f$ & $f(x)$, for $x$ in $(0,1,2,\hdots,2^n-1)$ & $\mathsf{N}$ & $b$
89 $\textcircled{a}$&[13,10,9,14,3,11,1,12,15,4,7,5,2,6,0,8]&4&64&154\\
93 [29, 22, 25, 30, 19, 27, 24, 16, 21, 6, 5, 28, 23, 26, 1, 17, & 5 & 78 & 236\\
95 31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 7, 20, 11, 18, 0, 4]
100 [55, 60, 45, 44, 58, 62, 61, 48, 53, 50, 52, 36, 59, 34, 33, 49,
103 15, 42, 47, 46, 35, 10, 57, 56, 7, 54, 39, 37, 51, 2, 1, 40, 63,
106 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, 16, 24, 13,
109 12, 29, 8, 43, 14, 41, 0, 5, 38, 4, 6, 11, 3, 9, 32]
114 [111, 94, 93, 116, 122, 90, 125, 88, 115, 126, 119, 84, 123, 98,
117 81, 120, 109, 106, 105, 110, 99, 107, 104, 72, 71, 118, 117,
120 96, 103, 102, 113, 64, 79, 86, 95, 124, 83, 91, 121, 24, 85, 22,
123 69, 20, 19, 114, 17, 112, 77, 76, 13, 108, 74, 10, 9, 73, 67, 66,
127 101, 100, 75, 82, 97, 0, 127, 54, 57, 62, 51, 59, 56, 48, 53, 38,
130 37, 60, 55, 58, 33, 49, 63, 44, 47, 40, 42, 46, 45, 41, 35, 34,
133 39, 52, 43, 50, 32, 36, 29, 28, 61, 92, 26, 18, 89, 25, 87, 30,
136 23, 4, 27, 2, 16, 80, 31, 78, 15, 14, 3, 11, 8, 12, 5, 70, 21,
146 [223, 190, 249, 254, 187, 251, 233, 232, 183, 230, 247, 180, 227,
149 178, 240, 248, 237, 236, 253, 172, 203, 170, 201, 168, 229, 166,
152 165, 244, 163, 242, 241, 192, 215, 220, 205, 216, 218, 222, 221,
155 208, 213, 210, 212, 214, 219, 211, 217, 209, 239, 202, 207, 140,
158 139, 234, 193, 204, 135, 196, 199, 132, 194, 130, 225, 200, 159,
161 62, 185, 252, 59, 250, 169, 56, 191, 246, 245, 52, 243, 50, 176,
164 48, 173, 238, 189, 44, 235, 42, 137, 184, 231, 38, 37, 228, 35,
167 226, 177, 224, 151, 156, 141, 152, 154, 158, 157, 144, 149, 146,
170 148, 150, 155, 147, 153, 145, 175, 206, 143, 136, 11, 142, 129,
173 8, 7, 198, 197, 4, 195, 2, 161, 160, 255, 124, 109, 108, 122,
176 126, 125, 112, 117, 114, 116, 100, 123, 98, 97, 113, 79, 106,
179 111, 110, 99, 74, 121, 120, 71, 118, 103, 101, 115, 66, 65,
182 104, 127, 90, 89, 94, 83, 91, 81, 92, 95, 84, 87, 85, 82, 86,
185 80, 88, 77, 76, 93, 72, 107, 78, 105, 64, 69, 102, 68, 70, 75,
188 67, 73, 96, 55, 58, 45, 188, 51, 186, 61, 40, 119, 182, 181,
191 53, 179, 54, 33, 49, 15, 174, 47, 60, 171, 46, 57, 32, 167, 6,
194 36, 164, 43, 162, 1, 0, 63, 26, 25, 30, 19, 27, 17, 28, 31,
197 20, 23, 21, 18, 22, 16, 24, 13, 10, 29, 14, 3, 138, 41, 12,
200 39, 134, 133, 5, 131, 34, 9, 128]
206 \caption{Functions with DSCC Matrix and smallest MT\label{table:nc}}
211 Let us first discuss about results against the NIST test suite.
212 In our experiments, 100 sequences (s = 100) of 1,000,000 bits are generated and tested.
213 If the value $\mathbb{P}_T$ of any test is smaller than 0.0001, the sequences are considered to be not good enough
214 and the generator is unsuitable. Table~\ref{The passing rate} shows $\mathbb{P}_T$ of sequences based on discrete
215 chaotic iterations using different schemes. If there are at least two statistical values in a test, this test is
216 marked with an asterisk and the average value is computed to characterize the statistics.
217 We can see in Table \ref{The passing rate} that all the rates are greater than 97/100, \textit{i.e.}, all the generators
218 achieve to pass the NIST battery of tests.
223 \renewcommand{\arraystretch}{1.3}
226 \setlength{\tabcolsep}{2pt}
229 \begin{tabular}{|l|l|l|l|l|l|}
231 Method &$\textcircled{a}$& $\textcircled{b}$ & $\textcircled{c}$ & $\textcircled{d}$ & $\textcircled{e}$ \\ \hline\hline
232 Frequency (Monobit)& 0.851 (0.98)& 0.719 (0.99)& 0.699 (0.99)& 0.514 (1.0)& 0.798 (0.99)\\ \hline
233 Frequency (Monobit)& 0.851 (0.98)& 0.719 (0.99)& 0.699 (0.99)& 0.514 (1.0)& 0.798 (0.99)\\ \hline
234 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
235 Cumulative Sums (Cusum) *& 0.301 (0.98)& 0.521 (0.99)& 0.688 (0.99)& 0.888 (1.0)& 0.598 (1.0)\\ \hline
236 Runs& 0.224 (0.97)& 0.383 (0.97)& 0.108 (0.96)& 0.213 (0.99)& 0.616 (0.99)\\ \hline
237 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
238 Binary Matrix Rank& 0.213 (1.0)& 0.867 (0.99)& 0.494 (0.98)& 0.162 (0.99)& 0.924 (0.99)\\ \hline
239 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
240 Unoverlapping Templ. Match.*& 0.505 (0.990)& 0.521 (0.990)& 0.510 (0.989)& 0.511 (0.990)& 0.499 (0.990)\\ \hline
241 Overlapping Temp. Match.& 0.574 (0.98)& 0.304 (0.99)& 0.437 (0.97)& 0.759 (0.98)& 0.275 (0.99)\\ \hline
242 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
243 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
244 Random Excursions *& 0.666 (0.994)& 0.410 (0.962)& 0.287 (0.998)& 0.365 (0.994)& 0.480 (0.985)\\ \hline
245 Random Excursions Variant *& 0.337 (0.988)& 0.519 (0.984)& 0.549 (0.994)& 0.225 (0.995)& 0.533 (0.993)\\ \hline
246 Serial* (m=10)& 0.630 (0.99)& 0.529 (0.99)& 0.460 (0.99)& 0.302 (0.995)& 0.360 (0.985)\\ \hline
247 Linear Complexity& 0.719 (1.0)& 0.739 (0.99)& 0.759 (0.98)& 0.122 (0.97)& 0.514 (0.99)\\ \hline
251 \caption{NIST SP 800-22 test results ($\mathbb{P}_T$)}
252 \label{The passing rate}
