prng.tex

   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
   4 \Bool^\mathsf{N}$,
   5 a PRNG \textit{Random},
   6 an integer $b$ that corresponds 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 traverse it, \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}.
  14
  15
  16
  17 \begin{algorithm}[ht]
  18 %\begin{scriptsize}
  19 \KwIn{a function $f$, an iteration number $b$, an initial configuration $x^0$ ($n$ bits)}
  20 \KwOut{a configuration $x$ ($n$ bits)}
  21 $x\leftarrow x^0$\;
  22 \For{$i=0,\dots,b-1$}
  23 {
  24 \If{$\textit{Random}(1) \neq 0$}{
  25 $s\leftarrow{\textit{Random}(n)}$\;
  26 $x\leftarrow{F_f(s,x)}$\;
  27 }
  28 }
  29 return $x$\;
  30 %\end{scriptsize}
  31 \caption{Pseudo Code of the $\chi_{\textit{15Rairo}}$ PRNG}
  32 \label{CI Algorithm}
  33 \end{algorithm}
  34
  35
  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}.
  45
  46
  47
  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}}$ algorithme
  51 only adds propbability constraints on existing edges,
  52 it preserves this property.
  53
  54