-\begin{lemma}[Strong transitivity]
-\label{strongTrans}
- For all couples $X,Y \in \mathcal{X}$ and any neighborhood $V$ of $X$, we can
-find $n \in \mathds{N}^*$ and $X' \in V$ such that $G^n(X')=Y$.
-\end{lemma}
-
-\begin{proof}
- Let $X=(S,E)$, $\varepsilon>0$, and $k_0 = \lfloor log_{10}(\varepsilon)+1 \rfloor$.
-Any point $X'=(S',E')$ such that $E'=E$ and $\forall k \leqslant k_0, S'^k=S^k$,
-are in the open ball $\mathcal{B}\left(X,\varepsilon\right)$. Let us define
-$\check{X} = \left(\check{S},\check{E}\right)$, where $\check{X}= G^{k_0}(X)$.
-We denote by $s\subset \llbracket 1; \mathsf{N} \rrbracket$ the set of coordinates
-that are different between $\check{E}$ and the state of $Y$. Thus each point $X'$ of
-the form $(S',E')$ where $E'=E$ and $S'$ starts with
-$(S^0, S^1, \hdots, S^{k_0},s,\hdots)$, verifies the following properties:
-\begin{itemize}
- \item $X'$ is in $\mathcal{B}\left(X,\varepsilon\right)$,
- \item the state of $G_f^{k_0+1}(X')$ is the state of $Y$.
-\end{itemize}
-Finally the point $\left(\left(S^0, S^1, \hdots, S^{k_0},s,s^0, s^1, \hdots\right); E\right)$,
-where $(s^0,s^1, \hdots)$ is the strategy of $Y$, satisfies the properties
-claimed in the lemma.
-\end{proof}
-
-We can now prove the Theorem~\ref{t:chaos des general}.
-
-\begin{proof}[Theorem~\ref{t:chaos des general}]
-Firstly, strong transitivity implies transitivity.
-
-Let $(S,E) \in\mathcal{X}$ and $\varepsilon >0$. To
-prove that $G_f$ is regular, it is sufficient to prove that
-there exists a strategy $\tilde S$ such that the distance between
-$(\tilde S,E)$ and $(S,E)$ is less than $\varepsilon$, and such that
-$(\tilde S,E)$ is a periodic point.
-
-Let $t_1=\lfloor-\log_{10}(\varepsilon)\rfloor$, and let $E'$ be the
-configuration that we obtain from $(S,E)$ after $t_1$ iterations of
-$G_f$. As $G_f$ is strongly transitive, there exists a strategy $S'$
-and $t_2\in\mathds{N}$ such
-that $E$ is reached from $(S',E')$ after $t_2$ iterations of $G_f$.
-
-Consider the strategy $\tilde S$ that alternates the first $t_1$ terms
-of $S$ and the first $t_2$ terms of $S'$:
-%%RAPH : j'ai coupé la ligne en 2
-$$\tilde
-S=(S_0,\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,$$$$\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,\dots).$$ It
-is clear that $(\tilde S,E)$ is obtained from $(\tilde S,E)$ after
-$t_1+t_2$ iterations of $G_f$. So $(\tilde S,E)$ is a periodic
-point. Since $\tilde S_t=S_t$ for $t<t_1$, by the choice of $t_1$, we
-have $d((S,E),(\tilde S,E))<\epsilon$.
-\end{proof}
-
-
-\begin{color}{red}
-\section{Statistical Improvements Using Chaotic Iterations}
+%% To study the Devaney's chaos property, a distance between two points
+%% $X = (S,E), Y = (\check{S},\check{E})$ of $\mathcal{X}$ must be defined.
+%% Let us introduce:
+%% \begin{equation}
+%% d(X,Y)=d_{e}(E,\check{E})+d_{s}(S,\check{S}),
+%% \label{nouveau d}
+%% \end{equation}
+%% \noindent where $ \displaystyle{d_{e}(E,\check{E})} = \displaystyle{\sum_{k=1}^{\mathsf{N}%
+%% }\delta (E_{k},\check{E}_{k})}$ is once more the Hamming distance, and
+%% $ \displaystyle{d_{s}(S,\check{S})} = \displaystyle{\dfrac{9}{\mathsf{N}}%
+%% \sum_{k=1}^{\infty }\dfrac{|S^k\Delta {S}^k|}{10^{k}}}$,
+%% %%RAPH : ici, j'ai supprimé tous les sauts à la ligne
+%% %% \begin{equation}
+%% %% \left\{
+%% %% \begin{array}{lll}
+%% %% \displaystyle{d_{e}(E,\check{E})} & = & \displaystyle{\sum_{k=1}^{\mathsf{N}%
+%% %% }\delta (E_{k},\check{E}_{k})} \textrm{ is once more the Hamming distance}, \\
+%% %% \displaystyle{d_{s}(S,\check{S})} & = & \displaystyle{\dfrac{9}{\mathsf{N}}%
+%% %% \sum_{k=1}^{\infty }\dfrac{|S^k\Delta {S}^k|}{10^{k}}}.%
+%% %% \end{array}%
+%% %% \right.
+%% %% \end{equation}
+%% where $|X|$ is the cardinality of a set $X$ and $A\Delta B$ is for the symmetric difference, defined for sets A, B as
+%% $A\,\Delta\,B = (A \setminus B) \cup (B \setminus A)$.
+
+
+%% \begin{proposition}
+%% The function $d$ defined in Eq.~\ref{nouveau d} is a metric on $\mathcal{X}$.
+%% \end{proposition}
+
+%% \begin{proof}
+%% $d_e$ is the Hamming distance. We will prove that $d_s$ is a distance
+%% too, thus $d$, as being the sum of two distances, will also be a distance.
+%% \begin{itemize}
+%% \item Obviously, $d_s(S,\check{S})\geqslant 0$, and if $S=\check{S}$, then
+%% $d_s(S,\check{S})=0$. Conversely, if $d_s(S,\check{S})=0$, then
+%% $\forall k \in \mathds{N}, |S^k\Delta {S}^k|=0$, and so $\forall k, S^k=\check{S}^k$.
+%% \item $d_s$ is symmetric
+%% ($d_s(S,\check{S})=d_s(\check{S},S)$) due to the commutative property
+%% of the symmetric difference.
+%% \item Finally, $|S \Delta S''| = |(S \Delta \varnothing) \Delta S''|= |S \Delta (S'\Delta S') \Delta S''|= |(S \Delta S') \Delta (S' \Delta S'')|\leqslant |S \Delta S'| + |S' \Delta S''|$,
+%% and so for all subsets $S,S',$ and $S''$ of $\llbracket 1, \mathsf{N} \rrbracket$,
+%% we have $d_s(S,S'') \leqslant d_e(S,S')+d_s(S',S'')$, and the triangle
+%% inequality is obtained.
+%% \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 use the sequential continuity.
+%% Let $(S^n,E^n)_{n\in \mathds{N}}$ be a sequence of the phase space $%
+%% \mathcal{X}$, which converges to $(S,E)$. We will prove that $\left(
+%% G_{f}(S^n,E^n)\right) _{n\in \mathds{N}}$ converges to $\left(
+%% G_{f}(S,E)\right) $. Let us remark that for all $n$, $S^n$ is a strategy,
+%% thus, we consider a sequence of strategies (\emph{i.e.}, a sequence of
+%% sequences).\newline
+%% As $d((S^n,E^n);(S,E))$ converges to 0, each distance $d_{e}(E^n,E)$ and $d_{s}(S^n,S)$ converges
+%% to 0. But $d_{e}(E^n,E)$ is an integer, so $\exists n_{0}\in \mathds{N},$ $%
+%% d_{e}(E^n,E)=0$ for any $n\geqslant n_{0}$.\newline
+%% In other words, there exists a threshold $n_{0}\in \mathds{N}$ after which no
+%% cell will change its state:
+%% $\exists n_{0}\in \mathds{N},n\geqslant n_{0}\Rightarrow E^n = E.$
+
+%% In addition, $d_{s}(S^n,S)\longrightarrow 0,$ so $\exists n_{1}\in %
+%% \mathds{N},d_{s}(S^n,S)<10^{-1}$ for all indexes greater than or equal to $%
+%% n_{1}$. This means that for $n\geqslant n_{1}$, all the $S^n$ have the same
+%% first term, which is $S^0$: $\forall n\geqslant n_{1},S_0^n=S_0.$
+
+%% Thus, after the $max(n_{0},n_{1})^{th}$ term, states of $E^n$ and $E$ are
+%% identical and strategies $S^n$ and $S$ start with the same first term.\newline
+%% Consequently, states of $G_{f}(S^n,E^n)$ and $G_{f}(S,E)$ are equal,
+%% so, after the $max(n_0, n_1)^{th}$ term, the distance $d$ between these two points is strictly less than 1.\newline
+%% \noindent We now prove that the distance between $\left(
+%% G_{f}(S^n,E^n)\right) $ and $\left( G_{f}(S,E)\right) $ is convergent to
+%% 0. Let $\varepsilon >0$. \medskip
+%% \begin{itemize}
+%% \item If $\varepsilon \geqslant 1$, we see that the distance
+%% between $\left( G_{f}(S^n,E^n)\right) $ and $\left( G_{f}(S,E)\right) $ is
+%% strictly less than 1 after the $max(n_{0},n_{1})^{th}$ term (same state).
+%% \medskip
+%% \item If $\varepsilon <1$, then $\exists k\in \mathds{N},10^{-k}\geqslant
+%% \varepsilon > 10^{-(k+1)}$. But $d_{s}(S^n,S)$ converges to 0, so
+%% \begin{equation*}
+%% \exists n_{2}\in \mathds{N},\forall n\geqslant
+%% n_{2},d_{s}(S^n,S)<10^{-(k+2)},
+%% \end{equation*}%
+%% thus after $n_{2}$, the $k+2$ first terms of $S^n$ and $S$ are equal.
+%% \end{itemize}
+%% \noindent As a consequence, the $k+1$ first entries of the strategies of $%
+%% G_{f}(S^n,E^n)$ and $G_{f}(S,E)$ are the same ($G_{f}$ is a shift of strategies) and due to the definition of $d_{s}$, the floating part of
+%% the distance between $(S^n,E^n)$ and $(S,E)$ is strictly less than $%
+%% 10^{-(k+1)}\leqslant \varepsilon $.
+
+%% In conclusion,
+%% %%RAPH : ici j'ai rajouté une ligne
+%% %%TOF : ici j'ai rajouté un commentaire
+%% %%TOF : ici aussi
+%% $
+%% \forall \varepsilon >0,$ $\exists N_{0}=max(n_{0},n_{1},n_{2})\in \mathds{N}
+%% ,$ $\forall n\geqslant N_{0},$
+%% $ d\left( G_{f}(S^n,E^n);G_{f}(S,E)\right)
+%% \leqslant \varepsilon .
+%% $
+%% $G_{f}$ is consequently continuous.
+%% \end{proof}
+
+
+%% It is now possible to study the topological behavior of the general chaotic
+%% iterations. We will prove that,
+
+%% \begin{theorem}
+%% \label{t:chaos des general}
+%% The general chaotic iterations defined on Equation~\ref{general CIs} satisfy
+%% the Devaney's property of chaos.
+%% \end{theorem}
+
+%% Let us firstly prove the following lemma.
+
+%% \begin{lemma}[Strong transitivity]
+%% \label{strongTrans}
+%% For all couples $X,Y \in \mathcal{X}$ and any neighborhood $V$ of $X$, we can
+%% find $n \in \mathds{N}^*$ and $X' \in V$ such that $G^n(X')=Y$.
+%% \end{lemma}
+
+%% \begin{proof}
+%% Let $X=(S,E)$, $\varepsilon>0$, and $k_0 = \lfloor log_{10}(\varepsilon)+1 \rfloor$.
+%% Any point $X'=(S',E')$ such that $E'=E$ and $\forall k \leqslant k_0, S'^k=S^k$,
+%% are in the open ball $\mathcal{B}\left(X,\varepsilon\right)$. Let us define
+%% $\check{X} = \left(\check{S},\check{E}\right)$, where $\check{X}= G^{k_0}(X)$.
+%% We denote by $s\subset \llbracket 1; \mathsf{N} \rrbracket$ the set of coordinates
+%% that are different between $\check{E}$ and the state of $Y$. Thus each point $X'$ of
+%% the form $(S',E')$ where $E'=E$ and $S'$ starts with
+%% $(S^0, S^1, \hdots, S^{k_0},s,\hdots)$, verifies the following properties:
+%% \begin{itemize}
+%% \item $X'$ is in $\mathcal{B}\left(X,\varepsilon\right)$,
+%% \item the state of $G_f^{k_0+1}(X')$ is the state of $Y$.
+%% \end{itemize}
+%% Finally the point $\left(\left(S^0, S^1, \hdots, S^{k_0},s,s^0, s^1, \hdots\right); E\right)$,
+%% where $(s^0,s^1, \hdots)$ is the strategy of $Y$, satisfies the properties
+%% claimed in the lemma.
+%% \end{proof}
+
+%% We can now prove the Theorem~\ref{t:chaos des general}.
+
+%% \begin{proof}[Theorem~\ref{t:chaos des general}]
+%% Firstly, strong transitivity implies transitivity.
+
+%% Let $(S,E) \in\mathcal{X}$ and $\varepsilon >0$. To
+%% prove that $G_f$ is regular, it is sufficient to prove that
+%% there exists a strategy $\tilde S$ such that the distance between
+%% $(\tilde S,E)$ and $(S,E)$ is less than $\varepsilon$, and such that
+%% $(\tilde S,E)$ is a periodic point.
+
+%% Let $t_1=\lfloor-\log_{10}(\varepsilon)\rfloor$, and let $E'$ be the
+%% configuration that we obtain from $(S,E)$ after $t_1$ iterations of
+%% $G_f$. As $G_f$ is strongly transitive, there exists a strategy $S'$
+%% and $t_2\in\mathds{N}$ such
+%% that $E$ is reached from $(S',E')$ after $t_2$ iterations of $G_f$.
+
+%% Consider the strategy $\tilde S$ that alternates the first $t_1$ terms
+%% of $S$ and the first $t_2$ terms of $S'$:
+%% %%RAPH : j'ai coupé la ligne en 2
+%% $$\tilde
+%% S=(S_0,\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,$$$$\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,\dots).$$ It
+%% is clear that $(\tilde S,E)$ is obtained from $(\tilde S,E)$ after
+%% $t_1+t_2$ iterations of $G_f$. So $(\tilde S,E)$ is a periodic
+%% point. Since $\tilde S_t=S_t$ for $t<t_1$, by the choice of $t_1$, we
+%% have $d((S,E),(\tilde S,E))<\epsilon$.
+%% \end{proof}
+
+
+
+
+%%RAF : mis en supplementary
+
+
+%\section{Statistical Improvements Using Chaotic Iterations}
+%\label{The generation of pseudorandom sequence}
+%The content is this section is given in Section~\ref{A-The generation of pseudorandom sequence} of the annex document.
+The reasons to desire chaos to achieve randomness are given in Annex~\ref{A-The generation of pseudorandom sequence}.
+
+%% \label{The generation of pseudorandom sequence}
+
+
+%% Let us now explain why we have reasonable ground to believe that chaos
+%% can improve statistical properties.
+%% We will show in this section that chaotic properties as defined in the
+%% mathematical theory of chaos are related to some statistical tests that can be found
+%% in the NIST battery. Furthermore, we will check that, when mixing defective PRNGs with
+%% chaotic iterations, the new generator presents better statistical properties
+%% (this section summarizes and extends the work of~\cite{bfg12a:ip}).
+
+
+
+%% \subsection{Qualitative relations between topological properties and statistical tests}
+
+
+%% There are various relations between topological properties that describe an unpredictable behavior for a discrete
+%% dynamical system on the one
+%% hand, and statistical tests to check the randomness of a numerical sequence
+%% on the other hand. These two mathematical disciplines follow a similar
+%% objective in case of a recurrent sequence (to characterize an intrinsically complicated behavior for a
+%% recurrent sequence), with two different but complementary approaches.
+%% It is true that the following illustrative links give only qualitative arguments,
+%% and proofs should be provided later to make such arguments irrefutable. However
+%% they give a first understanding of the reason why we think that chaotic properties should tend
+%% to improve the statistical quality of PRNGs.
+%% %
+%% Let us now list some of these relations between topological properties defined in the mathematical
+%% theory of chaos and tests embedded into the NIST battery. %Such relations need to be further
+%% %investigated, but they presently give a first illustration of a trend to search similar properties in the
+%% %two following fields: mathematical chaos and statistics.
+
+
+%% \begin{itemize}
+%% \item \textbf{Regularity}. As stated in Section~\ref{subsec:Devaney}, a chaotic dynamical system must
+%% have an element of regularity. Depending on the chosen definition of chaos, this element can be the existence of
+%% a dense orbit, the density of periodic points, etc. The key idea is that a dynamical system with no periodicity
+%% is not as chaotic as a system having periodic orbits: in the first situation, we can predict something and gain a
+%% knowledge about the behavior of the system, that is, it never enters into a loop. A similar importance for periodicity is emphasized in
+%% the two following NIST tests~\cite{Nist10}:
+%% \begin{itemize}
+%% \item \textbf{Non-overlapping Template Matching Test}. Detect generators that produce too many occurrences of a given non-periodic (aperiodic) pattern.
+%% \item \textbf{Discrete Fourier Transform (Spectral) Test}. Detect periodic features (i.e., repetitive patterns that are close one to another) in the tested sequence that would indicate a deviation from the assumption of randomness.
+%% \end{itemize}
+
+%% \item \textbf{Transitivity}. This topological property previously introduced states that the dynamical system is intrinsically complicated: it cannot be simplified into
+%% two subsystems that do not interact, as we can find in any neighborhood of any point another point whose orbit visits the whole phase space.
+%% This focus on the places visited by the orbits of the dynamical system takes various nonequivalent formulations in the mathematical theory
+%% of chaos, namely: transitivity, strong transitivity, total transitivity, topological mixing, and so on~\cite{bg10:ij}. A similar attention
+%% is brought on the states visited during a random walk in the two tests below~\cite{Nist10}:
+%% \begin{itemize}
+%% \item \textbf{Random Excursions Variant Test}. Detect deviations from the expected number of visits to various states in the random walk.
+%% \item \textbf{Random Excursions Test}. Determine if the number of visits to a particular state within a cycle deviates from what one would expect for a random sequence.
+%% \end{itemize}
+
+%% \item \textbf{Chaos according to Li and Yorke}. Two points of the phase space $(x,y)$ define a couple of Li-Yorke when $\limsup_{n \rightarrow +\infty} d(f^{(n)}(x), f^{(n)}(y))>0$ et $\liminf_{n \rightarrow +\infty} d(f^{(n)}(x), f^{(n)}(y))=0$, meaning that their orbits always oscillate as the iterations pass. When a system is compact and contains an uncountable set of such points, it is claimed as chaotic according
+%% to Li-Yorke~\cite{Li75,Ruette2001}. A similar property is regarded in the following NIST test~\cite{Nist10}.
+%% \begin{itemize}
+%% \item \textbf{Runs Test}. To determine whether the number of runs of ones and zeros of various lengths is as expected for a random sequence. In particular, this test determines whether the oscillation between such zeros and ones is too fast or too slow.
+%% \end{itemize}
+%% \item \textbf{Topological entropy}. The desire to formulate an equivalency of the thermodynamics entropy
+%% has emerged both in the topological and statistical fields. Once again, a similar objective has led to two different
+%% rewritting of an entropy based disorder: the famous Shannon definition of entropy is approximated in the statistical approach,
+%% whereas topological entropy is defined as follows:
+%% $x,y \in \mathcal{X}$ are $\varepsilon-$\emph{separated in time $n$} if there exists $k \leqslant n$ such that $d\left(f^{(k)}(x),f^{(k)}(y)\right)>\varepsilon$. Then $(n,\varepsilon)-$separated sets are sets of points that are all $\varepsilon-$separated in time $n$, which
+%% leads to the definition of $s_n(\varepsilon,Y)$, being the maximal cardinality of all $(n,\varepsilon)-$separated sets. Using these notations,
+%% the topological entropy is defined as follows: $$h_{top}(\mathcal{X},f) = \displaystyle{\lim_{\varepsilon \rightarrow 0} \Big[ \limsup_{n \rightarrow +\infty} \dfrac{1}{n} \log s_n(\varepsilon,\mathcal{X})\Big]}.$$
+%% This value measures the average exponential growth of the number of distinguishable orbit segments.
+%% In this sense, it measures the complexity of the topological dynamical system, whereas
+%% the Shannon approach comes to mind when defining the following test~\cite{Nist10}:
+%% \begin{itemize}
+%% \item \textbf{Approximate Entropy Test}. Compare the frequency of the overlapping blocks of two consecutive/adjacent lengths ($m$ and $m+1$) against the expected result for a random sequence.
+%% \end{itemize}
+
+%% \item \textbf{Non-linearity, complexity}. Finally, let us remark that non-linearity and complexity are
+%% not only sought in general to obtain chaos, but they are also required for randomness, as illustrated by the two tests below~\cite{Nist10}.
+%% \begin{itemize}
+%% \item \textbf{Binary Matrix Rank Test}. Check for linear dependence among fixed length substrings of the original sequence.
+%% \item \textbf{Linear Complexity Test}. Determine whether or not the sequence is complex enough to be considered random.
+%% \end{itemize}
+%% \end{itemize}
+
+
+%% We have proven in our previous works~\cite{guyeux12:bc} that chaotic iterations satisfying Theorem~\ref{Th:Caractérisation des IC chaotiques} are, among other
+%% things, strongly transitive, topologically mixing, chaotic as defined by Li and Yorke,
+%% and that they have a topological entropy and an exponent of Lyapunov both equal to $ln(\mathsf{N})$,
+%% where $\mathsf{N}$ is the size of the iterated vector.
+%% These topological properties make that we are ground to believe that a generator based on chaotic
+%% iterations will probably be able to pass all the existing statistical batteries for pseudorandomness like
+%% the NIST one. The following subsections, in which we prove that defective generators have their
+%% statistical properties improved by chaotic iterations, show that such an assumption is true.
+
+%% \subsection{Details of some Existing Generators}
+
+%% The list of defective PRNGs we will use
+%% as inputs for the statistical tests to come is introduced here.
+
+%% Firstly, the simple linear congruency generators (LCGs) will be used.
+%% They are defined by the following recurrence:
+%% \begin{equation}
+%% x^n = (ax^{n-1} + c)~mod~m,
+%% \label{LCG}
+%% \end{equation}
+%% where $a$, $c$, and $x^0$ must be, among other things, non-negative and inferior to
+%% $m$~\cite{LEcuyerS07}. In what follows, 2LCGs and 3LCGs refer to two (resp. three)
+%% combinations of such LCGs. For further details, see~\cite{bfg12a:ip,combined_lcg}.
