+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}
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}} \\
-\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
$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.
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}
-\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$,
u=\underline{6,7,} ~ \underline{4,2,} ...\\
v=2,2,...
\end{array}
-\right.$\\
+\right.$
while
$\check{s}=\left\{
\begin{array}{l}
Let us show that,
\begin{proposition}
-$d$ is a distance on $\mathcal{X}$.
+$d$ is a distance on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$.
\end{proposition}
\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
-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}
-
-\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}
+
\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}
-\subsubsection{Proofs of chaos}
+\subsection{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
+ $\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{proposition}
\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
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$),
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)$
We show now that,
\begin{proposition}
-If $\mathcal{G}_{f,\mathcal{P}}$ is strongly connected, then $G_f$ is
+If $\Gamma_{\mathcal{P}}(f)$ is strongly connected, then $G_f$ is
regular on $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$.
\end{proposition}
$$\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:
$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.
+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{Theo}
+
+\begin{Corollary}
+ The pseudorandom number generator $\chi_{\textit{14Secrypt}}$ is not chaotic
+ on $(\mathcal{X}_{\mathsf{N},\{b\}},d)$ for the negation function.
+\end{Corollary}
+\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
