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 $\Bool^n$
+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_n)$ maps to $f(x)=(f_1(x),\dots,f_n(x))$.
+$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;n \rrbracket$ called ``strategy''.
+``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: \llbracket1;n\rrbracket\times \Bool^{n}$ to $\Bool^n$ be defined by
+let $F_f: \Bool^{{\mathsf{N}}} \times \llbracket1;{\mathsf{N}}\rrbracket$ to $\Bool^{\mathsf{N}}$ be defined by
\[
-F_f(i,x)=(x_1,\dots,x_{i-1},f_i(x),x_{i+1},\dots,x_n).
+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^n$ be an initial configuration
+Then, let $x^0\in\Bool^{\mathsf{N}}$ be an initial configuration
and $s\in
-\llbracket1;n\rrbracket^\Nats$ be a strategy,
+\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(s_t,x^t).
+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^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)$.
+$\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 $n=3$.
+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) =
\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}
-\vspace{-1em}
\begin{figure}[ht]
\begin{center}
\includegraphics[scale=0.5]{images/iter_f0c}
\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}
-
-Let thus be given such kind of map.
-This article focusses on studying its iterations according to
-the equation~(\ref{eq:asyn}) with a given strategy.
-First of all, this can be interpreted as walking into its iteration graph
-where the choice of the edge to follow is decided by the strategy.
-Notice that the iteration graph is always a subgraph of
-$n$-cube augemented with all the self-loop, \textit{i.e.}, all the
-edges $(v,v)$ for any $v \in \Bool^n$.
-Next, if we add probabilities on the transition graph, iterations can be
-interpreted as Markov chains.
-
-
-
-
-Let $\pi$, $\mu$ be two distribution on a same set $\Omega$. The total
-variation distance between $\pi$ and $\mu$ is denoted $\tv{\pi-\mu}$ and is
-defined 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)|.$$ Moreover, if
-$\nu$ is a distribution on $\Omega$, one has
-$$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}$$
-
-Let $P$ be the matrix of a markov chain on $\Omega$. $P(x,\cdot)$ is the
-distribution induced by the $x$-th row of $P$. If the markov chain induced by
-$P$ has a stationary distribution $\pi$, then we define
-$$d(t)=\max_{x\in\Omega}\tv{P^t(x,\cdot)-\pi},$$
-and
-
-$$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
-One can prove that
-
-$$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$
-
-It is known that $d(t+1)\leq d(t)$.
-
-
-
-Let $(X_t)_{t\in \mathbb{N}}$ be a sequence of $\Omega$ valued random
-variables. A $\mathbb{N}$-valued random variable $\tau$ is a {\it stopping
- time} for the sequence $(X_i)$ if for each $t$ there exists $B_t\subseteq
-\omega^{t+1}$ such that $\{tau=t\}=\{(X_0,X_1,\ldots,X_t)\in B_t\}$.
-
-Let $(X_t)_{t\in \mathbb{N}}$ be a markov chain and $f(X_{t-1},Z_t)$ a
-random mapping representation of the markov chain. A {\it randomized
- stopping time} for the markov chain is a stopping time for
-$(Z_t)_{t\in\mathbb{N}}$. It he markov chain is irreductible and has $\pi$
-as stationary distribution, then a {\it stationay time} $\tau$ is a
-randomized stopping time (possibily depending on the starting position $x$),
-such that the distribution of $X_\tau$ is $\pi$:
-$$\P_x(X_\tau=y)=\pi(y).$$
-
-
-\JFC{Ou ceci a-t-il ete prouvé}
-\begin{Theo}
-If $\tau$ is a strong stationary time, then $d(t)\leq \max_{x\in\Omega}
-\P_x(\tau > t)$.
-\end{Theo}
-
-% 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
+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.
-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)}
+\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}(n)}$\;
-$x\leftarrow{F_f(s,x)}$\;
+$s\leftarrow{\textit{Random}({\mathsf{N}})}$\;
+$x\leftarrow{F_f(x,s)}$\;
}
return $x$\;
-%\end{scriptsize}
+\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.
+
+
+
+With all this material, we can study the chaos properties of these
+function.
+This is the aims of the next section.
+
