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 us first introduce basic notations.
Let $\mathsf{N}$ be a positive integer. The set $\{1, 2, \hdots , \mathsf{N}\}$
of integers belonging between $1$ and $\mathsf{N}$
is further denoted as $\llbracket 1, \mathsf{N} \rrbracket$.
A  {\emph{Boolean map} $f$ is 
a function from $\Bool^{\mathsf{N}}$  
to itself 
such that 
$x=(x_1,\dots,x_{\mathsf{N}})$ maps to $f(x)=(f_1(x),\dots,f_{\mathsf{N}}(x))$.
In what follows, for any finite set $X$, $|X|$ denotes its cardinality and 
$\lfloor y \rfloor$ is
the largest integer lower than $y$.

Functions are iterated as follows. 
At the $t^{th}$ iteration, only the $s_{t}-$th component is said to be
``iterated'', where $s = \left(s_t\right)_{t \in \mathds{N}}$ is a sequence of indices taken in $\llbracket 1;{\mathsf{N}} \rrbracket$ called ``strategy''. 
Formally,
let $F_f:  \Bool^{{\mathsf{N}}} \times \llbracket1;{\mathsf{N}}\rrbracket$ to $\Bool^{\mathsf{N}}$ be defined by
\[
F_f(x,i)=(x_1,\dots,x_{i-1},f_i(x),x_{i+1},\dots,x_{\mathsf{N}}).
\]
Then, let $x^0\in\Bool^{\mathsf{N}}$ be an initial configuration
and $s\in
\llbracket1;{\mathsf{N}}\rrbracket^\Nats$ be a strategy, 
the dynamics are described by the recurrence
\begin{equation}\label{eq:asyn}
x^{t+1}=F_f(x^t,s_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^{\mathsf{N}}$, and for all $x\in\Bool^{\mathsf{N}}$ and $i\in \llbracket1;{\mathsf{N}}\rrbracket$,
the graph $\Gamma(f)$ contains an arc from $x$ to $F_f(x,i)$.
Each arc $(x,F_f(x,i))$ is labelled with $i$. 


\begin{xpl}
Let us consider for instance ${\mathsf{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*}.
\end{xpl}

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

Let us finally recall the pseudorandom number generator $\chi_{\textit{14Secrypt}}$
\cite{DBLP:conf/secrypt/CouchotHGWB14}
formalized in Algorithm~\ref{CI Algorithm}.
It is based on random walks in $\Gamma(f)$. 
More precisely, let be given a Boolean map $f:\Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$,
an input PRNG \textit{Random},
an integer $b$ that corresponds to a number of iterations, 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.


\begin{algorithm}[ht]
\begin{scriptsize}
%\JFC{Mettre ceci dans une boite flottante}
\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$}
{
$s\leftarrow{\textit{Random}({\mathsf{N}})}$\;
$x\leftarrow{F_f(x,s)}$\;
}
return $x$\;
\end{scriptsize}
\caption{Pseudo Code of the $\chi_{\textit{14Secrypt}}$ PRNG}
\label{CI Algorithm}
\end{algorithm}




Based on this setup,
we can study the chaos properties of these 
function.
This is the aims of the next section. 


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