reprise de la preuve de PCH

[rairo15.git] / chaos.tex

\subsection{Notations and terminologies}\label{sec:notations}


Denote by $\mathds{B}$ the Boolean set, by $\mathds{N}^\ast$ the set
of natural integers $\{1,2,3, \hdots \}$, and by $\mathds{N}=\mathds{N}^\ast \cup \{0\}$.
For $a,b \in \mathds{N}, a \leqslant b$, $\llbracket a, b \rrbracket$ means the set
$\{a, a+1, \hdots , b\}$ of integers belonging between $a$ and $b$.
For any finite set $X$, $|X|$ denotes its cardinality.
The $n-$th of a sequence $v$ of vectors is $v^n$ while its $i-$th component is $v_i^n$, 
so $v=\left(v^n\right)_{n \in \mathds{N}}$. 
Finally, $\overline{x}$ stands for the negation of the Boolean $x$, while $\lfloor y \rfloor$ is
the largest integer lower than $y$.

\subsubsection{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{Def}
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{Def}

\begin{Def}
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{Def}

\begin{Def}
$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{Def}


\begin{Def}[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{Def}

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

\begin{Def}
\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{Def}

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). 


\subsubsection{Introducing the \textit{CIPRNG} categories of chaotic iterations based pseudorandom number generators}

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}

\subsubsection{The generator as a discrete dynamical system}


Using notations of the previous section, consider a $\textit{CIPRNG}_f^2(u,v)$ generator $G$, with
$\mathsf{N} \in \mathds{N}^\ast$, $f:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N}$,
$u \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$, and $v \in \mathcal{S}_\mathcal{P}$, with
$\mathcal{P} \subset \mathds{N}$ a finite nonempty set having the cardinality 
$\mathsf{p} \in \mathds{N}^\ast$.
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}$.
Let 
$$
\begin{array}{cccc}
 F_f: & \mathds{B}^\mathsf{N} \times \llbracket 1, \mathsf{N} \rrbracket & \longrightarrow & \mathds{B}^\mathsf{N}\\
      & (e,i) & \longmapsto & (e_1, \hdots , e_{i-1}, f(e)_i, e_{i+1}, \hdots , e_{\mathsf{N}}) 
\end{array}
$$
and
$$
\begin{array}{cccc}
 F_{f,\mathsf{p}} : & \mathds{B}^\mathsf{N} \times \llbracket 1, \mathsf{N} \rrbracket^\mathsf{p} & \longrightarrow & \mathds{B}^\mathsf{N}\\
      & (e,(u^0, u^1, \hdots, u^{\mathsf{p}-1})) & \longmapsto & F_f(\hdots (F_f(F_f(e,u^0), u^1), \hdots), u^{\mathsf{p}-1}) .
\end{array}
$$

Denote by $\mathcal{X}_{\mathsf{N},\mathcal{P}}=  \mathds{B}^\mathsf{N} \times \mathds{S}_{\mathsf{N},\mathcal{P}}$, where 
$\mathds{S}_{\mathsf{N},\mathcal{P}}=\mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}\times \mathcal{S}_\mathcal{P}$, 
we define the shift operation on sequences as follows,
$$\begin{array}{cccc}
\sigma:&\mathcal{S}_{X} &\longrightarrow
& \mathcal{S}_{X} \\
& (u^k)_{k \in \mathds{N}} & \longmapsto & (u^{k+1})_{k \in \mathds{N}}, 
\end{array}
$$
and let
$$\begin{array}{cccc}
\Sigma:&\mathds{S}_{\mathsf{N},\mathcal{P}} &\longrightarrow
&\mathds{S}_{\mathsf{N},\mathcal{P}} \\
& \left((u^k)_{k \in \mathds{N}},(v^k)_{k \in \mathds{N}}\right) & \longmapsto & \left(\sigma^{v^0}\left((u^k)_{k \in \mathds{N}}\right),\sigma\left((v^k)_{k \in \mathds{N}}\right)\right). 
\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}} & \longrightarrow & \mathcal{X}_{\mathsf{N},\mathcal{P}}\\
   & (e,(u,v)) & \longmapsto & \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}}$.






\subsubsection{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 O'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}




\begin{xpl}
Consider for instance that $\mathsf{N}=13$, $\mathcal{P}=\{1,2,11\}$ (so $\mathsf{p}=3$), 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.010004000000000000000000011005 ...$
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}{rcl}
 d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) &= &
   \sum_{k=0}^\infty \dfrac{1}{10^{(k+1)p+kn\max{(\mathcal{P})}}} 
   \bigg(|v^k - \check{v}^k|  \\
   & & + \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{proposition}
$d$ is a distance on $\mathcal{X}$.
\end{proposition}


\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{proposition}
 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{proposition}


\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}

\begin{figure}[h]
\centering
\includegraphics[scale=0.85]{graphe1.pdf}
\caption{Chaotic iterations of $f_0$, defining the $CIPRNG_{f_0}^1$ ($\mathsf{N}=2$)}
\label{graphe1}
\end{figure}

\subsubsection{The $\textit{CIPRNG}_f^2(u,v)$ as iterations on a graph}

We define the directed graph $\mathcal{G}_{f,\mathcal{P}}$ 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 $a_1, \hdots, a_{p_i}$, $i \in \llbracket 1, \mathsf{p} \rrbracket$ between vertices $x$ and $y$ if and only if $y=F_{f,p_i} (x, (a_1, \hdots, a_{p_i})) $.
\end{itemize}


\begin{figure}[h]
\centering
\includegraphics[scale=0.85]{graphe2.pdf}
\caption{Iteration graph of $CIPRNG_{f_0}^2$, $\mathcal{P}=\{2,3\}$, $\mathsf{N}=2$}
\label{graphe2}
\end{figure}

\begin{xpl}
Consider for instance $\mathsf{N}=2$, $f_0:\mathds{B}^2 \longrightarrow \mathds{B}^2, (x_1,x_2) \longmapsto (\overline{x_1}, \overline{x_2})$, and
$\mathcal{P}=\{2,3\}$. Chaotic iterations of $f_0$ are given in Figure~\ref{graphe1} while the digraph  $\mathcal{G}_{f_0,\{2,3\}}$ is depicted in
Figure~\ref{graphe2}. Notice that here, orientations of arcs are not necessary 
since the function $f$ is equal to its inverse $f^{-1}$. 
\end{xpl}

\subsubsection{Proofs of chaos}

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


\begin{proof}
Suppose that $\mathcal{G}_{f,\mathcal{P}}$ 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'))$. $\mathcal{G}_{f,\mathcal{P}}$
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, ..., u^{\sum_{l=0}^{k_1}v^l-1}, a_0^0, ..., a_0^{|a_0|}, a_1^0, ..., a_1^{|a_1|},..., 
 a_{k_2}^0, ..., a_{k_2}^{|a_{k_2}|},$ \linebreak
 $\check{u}^0, \check{u}^1, ...),(v^0, ..., v^{k_1},|a_0|, ...,
 |a_{k_2}|,\check{v}^0, \check{v}^1, ...)))$. So $y\in \mathcal{B}(x,\varepsilon)$
 and $G_{f}^{k_1+k_2}(y)=\check{x}$.
 
 
Conversely, if $\mathcal{G}_{f,\mathcal{P}}$ 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 \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{proposition}
If $\mathcal{G}_{f,\mathcal{P}}$ is strongly connected, then $G_f$ is 
regular on $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$.
\end{proposition}

\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, ..., u^{v^{k_1-1}},U^0, U^1, ...),(v^0, ..., v^{k_1},V^0, V^1, ...)) \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))$. $\mathcal{G}_{f,\mathcal{P}}$ being strongly connected,
there is at least a path from the Boolean state $y_1$ of $y$ and $e$.
Denote by $a_0, \hdots, a_{k_2}$ the edges of such a path.
Then the point:
$$(e,((u^0, ..., u^{v^{k_1-1}},a_0^0, ..., a_0^{|a_0|}, a_1^0, ..., a_1^{|a_1|},..., 
 a_{k_2}^0, ..., a_{k_2}^{|a_{k_2}|},u^0, ..., u^{v^{k_1-1}},$$
$$a_0^0, ...,a_{k_2}^{|a_{k_2}|}...),(v^0, ..., v^{k_1}, |a_0|, ..., |a_{k_2}|,v^0, ..., v^{k_1}, |a_0|, ..., |a_{k_2}|,...))$$
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{Theo}
The pseudorandom number generator $\textit{CIPRNG}_f^2$ denoted by $G_f$ in
this section is chaotic on $(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$ if
and only if its graph $\mathcal{G}_{f,\mathcal{P}}$ is strongly connected.
\end{Theo}