From: Christophe Guyeux <guyeux@gmail.com>
Date: Fri, 20 Feb 2015 15:29:03 +0000 (+0100)
Subject: ajout de la partie chaos
X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/rairo15.git/commitdiff_plain/e878014111cef8e935255d892d3d132429d03469?ds=inline

ajout de la partie chaos
---

diff --git a/chaos.tex b/chaos.tex
new file mode 100644
index 0000000..74d07cf
--- /dev/null
+++ b/chaos.tex
@@ -0,0 +1,461 @@
+
+
+\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}
diff --git a/graphe1.pdf b/graphe1.pdf
new file mode 100644
index 0000000..0e0e765
Binary files /dev/null and b/graphe1.pdf differ
diff --git a/graphe2.pdf b/graphe2.pdf
new file mode 100644
index 0000000..9ea5f8e
Binary files /dev/null and b/graphe2.pdf differ