ajout de fichiers

[16dcc.git] / chaos.tex

\subsection{Motivations}
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 corollary 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 few of them are concerned and 
any subsequence of a chaotic sequence  is   not  necessarily  
a   chaotic  sequence  as well.
This necessitates a rigorous proof, which is the aim of this section.
Let us firstly recall the theoretical framework in which this research takes place.




\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}$~\cite{Devaney}.

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

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

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


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

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

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

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

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


\subsection{A Metric Space for PRNG Iterations}

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

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


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

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

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

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


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

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




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

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


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

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

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

In other words, $\Sigma$ receives two sequences $u$ and $v$, and
it operates $v^0$ shifts on the first sequence and a single shift
on the second one. 
Let us consider
\begin{equation}
\begin{array}{cccc}
G_f :&  \mathcal{X}_{\mathsf{N},\mathcal{P}} & \rightarrow & \mathcal{X}_{\mathsf{N},\mathcal{P}}\\
   & (e,(u,v)) & \mapsto & \left( F_{f,v^0}\left( e, (u^0, \hdots, u^{v^0-1}\right), \Sigma (u,v) \right) .
\end{array}
\end{equation}
Then the outputs $(y^0, y^1, \hdots )$ produced by the $\textit{CIPRNG}_f^2(u,v)$ generator~\cite{wbg10:ip} 
are by definition 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}}$.
The new obtained generator can be shown as either a post-treatment over generators $u$ and $v$, or a
discrete dynamical system on a set constituted by binary vectors and couple of integer sequences.





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

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

This distance has been defined to capture all aspects of divergences between two sequences generated 
by the $\textit{CIPRNG}_f^2$ method, when setting respectively $(u,v)$ and $(\check{u},\check{v})$ as inputted 
couples of generators. The integral part measures the bitwise Hamming distance between 
the two $\mathsf{N}$-length binary vectors chosen as seeds. The fractional part must decrease 
when the number of identical iterations applied by the $\textit{CIPRNG}_f^2$ discrete dynamical system on these seeds, in both cases (that is, when inputting either $(u,v)$ or $(\check{u},\check{v})$), increases.
More precisely, the fractional part will alternately measure the following elements:
\begin{itemize}
  \item Do we iterate the same number of times between the next two outputs, when considering either $(u,v)$ or $(\check{u},\check{v})$?
  \item Then, do we iterate the same components between the next two outputs of $\textit{CIPRNG}_f^2$ ?
  \item etc.
\end{itemize}
Finally, zeros are put to be able to recover what occurred at a given iteration. Such aims are illustrated in the two following examples.
\begin{xpl}
Consider for instance that $\mathsf{N}=13$, $\mathcal{P}=\{1,2,11\}$ (so $\mathsf{p}=3$, $p=\lfloor \log_{10}{(\max{\mathcal{P}})}\rfloor +1 = 2$, while $n=2$), and that
$s=\left\{
\begin{array}{l}
u=\underline{6,} ~ \underline{11,5}, ...\\
v=1,2,...
\end{array}
\right.$
while
$\check{s}=\left\{
\begin{array}{l}
\check{u}=\underline{6,4} ~ \underline{1}, ...\\
\check{v}=2,1,...
\end{array}
\right.$.

So 
$$d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.01~0004000000000000000000~01~1005...$$
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 first $\check{v}^0=2$ 
terms in $\check{u}$ are represented by 0604000000000000000000, and the value of their
digit per digit absolute 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$ ($n=1$), $\mathcal{P}=\{2,7\}$ ($\mathsf{p}=2, p=1$), 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.5~2263667~1~5600000...$. 
%as $|v^0-\check{v}^0|=5$, $|4963667-6700000| = 1736333$, $|v^1-\check{v}^1|=0$,
%and $|9800000-4200000| = 5600000$.
\end{xpl}



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


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


\begin{proof}
 $d_{\mathds{B}^\mathsf{N}}$ is the Hamming distance. We will prove that 
 $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}$ is a distance
too, thus $d$ will also be a distance, being the sum of two distances.
 \begin{itemize}
\item Obviously, $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})\geqslant 0$, and if $s=\check{s}$, then 
$d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=0$. Conversely, if $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=0$, then 
$\forall k \in \mathds{N}, v^k=\check{v}^k$ due to the 
definition of $d$. Then, as digits between positions $p+1$ and $p+n$ are null and correspond to $|u^0-\check{u}^0|$, we can conclude that $u^0=\check{u}^0$. An extension of this result to the whole first $n \times \max{(\mathcal{P})}$ blocs 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 as well.
 \end{itemize}
\end{proof}


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

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


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

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



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

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

It is not hard to see that the graph $\Gamma_{\{1\}}(f)$ is 
$\Gamma(f)$ formerly introduced in~\cite{bcgr11:ip} for the $\textit{CIPRNG}_f^1(u)$ generator,
which is indeed $\textit{CIPRNG}_f^2(u,(1)_{n \in \mathds{N}})$.

\begin{figure}[ht]
  \centering
  \subfigure[$\Gamma(f_0)$]{
      \begin{minipage}{0.45\textwidth}
        \centering
        \includegraphics[scale=0.85]{graphe1.pdf}
      \end{minipage}
    \label{graphe1}
    }
    \subfigure[$\Gamma_{\{2,3\}}(f_0)$]{
      \begin{minipage}{0.3\textwidth}
        \centering
          \includegraphics[scale=0.85]{graphe2.pdf}
      \end{minipage}
    \label{graphe2}
    }
  \caption{Iterating $f_0:(x_1,x_2) \mapsto (\overline{x_1}, \overline{x_2})$}
  \label{fig:itg}
\end{figure}


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

\subsection{Proofs of chaos}

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


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

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

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

Let

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


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

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

$G_f$ being topologically transitive and regular, we can thus conclude that
\begin{thrm}
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, no vertex $e$ of $\Gamma_{\{b\}}(f_0)$ can reach 
  its neighborhood and thus $\Gamma_{\{b\}}(f_0)$ is not strongly connected. 
  If $b$ is odd, no vertex $e$ of $\Gamma_{\{b\}}(f_0)$ can reach itself 
  and thus $\Gamma_{\{b\}}(f_0)$ is not strongly connected.
\end{proof}


\subsection{Comparison with other well-known generators}

\begin{table}
\centering
  \begin{tabular}{c|ccccccc}
  PRNG & LCG & MRG & AWC & SWB & SWC & GFSR & INV\\
  \hline
  NIST & 11 & 14 & 15 & 15 & 14 & 14 & 14\\
  DieHARD & 16 & 16 & 15 & 16 &18 & 16 & 16
  \end{tabular}
  \caption{Statistical evaluation of known PRNGs: number of succeeded tests}
  \label{table:comparisonWithout}
\end{table}

\begin{table}
\centering
  \begin{tabular}{c|ccccccc}
  PRNG & LCG & MRG & AWC & SWB & SWC & GFSR & INV\\
  \hline
  NIST & 15 & 15 & 15 & 15 & 15 & 15 & 15\\
  DieHARD & 18 & 18 & 18 & 18 & 18 & 18 & 18
  \end{tabular}
  \caption{Statistical effects of CIPRNG on the succeeded tests}
  \label{table:comparisonWith}
\end{table}
The objective of this section is to evaluate the statistical performance of the 
proposed CIPRNG method, by comparing the effects of its application on well-known
but defective generators. We considered during the experiments the following PRNGs:
linear congruential generator (LCG), multiple recursive generators (MRG)
add-with-carry (AWC), subtract-with-borrow (SWB), shift-with-carry (SWC)
Generalized Feedback Shift Register (GFSR), and nonlinear inversive generator.
A general overview and a reminder of these  generators 
can be found, for instance, in the documentation of the TestU01 statistical
battery of tests~\cite{LEcuyerS07}. For each studied generator, we have compared
their scores according to both NIST~\cite{Nist10} and DieHARD~\cite{Marsaglia1996}
statistical batteries of tests, by launching them alone or inside the $\textit{CIPRNG}_f^2(v,v)$
dynamical system, where $v$ is the considered PRNG set with most usual parameters,
and $f$ is the vectorial negation. 

Obtained results are reproduced in Tables~\ref{table:comparisonWithout} and \ref{table:comparisonWith}.
As can be seen, all these generators considered alone failed to pass either the 15 NIST tests or the
18 DieHARD ones, while both batteries of tests are always passed when applying the $\textit{CIPRNG}_f^2$
post-treatment. Other results in the same direction, which can be found in~\cite{bfgw11:ip}, illustrate
the fact that operating a provable chaotic post-treatment on defective generators tends to improve
their statistical profile. 

Such post-treatment depending on the properties of the inputted function $f$, we need to recall a general scheme to produce
functions and an iteration number $b$ such that $\Gamma_{\{b\}}$ is strongly connected.


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