\usepackage{amsmath}
\usepackage{color}
\usepackage{dsfont}
-
+\usepackage{graphicx}
\title{A Review of Chaotic Iteration Based Pseudorandom Number Generators}
\begin{definition}
+\label{defIC}
Let $f: \mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N}$ and
$S \subset \mathcal{P} \left(\llbracket1,\mathsf{N}\rrbracket\right)^\mathds{N}$.
\emph{Chaotic iterations} $(f, (x^0, S))$ are defined by:
\subsection{The Lyapunov Exponent}
-%\frame{
-% \frametitle{Exposant de Lyapunov}
-%\begin{block}{L'exposant de Lyapunov}
-%$$\lambda(x^0) = \displaystyle{\lim_{n \to +\infty} \dfrac{1}{n} \sum_{i=1}^n \ln \left| ~f'\left(x^{i-1}\right)\right|}$$
-%Il doit être positif pour multiplier les erreurs
-%\end{block}
-%}
-
-
-
-
-
-%\subsection*{Etude des systèmes itératifs}
-
-%%\frame{
-%% \frametitle{IC et propriété de Devaney}
-%%\begin{alertblock}{Théorème}
-%%$G_{f_0}$ est régulier et transitif (Devaney).
-
-%%Sa sensibilité est $\geqslant \mathsf{N}-1$.
-%%\end{alertblock}
-
-%%\uncover<2->{
-%% \begin{exampleblock}{Question}
-%% $f_0$ est-elle la seule fonction dont le système itératif vérifie la condition de Devaney ?
-%% \end{exampleblock}
-%%
-%% \vspace{0.5cm}
-
-%%Pour y répondre, nous avons utilisé le graphe de tous les possibles par itérations chaotiques : le GTPIC.}
-%%}
-
-
-
-
-%%\frame{
-%% \frametitle{Nombre de fonctions imprévisibles}
-%% \begin{alertblock}{Caractérisation des IC imprévisibles selon Devaney}
-%%$G_f$ vérifie l'hypothèse de Devaney $\Leftrightarrow$ Son graphe des possibles est fortement connexe.
-
-%%$\Rightarrow$ Il y a $\left(2^\mathsf{N}\right)^{2^\mathsf{N}}$ IC chaotiques.
-%%\end{alertblock}
-%%}
-
-
-
-
-
-
-
-%\frame{
-% \frametitle{Etude topologique}
-% \begin{exampleblock}{Etude topologique des ICs}
-% \begin{itemize}
-% \item $\forall f \in \mathcal{C}$, $Per\left(G_f\right)$ est infini dénombrable, $G_f$ est fortement transitive, est chaotique selon Knudsen,
-% \item $\left(\mathcal{X}, G_{f_0}\right)$ est topologiquement mélangeant, expansif (constante 1), est chaotique selon Li-Yorke, a une entropie topologique infinie, un exposant de Lyapunov de $ln(\mathsf{N})$
-% \item Indécomposabilité, instabilité, chaos de Wiggins, de la multiplicité des périodes...
-% \end{itemize}
-% \end{exampleblock}
-%}
-
-
-
-
-
-
-
-%\frame{
-% \frametitle{Graphe de tous les possibles par IC}
-% \begin{center}
-% \includegraphics[scale=0.55]{14.Caracterisation_des_IC_chaotiques_selon_Devaney/grapheTPICver2.pdf}
-% \end{center}
-%}
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%\section*{Topologie des programmes}
-%\frame{
-%% 'transition': Crossfade,
-% \begin{center}
-% \Huge{Topologie des programmes}
-%
-% \end{center}
-%}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-
-%%\frame{
-%% \frametitle{Premières questions}
-%% \begin{exampleblock}{Le chaos dans mon PC ?}
-%% Le désordre, l'imprévisibilité (vrai, sans perte) sont-ils possibles sur un ordinateur ?
-%%\begin{itemize}
-%% \item Il n'y a pas de réels sur mon PC
-%% \item Toute machine ayant un nombre fini d'états finit par entrer dans un cycle.
-%%\end{itemize}
-%% \end{exampleblock}
-%%}
-
-
-
+The last measure of chaos that has been regarded for our proposed family
+of pseudorandom number generators is the Lyapunov exponent. This
+quantity characterizes the rate of separation of infinitesimally close
+trajectories. Indeed, two trajectories in phase space with initial
+separation $\delta$ diverge at a rate approximately
+equal to $\delta e^{\lambda t}$,
+where $\lambda$ is the Lyapunov exponent, which is defined by:
+\begin{definition}
+Let $f:\mathds{R} \longrightarrow \mathds{R}$ be a differentiable
+function, and $x^0\in \mathds{R}$. The Lyapunov exponent is given by
+$$\lambda(x^0) = \displaystyle{\lim_{n \to +\infty} \dfrac{1}{n} \sum_{i=1}^n \ln \left| ~f'\left(x^{i-1}\right)\right|}.$$
+\end{definition}
+Obviously, this exponent must be positive to have a multiplication of
+initial errors, and thus chaos in this understanding.
+
+Having all these definitions in mind, we have studied the topological
+behavior of chaotic iterations presented in Definition~\ref{defIC}.
+
+\section{The Study of Iterative Systems}
+
+We have firstly stated that~\cite{gb11:bc,GuyeuxThese10}:
+
+\begin{theorem}
+ $G_{f_0}$ is regular and transitive on $(\mathcal{X},d)$, thus it is
+ chaotic according to Devaney.
+Furthermore, its constant of sensibility is greater than $\mathsf{N}-1$.
+\end{theorem}
+
+Thus the set $\mathcal{C}$ of functions $f:\mathds{B}^\mathsf{N}
+\longrightarrow \mathds{B}^\mathsf{N}$ making the chaotic iterations of
+Definition~\ref{defIC} a case of chaos according to Devaney, is a nonempty
+set. To characterize functions of $\mathcal{C}$, we have firstly stated
+that transitivity implies regularity for these particular iterated
+systems~\cite{bcgr11:ip}. To achieve characterization, we then have introduced the
+following graph.
+
+\begin{figure}
+ \centering
+ \includegraphics[scale=0.55]{grapheTPICver2.pdf}
+ \caption{Example of an asynchronous iteration graph}
+ \label{GTPIC}
+ \end{figure}
+
+
+
+Let $f$ be a map from $\mathds{B}^\mathsf{N}$ to itself. The
+{\emph{asynchronous iteration graph}} associated with $f$ is the
+directed graph $\Gamma(f)$ defined by: the set of vertices is
+$\mathds{B}^\mathsf{N}$; for all $x\in\mathds{B}^\mathsf{N}$ and
+$i\in \llbracket1;\mathsf{N}\rrbracket$,
+the graph $\Gamma(f)$ contains an arc from $x$ to $F_f(i,x)$.
+The relation between $\Gamma(f)$ and $G_f$ is clear: there exists a
+path from $x$ to $x'$ in $\Gamma(f)$ if and only if there exists a
+strategy $s$ such that the parallel iteration of $G_f$ from the
+initial point $(s,x)$ reaches the point $x'$. Figure~\ref{GTPIC} presents
+such an asynchronous iteration graph.
+We thus have proven that~\cite{bcgr11:ip}.
+
+
+\begin{theorem}
+$G_f$ is transitive, and thus chaotic according to Devaney,
+if and only if $\Gamma(f)$ is strongly connected.
+\end{theorem}
+
+This characterization makes it possible to quantify the number of
+functions in $\mathcal{C}$: it is equal to
+ $\left(2^\mathsf{N}\right)^{2^\mathsf{N}}$.
+Then the study of the topological properties of disorder of these
+iterative systems has been further investigated, leading to the following
+results.
+
+\begin{theorem}
+ $\forall f \in \mathcal{C}$, $Per\left(G_f\right)$ is infinitely countable, $G_f$ is strongly transitive and is chaotic according to Knudsen. It is thus undecomposable, unstable, and chaotic as defined by Wiggins.
+ \end{theorem}
+
+ \begin{theorem}
+$\left(\mathcal{X}, G_{f_0}\right)$ is topologically mixing,
+ expansive (with a constant equal to 1), chaotic as defined by
+ Li and Yorke, and has a topological entropy and an exponent of Lyapunov
+ both equal to $ln(\mathsf{N})$.
+\end{theorem}
+
+At this stage, a new kind of iterative systems that only manipulates
+integers have been discovered, leading to the questioning of their
+computing for security applications. In order to do so, the possibility
+of their computation without any loss of chaotic properties has first
+been investigated. These chaotic machines are presented in the next
+section.
+
+
+
+
+\section{Topology of Programs}
+
+
+The next stage was to prove that chaos was possible in finite machine.
+The two main problems were that: (1) Chaotic sequences are usually
+defined in the real line whereas define real numbers on computers
+is impossible. (2) All finite state machines always enter into a cycle
+when iterating, and this periodic behavior cannot be stated as chaotic.
+
+The first problem is disputable, as the shadow lemma proves that, when
+considering the sequence $x^{n+1} = trunc_k\left(f(x^n)\right)$, where
+$(f,[0,1])$ is a chaotic dynamical system and $trunc_k(x) =
+\dfrac{\lfloor 10^k x \rfloor}{10^k}$ is the truncated version of
+$x\in \mathds{R}$ at its $k-$th digits, then the sequence $(x^n)$ is as
+close as possible to a real chaotic orbit. Thus iterating a chaotic
+function on floating point numbers does not deflate the chaotic behavior
+as much. However, even if this first claim is not really a problem, we
+have prevent from any disputation by considering a tool (the chaotic
+iterations) that only manipulates integers bounded by $\mathsf{N}$.
+
+The second claim is surprisingly never considered as an issue when
+considering the generation of randomness on computers.
