pch

[16dcc.git] / chaos.tex

Let us us first recall the chaos theoretical context presented 
in~\cite{bcgr11:ip}. In this article, the space of interest 
is $\Bool^{{\mathsf{N}}} \times \llbracket1;{\mathsf{N}}\rrbracket^{\Nats}$ 
and the iteration function $\mathcal{H}_f$ is  
the map from 
$\Bool^{{\mathsf{N}}} \times \llbracket1;{\mathsf{N}}\rrbracket^{\Nats}$ 
to itself defined by
\[
\mathcal{H}_f(x,s)=(F_f(x,s_0),\sigma(s)).
\] 
In this definition, 
$\sigma: \llbracket1;{\mathsf{N}}\rrbracket^{\Nats} \longrightarrow
 \llbracket1;{\mathsf{N}}\rrbracket^{\Nats} 
$
 is a shift operation on sequences (\textit{i.e.}, a function that removes the 
first element of the sequence) formally defined with
$$
\sigma((u^k)_{k \in \Nats}) =  (u^{k+1})_{k \in \Nats}. 
$$

We have proven~\cite[Theorem 1]{bcgr11:ip} that   
$\mathcal{H}_f$ is chaotic in 
$\Bool^{{\mathsf{N}}} \times \llbracket1;{\mathsf{N}}\rrbracket^{\Nats}$
if and only if $\Gamma(f)$ is strongly connected.
However, the corrolary which would say that $\chi_{\textit{14Secrypt}}$ is chaotic 
cannot be directly deduced since we do not output all the successive
values of iterating $F_f$. Only a a few of them is concerned and 
any subsequence of a chaotic sequence  is   not  necessarily  
a   chaotic  sequence  too.
This necessitates a rigorous proof, which is the aim of this section.





\subsection{Devaney's Chaotic Dynamical Systems}
\label{subsec:Devaney}


Consider a topological space $(\mathcal{X},\tau)$ and a continuous function $f :
\mathcal{X} \rightarrow \mathcal{X}$.

\begin{definition}
The function $f$ is said to be \emph{topologically transitive} if, for any pair of open sets
$U,V \subset \mathcal{X}$, there exists $k>0$ such that $f^k(U) \cap V \neq
\varnothing$.
\end{definition}

\begin{definition}
An element $x$ is a \emph{periodic point} for $f$ of period $n\in \mathds{N}^*$
if $f^{n}(x)=x$.% The set of periodic points of $f$ is denoted $Per(f).$
\end{definition}

\begin{definition}
$f$ is said to be \emph{regular} on $(\mathcal{X}, \tau)$ if the set of periodic
points for $f$ is dense in $\mathcal{X}$: for any point $x$ in $\mathcal{X}$,
any neighborhood of $x$ contains at least one periodic point (without
necessarily the same period).
\end{definition}


\begin{definition}[Devaney's formulation of chaos~\cite{Devaney}]
The function $f$ is said to be \emph{chaotic} on $(\mathcal{X},\tau)$ if $f$ is regular and
topologically transitive.
\end{definition}

The chaos property is strongly linked to the notion of ``sensitivity'', defined
on a metric space $(\mathcal{X},d)$ by:

\begin{definition}
\label{sensitivity} The function $f$ has \emph{sensitive dependence on initial conditions}
if there exists $\delta >0$ such that, for any $x\in \mathcal{X}$ and any
neighborhood $V$ of $x$, there exist $y\in V$ and $n > 0$ such that
$d\left(f^{n}(x), f^{n}(y)\right) >\delta $.

The constant $\delta$ is called the \emph{constant of sensitivity} of $f$.
\end{definition}

Indeed, Banks \emph{et al.} have proven in~\cite{Banks92} that when $f$ is
chaotic and $(\mathcal{X}, d)$ is a metric space, then $f$ has the property of
sensitive dependence on initial conditions (this property was formerly an
element of the definition of chaos). 


\subsection{A Metric Space for PRNG Iterations}

% Define by $\mathcal{S}_X$ the set of sequences whose elements belong in $X \subset \mathds{N}, X \neq \varnothing$,
% that is, $\mathcal{S}_X = \mathcal{X}^\mathds{N}$.
% Let $\mathsf{N} \in \mathds{N}^\ast$, $f:\mathds{B}^\mathsf{N} \rightarrow \mathds{B}^\mathsf{N}$, and
% $\mathcal{P} \subset \mathds{N}^\ast$ a non empty and finite set of integers.

% Any couple $(u,v) \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket} \times \mathcal{S}_\mathcal{P}$ defines
% a ``chaotic iterations based'' pseudorandom number generator, which is denoted by  $\textit{CIPRNG}_f^2(u,v)$~\cite{wbg10:ip}. It is 
% defined as follows:
% \begin{equation}
% \label{CIPRNGver2}
% \left\{
% \begin{array}{l}
%  x^0 \in \mathds{B}^\mathsf{N}\\
%  \forall n \in \mathds{N}, \forall i \in \llbracket 1, \mathsf{N} \rrbracket, x_i^{n+1} = \left\{ \begin{array}{ll} f(x^n)_i & \text{if  }~ i=u^n \\ x_i^n & \text{else} \end{array} \right.\\
%  \forall n \in \mathds{N}, y^n = x^{v^n} .
% \end{array}
% \right.
% \end{equation}
% The outputted sequence produced by this generator is $\left(y^n\right)_{n \in \mathds{N}}$. 
% Remark that, given a sequence $S \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$ called a ``chaotic strategy'',
% the following way to iterate: 
% $$x^0 \in \mathds{B}^\mathsf{N}, \forall n \in \mathds{N}, \forall i \in \llbracket 1, \mathsf{N} \rrbracket,  x_i^{n+1} = \left\{ \begin{array}{ll} f(x^n)_i & \text{if  }~ i=S^n \\ x_i^n & \text{else} \end{array} \right. ,$$
% is referred in the discrete mathematics literature as ``chaotic iterations''~\cite{Robert} (a terminology which has
% \emph{a priori} no relation with the mathematical theory of chaos recalled previously), which
% explains the name provided to these categories of pseudorandom number generators.


% The formerly proposed $\textit{CIPRNG}_f^1(u)$~\cite{bgw09:ip,guyeuxTaiwan10} is equal to \linebreak $\textit{CIPRNG}_f^2\left(u,\left(1\right)_{n\in \mathds{N}}\right)$, where $\left(1\right)_{n\in \mathds{N}}$ is the sequence that is 
% uniformly equal to 1. 
% It has been proven as chaotic for the vectorial Boolean negation $f_0:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N}$, 
% $(x_1, \hdots , x_\mathsf{N}) \longmapsto (\overline{x_1}, \hdots, \overline{x_\mathsf{N}})$ in \cite{bgw09:ip} 
% and for a larger set of well-chosen iteration functions in~\cite{bcgr11:ip} but,
% as only one bit is modified at each iteration, this generator is not able to pass any reasonable statistical tests.

% The $\textit{XOR~CIPRNG}(S)$, for its part~\cite{DBLP:journals/corr/abs-1112-5239}, is defined as follows: $x^0 \in \mathds{B}^\mathsf{N}$, and $\forall n \in \mathds{N}, x^{n+1} = x^n \oplus S^n$
% where $S \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$ and $\oplus$ stands for the bitwise \emph{exclusive or} (xor) operation
% between the binary decomposition of $x^n$ and $S^n$. This is indeed a $CIPRNG_{f_0}^2 (u,v)$ generator:
% %, for 
% %$u,v \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$: 
% for any given $S \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$, $v^n$ is the number
% of 1's in the binary decomposition of $S^n$ while $u^{v^n}, u^{v^n+1}, \hdots , u^{v^{n+1}-1}$
% are the positions of these ones.
% The $\textit{XOR~CIPRNG}$ has been proven chaotic and it is able to pass all the most stringent statistical 
% batteries of tests~\cite{DBLP:journals/corr/abs-1112-5239}, namely: DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10}, and TestU01~\cite{LEcuyerS07},
% which encompasses the two former ones. Furthermore, the output sequence is cryptographically secure
% when $S$ is cryptographically secure~\cite{DBLP:journals/corr/abs-1112-5239}.
% We are then left to prove $\textit{CIPRNG}_f^2(u,v)$ is chaotic.

% \subsection{The $\textit{CIPRNG}_f^2(u,v)$ is chaotic for well-chosen $f$}\label{sec:wellchosen}

% \subsection{The generator as a discrete dynamical system}


% This algorithm may be seen as $\mathsf{p}$ functional composition of $F_f$.
% We thus introduce the function 
% $F_{f,\mathsf{p}} :  \mathds{B}^\mathsf{N} \times \llbracket 1, \mathsf{N} \rrbracket^\mathsf{p}  \rightarrow \mathds{B}^\mathsf{N}$ defined by 

% $$
% F_{f,\mathsf{p}} (x,(u^0, u^1, \hdots, u^{\mathsf{p}-1}))  \mapsto 
% F_f(\hdots (F_f(F_f(x,u^0), u^1), \hdots), u^{\mathsf{p}-1}).
% $$




Let us first introduce $\mathcal{P} \subset \mathds{N}$ a finite nonempty
set having the cardinality $\mathsf{p} \in \mathds{N}^\ast$.
Intuitively, this  is the set of authorized numbers of iterations.
Denote by $p_1, p_2, \hdots, p_\mathsf{p}$ the ordered elements of $\mathcal{P}$: $\mathcal{P} = \{ p_1, p_2, \hdots, p_\mathsf{p}\}$
and $p_1< p_2< \hdots < p_\mathsf{p}$. In our algorithm, 
$\mathsf{p}$ is 1 and $p_1$ is $b$. 


The Algorithm~\ref{CI Algorithm} 
may be seen as $b$ functional composition of $F_f$.
However, it can be generalized with $p_i$, $p_i \in \mathcal{P}$,
functional compositions of $F_f$.
Thus, for any $p_i \in \mathcal{P}$ we introduce the function 
$F_{f,p_i} :  \mathds{B}^\mathsf{N} \times \llbracket 1, \mathsf{N} \rrbracket^{p_i}  \rightarrow \mathds{B}^\mathsf{N}$ defined by 
\[
\begin{array}{l}
F_{f,p_i} (x,(u^0, u^1, \hdots, u^{p_i-1}))  \mapsto \\
\qquad F_f(\hdots (F_f(F_f(x,u^0), u^1), \hdots), u^{p_i-1}).
\end{array}
\]


The considered space is 
 $\mathcal{X}_{\mathsf{N},\mathcal{P}}=  \mathds{B}^\mathsf{N} \times \mathds{S}_{\mathsf{N},\mathcal{P}}$, where 
$\mathds{S}_{\mathsf{N},\mathcal{P}}=
\llbracket 1, \mathsf{N} \rrbracket^{\Nats}\times 
\mathcal{P}^{\Nats}$. 
Each element in this space is a pair where the first element is 
$\mathsf{N}$-uple in $\Bool^{\mathsf{N}}$, as in the previous space.  
The second element is a pair $((u^k)_{k \in \Nats},(v^k)_{k \in \Nats})$ of infinite sequences.
The sequence $(v^k)_{k \in \Nats}$ defines how many iterations are executed at time $k$ between two outputs. 
The sequence $(u^k)_{k \in \Nats}$ defines which elements is modified. 

Let us define the shift function $\Sigma$ for any element of $\mathds{S}_{\mathsf{N},\mathcal{P}}$.

\[
\begin{array}{cccc}
\Sigma:&\mathds{S}_{\mathsf{N},\mathcal{P}} &\rightarrow
&\mathds{S}_{\mathsf{N},\mathcal{P}} \\
& \left((u^k)_{k \in \mathds{N}},(v^k)_{k \in \mathds{N}}\right) & \mapsto & 
\begin {array}{l}
    \left(\sigma^{v^0}\left((u^k)_{k \in \mathds{N}}\right), \right. \\
     \qquad \left. \sigma\left((v^k)_{k \in \mathds{N}}\right)\right).
 \end{array} 
\end{array}
\]

In other words, $\Sigma$ receives two sequences $u$ and $v$, and
it operates $v^0$ shifts on the first sequence and a single shift
on the second one. 
Let
\begin{equation}
\begin{array}{cccc}
G_f :&  \mathcal{X}_{\mathsf{N},\mathcal{P}} & \rightarrow & \mathcal{X}_{\mathsf{N},\mathcal{P}}\\
   & (e,(u,v)) & \mapsto & \left( F_{f,v^0}\left( e, (u^0, \hdots, u^{v^0-1}\right), \Sigma (u,v) \right) .
\end{array}
\end{equation}
Then the outputs $(y^0, y^1, \hdots )$ produced by the $\textit{CIPRNG}_f^2(u,v)$ generator 
are the first components of the iterations $X^0 = (x^0, (u,v))$ and $\forall n \in \mathds{N}, 
X^{n+1} = G_f(X^n)$ on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$.






\subsection{A metric on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$}

We define a distance $d$ on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ as follows. 
Consider 
$x=(e,s)$ and $\check{x}=(\check{e},\check{s})$ in 
$\mathcal{X}_{\mathsf{N},\mathcal{P}} = \mathds{B}^\mathsf{N} \times \mathds{S}_{\mathsf{N},\mathcal{P}} $,
where $s=(u,v)$ and $\check{s}=(\check{u},\check{v})$ are in $ \mathds{S}_{\mathsf{N},\mathcal{P}} = 
\mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket} \times \mathcal{S}_\mathcal{P}$. 
\begin{itemize}
\item $e$ and $\check{e}$ are integers belonging in $\llbracket 0, 2^{\mathsf{N}-1} \rrbracket$. The Hamming distance
on their binary decomposition, that is, the number of dissimilar binary digits, constitutes the integral
part of $d(X,\check{X})$.
\item The fractional part is constituted by the differences between $v^0$ and $\check{v}^0$, followed by the differences
between finite sequences $u^0, u^1, \hdots, u^{v^0-1}$ and  $\check{u}^0, \check{u}^1, \hdots, \check{u}^{\check{v}^0-1}$, followed by 
 differences between $v^1$ and $\check{v}^1$, followed by the differences
between $u^{v^0}, u^{v^0+1}, \hdots, u^{v^1-1}$ and  $\check{u}^{\check{v}^0}, \check{u}^{\check{v}^0+1}, \hdots, \check{u}^{\check{v}^1-1}$, etc.
More precisely, let $p = \lfloor \log_{10}{(\max{\mathcal{P}})}\rfloor +1$ and $n = \lfloor \log_{10}{(\mathsf{N})}\rfloor +1$.
\begin{itemize}
\item The $p$ first digits of $d(x,\check{x})$ is $|v^0-\check{v}^0|$ written in decimal numeration (and with $p$ digits).
\item The next $n\times \max{(\mathcal{P})}$ digits aim at measuring how much $u^0, u^1, \hdots, u^{v^0-1}$ differs from $\check{u}^0, \check{u}^1, \hdots, \check{u}^{\check{v}^0-1}$. The $n$ first
digits are $|u^0-\check{u}^0|$. They are followed by 
$|u^1-\check{u}^1|$ written with $n$ digits, etc.
\begin{itemize}
\item If
$v^0=\check{v}^0$, then the process is continued until $|u^{v^0-1}-\check{u}^{\check{v}^0-1}|$ and the fractional
part of $d(X,\check{X})$ is completed by 0's until reaching
$p+n\times \max{(\mathcal{P})}$ digits.
\item If $v^0<\check{v}^0$, then the $ \max{(\mathcal{P})}$  blocs of $n$
digits are $|u^0-\check{u}^0|$, ..., $|u^{v^0-1}-\check{u}^{v^0-1}|$,
$\check{u}^{v^0}$ (on $n$ digits), ..., $\check{u}^{\check{v}^0-1}$ (on $n$ digits), followed by 0's if required.
\item The case $v^0>\check{v}^0$ is dealt similarly.
\end{itemize}
\item The next $p$ digits are $|v^1-\check{v}^1|$, etc.
\end{itemize}
\end{itemize}



\newcommand{\ns}{$\hspace{.1em}$}

\begin{xpl}
Consider for instance that $\mathsf{N}=13$, $\mathcal{P}=\{1,2,11\}$ (so $\mathsf{p}=2$), and that
$s=\left\{
\begin{array}{l}
u=\underline{6,} ~ \underline{11,5}, ...\\
v=1,2,...
\end{array}
\right.$
while
$\check{s}=\left\{
\begin{array}{l}
\check{u}=\underline{6,4} ~ \underline{1}, ...\\
\check{v}=2,1,...
\end{array}
\right.$.

So $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.01\ns00\ns04\ns00\ns00\ns00\ns00\ns00\ns00\ns00\ns00\ns00\ns01\ns10\ns05 ...$
Indeed, the $p=2$ first digits are 01, as $|v^0-\check{v}^0|=1$, 
and we use $p$ digits to code this difference ($\mathcal{P}$ being $\{1,2,11\}$, this difference can be equal to 10). We then take the $v^0=1$ first terms of $u$, each term being coded in $n=2$ digits, that is, 06. As we can iterate
at most $\max{(\mathcal{P})}$ times, we must complete this
value by some 0's in such a way that the obtained result
has $n\times \max{(\mathcal{P})}=22$ digits, that is: 
0600000000000000000000. Similarly, the $\check{v}^0=2$ first
terms in $\check{u}$ are represented by 0604000000000000000000, and the absolute value of their
difference is equal to 0004000000000000000000. These digits are concatenated to 01, and
we start again with the remainder of the sequences.
\end{xpl}


\begin{xpl}
Consider now that $\mathsf{N}=9$, and $\mathcal{P}=\{2,7\}$, and that

$s=\left\{
\begin{array}{l}
u=\underline{6,7,} ~ \underline{4,2,} ...\\
v=2,2,...
\end{array}
\right.$
while
$\check{s}=\left\{
\begin{array}{l}
\check{u}=\underline{4, 9, 6, 3, 6, 6, 7,} ~ \underline{9, 8}, ...\\
\check{v}=7,2,...
\end{array}
\right.$

So $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.5173633305600000...$, as $|v^0-\check{v}^0|=5$, $|4963667-6700000| = 1736333$, $|v^1-\check{v}^1|=0$,
and $|9800000-4200000| = 5600000$.
\end{xpl}



$d$ can be more rigorously written as follows:
$$d(x,\check{x})=d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})+d_{\mathds{B}^\mathsf{N}}(e,\check{e}),$$
where: % $p=\max \mathcal{P}$ and:
\begin{itemize}
\item $d_{\mathds{B}^\mathsf{N}}$ is the Hamming distance,
\item $\forall s=(u,v), \check{s}=(\check{u},\check{v}) \in \mathcal{S}_{\mathsf{N},\mathcal{P}}$,\newline 
\[
\begin{array}{l}
 d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = \\
  \quad  \sum_{k=0}^\infty \dfrac{1}{10^{(k+1)p+kn\max{(\mathcal{P})}}} 
   \bigg(|v^k - \check{v}^k|  \\
   \quad\quad + \left| \sum_{l=0}^{v^k-1} 
       \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{(l+1)n}} -
       \sum_{l=0}^{\check{v}^k-1} 
       \dfrac{\check{u}^{\sum_{m=0}^{k-1} \check{v}^m +l}}{ 10^{(l+1)n}} \right| \bigg)
\end{array}
\]
 %\left| \sum_{l=0}^{v^k-1} \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{l}} - \sum_{l=0}^{\check{v}^k-1} \dfrac{\check{u}^{\sum_{m=0}^{k-1} \check{v}^m +l}}{ 10^{l}}\right|\right)}.
\end{itemize}


Let us show that,
\begin{prpstn}
$d$ is a distance on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$.
\end{prpstn}


\begin{proof}
 $d_{\mathds{B}^\mathsf{N}}$ is the Hamming distance. We will prove that 
 $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}$ is a distance
too, thus $d$ will also be a distance, being the sum of two distances.
 \begin{itemize}
\item Obviously, $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})\geqslant 0$, and if $s=\check{s}$, then 
$d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=0$. Conversely, if $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=0$, then 
$\forall k \in \mathds{N}, v^k=\check{v}^k$ due to the 
definition of $d$. Then, as digits between positions $p+1$ and $p+n$ are null and correspond to $|u^0-\check{u}^0|$, we can conclude that $u^0=\check{u}^0$. An extension of this result to the whole first $n \times \max{(\mathcal{P})}$ bloc leads to $u^i=\check{u}^i$, $\forall i \leqslant v^0=\check{v}^0$, and by checking all the $n \times \max{(\mathcal{P})}$ blocs, $u=\check{u}$.
 \item $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}$ is clearly symmetric 
($d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(\check{s},s)$). 
\item The triangle inequality is obtained because the absolute value satisfies it too.
 \end{itemize}
\end{proof}


Before being able to study the topological behavior of the general 
chaotic iterations, we must first establish that:

\begin{prpstn}
 For all $f:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N} $, the function $G_f$ is continuous on 
$\left( \mathcal{X},d\right)$.
\end{prpstn}


\begin{proof}
We will show this result by using the sequential continuity. Consider a
sequence $x^n=(e^n,(u^n,v^n)) \in \mathcal{X}_{\mathsf{N},\mathcal{P}}^\mathds{N}$ such
that $d(x^n,x) \longrightarrow 0$, for some $x=(e,(u,v))\in
\mathcal{X}_{\mathsf{N},\mathcal{P}}$. We will show that
$d\left(G_f(x^n),G_f(x)\right) \longrightarrow 0$.
Remark that $u$ and $v$ are sequences of sequences.

As $d(x^n,x) \longrightarrow 0$, there exists 
$n_0\in\mathds{N}$ such that 
$d(x^n,x) < 10^{-(p+n \max{(\mathcal{P})})}$
(its $p+n \max{(\mathcal{P})}$ first digits are null). 
In particular, $\forall n \geqslant n_0, e^n=e$,
as the Hamming distance between the integral parts of
$x$ and $\check{x}$ is 0. Similarly, due to the nullity 
of the $p+n \max{(\mathcal{P})}$ first digits of 
$d(x^n,x)$, we can conclude that $\forall n \geqslant n_0$,
$(v^n)^0=v^0$, and that $\forall n \geqslant n_0$,
$(u^n)^0=u^0$, $(u^n)^1=u^1$, ..., $(u^n)^{v^0-1}=u^{v^0-1}$.
This implies that:
\begin{itemize}
\item $G_f(x^n)_1=G_f(x)_1$: they have the same
Boolean vector as first coordinate.
\item $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(\Sigma (u^n,v^n); \Sigma(u,v)) = 10^{p+n \max{(\mathcal{P})}} d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u^n,v^n); (u,v))$. As the right part of the equality tends
to 0, we can deduce that it is the case too for the left part of the equality, and so
$G_f(x^n)_2$ is convergent to $G_f(x)_2$.
\end{itemize}
\end{proof}



\subsection{$\Gamma_{\mathcal{P}}(f)$ as an extension of  $\Gamma(f)$}

Let $\mathcal{P}=\{p_1, p_2, \hdots, p_\mathsf{p}\}$.
We define the directed graph $\Gamma_{\mathcal{P}}(f)$ as follows.
\begin{itemize}
\item Its vertices are the $2^\mathsf{N}$ elements of $\mathds{B}^\mathsf{N}$.
\item Each vertex has $\displaystyle{\sum_{i=1}^\mathsf{p} \mathsf{N}^{p_i}}$ arrows, namely all the $p_1, p_2, \hdots, p_\mathsf{p}$ tuples 
  having their elements in $\llbracket 1, \mathsf{N} \rrbracket $.
\item There is an arc labeled $u_0, \hdots, u_{p_i-1}$, $i \in \llbracket 1, \mathsf{p} \rrbracket$ between vertices $x$ and $y$ if and only if 
$y=F_{f,p_i} (x, (u_0, \hdots, u_{p_i-1})) $.
\end{itemize}

It is not hard to see that the graph $\Gamma_{\{1\}}(f)$ is 
$\Gamma(f)$.

\begin{figure}[ht]
  \centering
  \begin{subfigure}[b]{0.45\textwidth}
    \centering
    \includegraphics[scale=0.85]{graphe1.pdf}
    \caption{$\Gamma(f_0)$}
    \label{graphe1}
  \end{subfigure}%
  
~ %add desired spacing between images, e. g. ~, \quad, \qquad, \hfill etc.
  % (or a blank line to force the subfigure onto a new line)
  \begin{subfigure}[b]{0.3\textwidth}
    \centering  
    \includegraphics[scale=0.85]{graphe2.pdf}
    \caption{$\Gamma_{\{2,3\}}(f_0)$}
    \label{graphe2}
  \end{subfigure}
  ~ %add desired spacing between images, e. g. ~, \quad, \qquad, \hfill etc.
  \caption{Iterating $f_0:(x_1,x_2) \mapsto (\overline{x_1}, \overline{x_2})$}
  \label{fig:itg}
\end{figure}


\begin{xpl}
Consider for instance $\mathsf{N}=2$, 
Let $f_0:\mathds{B}^2 \longrightarrow \mathds{B}^2$ be the negation function,
\textit{i.e.}, $f_0(x_1,x_2) = (\overline{x_1}, \overline{x_2})$, and consider
$\mathcal{P}=\{2,3\}$. The graphs of iterations are given in 
\textsc{Figure~\ref{fig:itg}}.
The \textsc{Figure~\ref{graphe1}} shows what happens when 
displaying each iteration result.
On the contrary, the \textsc{Figure~\ref{graphe2}} explicits the behaviors
when always applying either 2 or 3 modifications before generating results. 
Notice that here, orientations of arcs are not necessary 
since the function $f_0$ is equal to its inverse $f_0^{-1}$. 
\end{xpl}

\subsection{Proofs of chaos}

We will show that,
\begin{prpstn}
\label{prop:trans}
 $\Gamma_{\mathcal{P}}(f)$ is strongly connected if and only if $G_f$ is 
topologically transitive on $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$.
\end{prpstn}


\begin{proof}
Suppose that $\Gamma_{\mathcal{P}}(f)$ is strongly connected. 
Let $x=(e,(u,v)),\check{x}=(\check{e},(\check{u},\check{v})) 
\in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ and $\varepsilon >0$.
We will find a point $y$ in the open ball $\mathcal{B}(x,\varepsilon )$ and
$n_0 \in \mathds{N}$ such that $G_f^{n_0}(y)=\check{x}$: this strong transitivity
will imply the transitivity property.
We can suppose that $\varepsilon <1$ without loss of generality. 

Let us denote by $(E,(U,V))$  the elements of $y$. As
$y$ must be in $\mathcal{B}(x,\varepsilon)$ and  $\varepsilon < 1$,
$E$ must be equal to $e$. Let $k=\lfloor \log_{10} (\varepsilon) \rfloor +1$.
$d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))$ must be lower than
$\varepsilon$, so the $k$ first digits of the fractional part of 
$d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))$ are null.
Let $k_1$ the smallest integer such that, if $V^0=v^0$, ...,  $V^{k_1}=v^{k_1}$,
 $U^0=u^0$, ..., $U^{\sum_{l=0}^{k_1}V^l-1} = u^{\sum_{l=0}^{k_1}v^l-1}$.
Then $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))<\varepsilon$.
In other words, any $y$ of the form $(e,((u^0, ..., u^{\sum_{l=0}^{k_1}v^l-1}),
(v^0, ..., v^{k_1}))$ is in $\mathcal{B}(x,\varepsilon)$.

Let $y^0$ such a point and $z=G_f^{k_1}(y^0) = (e',(u',v'))$. $\Gamma_{\mathcal{P}}(f)$
being strongly connected, there is a path between $e'$ and $\check{e}$. Denote
by $a_0, \hdots, a_{k_2}$ the edges visited by this path. We denote by
$V^{k_1}=|a_0|$ (number of terms in the finite sequence $a_1$),
$V^{k_1+1}=|a_1|$, ..., $V^{k_1+k_2}=|a_{k_2}|$, and by 
$U^{k_1}=a_0^0$, $U^{k_1+1}=a_0^1$, ..., $U^{k_1+V_{k_1}-1}=a_0^{V_{k_1}-1}$,
$U^{k_1+V_{k_1}}=a_1^{0}$, $U^{k_1+V_{k_1}+1}=a_1^{1}$,...

Let $y=(e,((u^0, \dots, u^{\sum_{l=0}^{k_1}v^l-1}, a_0^0, \dots, a_0^{|a_0|}, a_1^0, \dots, $ \linebreak 
$a_1^{|a_1|},\dots, a_{k_2}^0, \dots, a_{k_2}^{|a_{k_2}|},$  
 $\check{u}^0, \check{u}^1, \dots),(v^0, \dots, v^{k_1},|a_0|, \dots,$\linebreak
 $|a_{k_2}|,\check{v}^0, \check{v}^1, \dots)))$. So $y\in \mathcal{B}(x,\varepsilon)$
 and $G_{f}^{k_1+k_2}(y)=\check{x}$.
 
 
Conversely, if $\Gamma_{\mathcal{P}}(f)$ is not strongly connected, then there are 
2 vertices $e_1$ and $e_2$ such that there is no path between $e_1$ and $e_2$.
That is, it is impossible to find $(u,v)\in \mathds{S}_{\mathsf{N},\mathcal{P}}$
and $n\in \mathds{N}$ such that $G_f^n(e,(u,v))_1=e_2$. The open ball $\mathcal{B}(e_2, 1/2)$
cannot be reached from any neighborhood of $e_1$, and thus $G_f$ is not transitive.
\end{proof}


We show now that,
\begin{prpstn}
If $\Gamma_{\mathcal{P}}(f)$ is strongly connected, then $G_f$ is 
regular on $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$.
\end{prpstn}

\begin{proof}
Let $x=(e,(u,v)) \in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ and $\varepsilon >0$. 
As in the proofs of Prop.~\ref{prop:trans}, let $k_1 \in \mathds{N}$ such
that 
$$\left\{(e, ((u^0, \dots, u^{v^{k_1-1}},U^0, U^1, \dots),(v^0, \dots, v^{k_1},V^0, V^1, \dots)) \mid \right.$$
$$\left.\forall i,j \in \mathds{N}, U^i \in \llbracket 1, \mathsf{N} \rrbracket, V^j \in \mathcal{P}\right\}
\subset \mathcal{B}(x,\varepsilon),$$
and $y=G_f^{k_1}(e,(u,v))$. $\Gamma_{\mathcal{P}}(f)$ being strongly connected,
there is at least a path from the Boolean state $y_1$ of $y$ and $e$ \ANNOT{Phrase pas claire : "from \dots " mais pas de "to \dots"}.
Denote by $a_0, \hdots, a_{k_2}$ the edges of such a path.
Then the point:\linebreak
$(e,((u^0, \dots, u^{v^{k_1-1}},a_0^0, \dots, a_0^{|a_0|}, a_1^0, \dots, a_1^{|a_1|},\dots, 
 a_{k_2}^0, \dots,$ \linebreak 
$\,a_{k_2}^{|a_{k_2}|},u^0, \dots, u^{v^{k_1-1}},a_0^0, \dots,a_{k_2}^{|a_{k_2}|}\dots),$\linebreak
$(v^0, \dots, v^{k_1}, |a_0|, \dots, |a_{k_2}|,v^0, \dots, v^{k_1}, |a_0|, \dots, |a_{k_2}|,\dots))$
is a periodic point in the neighborhood $\mathcal{B}(x,\varepsilon)$ of $x$.
\end{proof}

$G_f$ being topologically transitive and regular, we can thus conclude that
\begin{thrm}
The function $G_f$ is chaotic on $(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$ if
and only if its iteration graph $\Gamma_{\mathcal{P}}(f)$ is strongly connected.
\end{thrm}

\begin{crllr}
  The pseudorandom number generator $\chi_{\textit{14Secrypt}}$ is not chaotic
  on $(\mathcal{X}_{\mathsf{N},\{b\}},d)$ for the negation function.
\end{crllr}
\begin{proof}
  In this context, $\mathcal{P}$ is the singleton $\{b\}$.
  If $b$ is even, any vertex $e$ of $\Gamma_{\{b\}}(f_0)$ cannot reach 
  its neighborhood and thus $\Gamma_{\{b\}}(f_0)$ is not strongly connected. 
  If $b$ is odd, any vertex $e$ of $\Gamma_{\{b\}}(f_0)$ cannot reach itself 
  and thus $\Gamma_{\{b\}}(f_0)$ is not strongly connected.
\end{proof}

The next section recalls a general scheme to produce
functions and a iteration number $b$
such that $\Gamma_{\{b\}}$ is strongly connected.


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