


In what follows, we consider the Boolean algebra on the set 
$\Bool=\{0,1\}$ with the classical operators of conjunction '.', 
of disjunction '+', of negation '$\overline{~}$', and of 
disjunctive union $\oplus$. 

Let $n$ be a positive integer. A  {\emph{Boolean map} $f$ is 
a function from the Boolean domain 
 to itself 
such that 
$x=(x_1,\dots,x_n)$ maps to $f(x)=(f_1(x),\dots,f_n(x))$.
Functions are iterated as follows. 
At the $t^{th}$ iteration, only the $s_{t}-$th component is
``iterated'', where $s = \left(s_t\right)_{t \in \mathds{N}}$ is a sequence of indices taken in $\llbracket 1;n \rrbracket$ called ``strategy''. Formally,
let $F_f: \llbracket1;n\rrbracket\times \Bool^{n}$ to $\Bool^n$ be defined by
\[
F_f(i,x)=(x_1,\dots,x_{i-1},f_i(x),x_{i+1},\dots,x_n).
\]
Then, let $x^0\in\Bool^n$ be an initial configuration
and $s\in
\llbracket1;n\rrbracket^\Nats$ be a strategy, 
the dynamics are described by the recurrence
\begin{equation}\label{eq:asyn}
x^{t+1}=F_f(s_t,x^t).
\end{equation}


Let be given a Boolean map $f$. Its associated   
{\emph{iteration graph}}  $\Gamma(f)$ is the
directed graph such that  the set of vertices is
$\Bool^n$, and for all $x\in\Bool^n$ and $i\in \llbracket1;n\rrbracket$,
the graph $\Gamma(f)$ contains an arc from $x$ to $F_f(i,x)$. 

\begin{xpl}
Let us consider for instance $n=3$.
Let 
$f^*: \Bool^3 \rightarrow \Bool^3$ be defined by

$f^*(x_1,x_2,x_3) = 
(x_2 \oplus x_3, \overline{x_1}\overline{x_3} + x_1\overline{x_2},
\overline{x_1}\overline{x_3} + x_1x_2)$
The iteration graph $\Gamma(f^*)$ of this function is given in 
Figure~\ref{fig:iteration:f*}.

\vspace{-1em}
\begin{figure}[ht]
\begin{center}
\includegraphics[scale=0.5]{images/iter_f0b}
\end{center}
\vspace{-0.5em}
\caption{Iteration Graph $\Gamma(f^*)$ of the function $f^*$}\label{fig:iteration:f*}
\end{figure}
\end{xpl}

\vspace{-0.5em}
It is easy to associate a Markov Matrix $M$ to such a graph $G(f)$
as follows:

$M_{ij} = \frac{1}{n}$ if there is an edge from $i$ to $j$ in $\Gamma(f)$ and $i \neq j$;  $M_{ii} = 1 - \sum\limits_{j=1, j\neq i}^n M_{ij}$; and $M_{ij} = 0$ otherwise.

\begin{xpl}
The Markov matrix associated to the function $f^*$ is 

\[
M=\dfrac{1}{3} \left(
\begin{array}{llllllll}
1&1&1&0&0&0&0&0 \\
1&1&0&0&0&1&0&0 \\
0&0&1&1&0&0&1&0 \\
0&1&1&1&0&0&0&0 \\
1&0&0&0&1&0&1&0 \\
0&0&0&0&1&1&0&1 \\
0&0&0&0&1&0&1&1 \\
0&0&0&1&0&1&0&1 
\end{array}
\right)
\]



 

\end{xpl}


It is usual to check whether rows of such kind of matrices
converge to a specific 
distribution. 
Let us first recall the  \emph{Total Variation} distance $\tv{\pi-\mu}$,
which is defined for two distributions $\pi$ and $\mu$ on the same set 
$\Omega$  by:
$$\tv{\pi-\mu}=\max_{A\subset \Omega} |\pi(A)-\mu(A)|.$$ 
% It is known that
% $$\tv{\pi-\mu}=\frac{1}{2}\sum_{x\in\Omega}|\pi(x)-\mu(x)|.$$

Let then $M(x,\cdot)$ be the
distribution induced by the $x$-th row of $M$. If the Markov chain
induced by
$M$ has a stationary distribution $\pi$, then we define
$$d(t)=\max_{x\in\Omega}\tv{M^t(x,\cdot)-\pi}.$$
Intuitively $d(t)$ is the largest deviation between
the distribution $\pi$ and $M^t(x,\cdot)$, which 
is the result of iterating $t$ times the function.
Finally, let $\varepsilon$ be a positive number, the \emph{mixing time} 
with respect to $\varepsilon$ is given by
$$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
It defines the smallest iteration number 
that is sufficient to obtain a deviation lesser than $\varepsilon$.
% Notice that the upper and lower bounds of mixing times cannot    
% directly be computed with eigenvalues formulae as expressed 
% in~\cite[Chap. 12]{LevinPeresWilmer2006}. The authors of this latter work  
% only consider reversible Markov matrices whereas we do no restrict our 
% matrices to such a form.



Let us finally present the pseudorandom number generator $\chi_{\textit{14Secrypt}}$
which is based on random walks in $\Gamma(f)$. 
More precisely, let be given a Boolean map $f:\Bool^n \rightarrow \Bool^n$,
a PRNG \textit{Random},
an integer $b$ that corresponds to an awaited mixing time, 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.
The final configuration is thus outputted.
This PRNG is formalized in Algorithm~\ref{CI Algorithm}.



\vspace{-1em}
\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)}
$x\leftarrow x^0$\;
\For{$i=0,\dots,b-1$}
{
$s\leftarrow{\textit{Random}(n)}$\;
$x\leftarrow{F_f(s,x)}$\;
}
return $x$\;
%\end{scriptsize}
\caption{Pseudo Code of the $\chi_{\textit{14Secrypt}}$ PRNG}
\label{CI Algorithm}
\end{algorithm}
\vspace{-0.5em}
This PRNG is a particularized version of Algorithm given in~\cite{BCGR11}.
Compared to this latter, the length of the random 
walk of our algorithm is always constant (and is equal to $b$) whereas it 
was given by a second PRNG in this latter.
However, all the theoretical results that are given in~\cite{BCGR11} remain
true since the proofs do not rely on this fact. 

Let $f: \Bool^{n} \rightarrow \Bool^{n}$.
It has been shown~\cite[Th. 4, p. 135]{BCGR11}} that 
if its iteration graph is strongly connected, then 
the output of $\chi_{\textit{14Secrypt}}$ follows 
a law that tends to the uniform distribution 
if and only if its Markov matrix is a doubly stochastic matrix.
  
Let us now present  a method to
generate  functions
with Doubly Stochastic matrix and Strongly Connected iteration graph,
 denoted as DSSC matrix.   

