modifs pour le style ita

[rairo15.git] / chaos.tex

diff --git a/chaos.tex b/chaos.tex
index 74d07cf30515e46e915f9256785bc849c05dd706..d5ab5f94edc376ad4b7a09529fb1dd0d6d7f5511 100644 (file)
--- a/chaos.tex
+++ b/chaos.tex
@@ -1,60 +1,80 @@
+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{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}
+\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}$.
 
 \label{subsec:Devaney}
 
 
 Consider a topological space $(\mathcal{X},\tau)$ and a continuous function $f :
 \mathcal{X} \rightarrow \mathcal{X}$.
 

-\begin{Def}
+\begin{dfntn}

 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$.
 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}
+\end{dfntn}

 
 

-\begin{Def}
+\begin{dfntn}

 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).$
 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}
+\end{dfntn}

 
 

-\begin{Def}
+\begin{dfntn}

 $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).
 $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}
+\end{dfntn}

 
 
 
 

-\begin{Def}[Devaney's formulation of chaos~\cite{Devaney}]
+\begin{dfntn}[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.
 The function $f$ is said to be \emph{chaotic} on $(\mathcal{X},\tau)$ if $f$ is regular and
 topologically transitive.

-\end{Def}
+\end{dfntn}

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

-\begin{Def}
+\begin{dfntn}

 \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$.
 \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}
+\end{dfntn}

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


@@ -62,93 +82,106 @@ sensitive dependence on initial conditions (this property was formerly an
 element of the definition of chaos). 
 
 
 element of the definition of chaos). 
 
 

-\subsubsection{Introducing the \textit{CIPRNG} categories of chaotic iterations based pseudorandom number generators}
+\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$. 

 
 

-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
+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}{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}
+F_{f,p_i} (x,(u^0, u^1, \hdots, u^{p_i-1}))  \mapsto 
+F_f(\hdots (F_f(F_f(x,u^0), u^1), \hdots), u^{p_i-1}).

 $$
 
 $$
 

-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
+
+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}} &\longrightarrow
 &\mathds{S}_{\mathsf{N},\mathcal{P}} \\
 $$\begin{array}{cccc}
 \Sigma:&\mathds{S}_{\mathsf{N},\mathcal{P}} &\longrightarrow
 &\mathds{S}_{\mathsf{N},\mathcal{P}} \\


@@ -174,7 +207,7 @@ X^{n+1} = G_f(X^n)$ on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$.
 
 
 
 
 
 

-\subsubsection{A metric 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 
 
 We define a distance $d$ on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ as follows. 
 Consider 


@@ -203,7 +236,7 @@ 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}|$,
 $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.
+$\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.
 \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.


@@ -220,14 +253,14 @@ $s=\left\{
 u=\underline{6,} ~ \underline{11,5}, ...\\
 v=1,2,...
 \end{array}
 u=\underline{6,} ~ \underline{11,5}, ...\\
 v=1,2,...
 \end{array}

-\right.$\\
+\right.$

 while
 $\check{s}=\left\{
 \begin{array}{l}
 \check{u}=\underline{6,4} ~ \underline{1}, ...\\
 \check{v}=2,1,...
 \end{array}
 while
 $\check{s}=\left\{
 \begin{array}{l}
 \check{u}=\underline{6,4} ~ \underline{1}, ...\\
 \check{v}=2,1,...
 \end{array}

-\right.$
+\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$, 
 
 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$, 


@@ -250,7 +283,7 @@ $s=\left\{
 u=\underline{6,7,} ~ \underline{4,2,} ...\\
 v=2,2,...
 \end{array}
 u=\underline{6,7,} ~ \underline{4,2,} ...\\
 v=2,2,...
 \end{array}

-\right.$\\
+\right.$

 while
 $\check{s}=\left\{
 \begin{array}{l}
 while
 $\check{s}=\left\{
 \begin{array}{l}


@@ -285,9 +318,9 @@ $$ %\left| \sum_{l=0}^{v^k-1} \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{l}} - \su
 
 
 Let us show that,
 
 
 Let us show that,

-\begin{proposition}
-$d$ is a distance on $\mathcal{X}$.
-\end{proposition}
+\begin{prpstn}
+$d$ is a distance on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$.
+\end{prpstn}

 
 
 \begin{proof}
 
 
 \begin{proof}


@@ -309,10 +342,10 @@ definition of $d$. Then, as digits between positions $p+1$ and $p+n$ are null an
 Before being able to study the topological behavior of the general 
 chaotic iterations, we must first establish that:
 
 Before being able to study the topological behavior of the general 
 chaotic iterations, we must first establish that:
 

-\begin{proposition}
+\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)$.
  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}
+\end{prpstn}

 
 
 \begin{proof}
 
 
 \begin{proof}


@@ -344,50 +377,71 @@ $G_f(x^n)_2$ is convergent to $G_f(x)_2$.
 \end{itemize}
 \end{proof}
 
 \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.
+\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 
 \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})) $.
+  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}
 
 \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}
+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}
 
 \end{figure}
 

+

 \begin{xpl}
 \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}$. 
+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 2 or 3 modification and next outputing 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}
 
 \end{xpl}
 

-\subsubsection{Proofs of chaos}
+\subsection{Proofs of chaos}

 
 We will show that,
 
 We will show that,

-\begin{proposition}
+\begin{prpstn}

 \label{prop:trans}
 \label{prop:trans}

- $\mathcal{G}_{f,\mathcal{P}}$ is strongly connected if and only if $G_f$ is 
+ $\Gamma_{\mathcal{P}}(f)$ is strongly connected if and only if $G_f$ is 

 topologically transitive on $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$.
 topologically transitive on $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$.

-\end{proposition}
+\end{prpstn}

 
 
 \begin{proof}
 
 
 \begin{proof}

-Suppose that $\mathcal{G}_{f,\mathcal{P}}$ is strongly connected. 
+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
 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


@@ -407,7 +461,7 @@ 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)$.
 
 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}}$
+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$),
 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$),


@@ -422,7 +476,7 @@ Let $y=(e,((u^0, ..., u^{\sum_{l=0}^{k_1}v^l-1}, a_0^0, ..., a_0^{|a_0|}, a_1^0,
  and $G_{f}^{k_1+k_2}(y)=\check{x}$.
  
  
  and $G_{f}^{k_1+k_2}(y)=\check{x}$.
  
  

-Conversely, if $\mathcal{G}_{f,\mathcal{P}}$ is not strongly connected, then there are 
+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 \mathds{N}$ such that $G_f^n(e,(u,v))_1=e_2$. The open ball $\mathcal{B}(e_2, 1/2)$
 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)$


@@ -431,10 +485,10 @@ cannot be reached from any neighborhood of $e_1$, and thus $G_f$ is not transiti
 
 
 We show now that,
 
 
 We show now that,

-\begin{proposition}
-If $\mathcal{G}_{f,\mathcal{P}}$ is strongly connected, then $G_f$ is 
+\begin{prpstn}
+If $\Gamma_{\mathcal{P}}(f)$ is strongly connected, then $G_f$ is 

 regular on $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$.
 regular on $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$.

-\end{proposition}
+\end{prpstn}

 
 \begin{proof}
 Let $x=(e,(u,v)) \in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ and $\varepsilon >0$. 
 
 \begin{proof}
 Let $x=(e,(u,v)) \in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ and $\varepsilon >0$. 


@@ -443,7 +497,7 @@ 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),$$
 $$\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,
+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$.
 Denote by $a_0, \hdots, a_{k_2}$ the edges of such a path.
 Then the point:
 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:


@@ -454,8 +508,25 @@ 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
 \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}
+\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 even, 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 shows how to generate functions and a iteration number $b$
+such that $\Gamma_{\{b\}}$ is strongly connected.
+
+
+ 
\ No newline at end of file