]> AND Private Git Repository - review_prng.git/blobdiff - review_prng.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
avancées
[review_prng.git] / review_prng.tex
index 1ddc487ed270a04fff935bfacf15d8dab75f8893..80fece0e5c121f7add1f96af3e7d10eeeea95a06 100644 (file)
@@ -7,11 +7,11 @@
 \usepackage{amsmath}
 \usepackage{color}
 \usepackage{dsfont}
 \usepackage{amsmath}
 \usepackage{color}
 \usepackage{dsfont}
-
+\usepackage{graphicx}
 
 
 \title{A Review of Chaotic Iteration Based Pseudorandom Number Generators}
 
 
 \title{A Review of Chaotic Iteration Based Pseudorandom Number Generators}
-\author{Jacques M. Bahi, Jean-Fran\c cois Couchot, Raphaël Couturier, and Christophe Guyeux~\thanks{Authors in alphabetic order}}
+\author{Jacques M. Bahi, Jean-Fran\c cois Couchot, Raphaël Couturier,\\ Nicolas Friot, and Christophe Guyeux~\thanks{Authors in alphabetic order}}
 
 
 
 
 
 
@@ -27,7 +27,7 @@
 \section{Introduction}
 
 
 \section{Introduction}
 
 
-\section{Topologycal Study of Disorder}
+\section{Topological Study of Disorder}
 
 \subsection{Historical Context}
 
 
 \subsection{Historical Context}
 
@@ -58,16 +58,16 @@ cycles and order. Conversely, Li and Yorke have established in 1975~\cite{Li75}
 the presence of a point of period three implies chaos in the same situation
 than previously. By chaos, they mean the existence of points of any 
 period: this kind of disorder, which is the first occurrence of the
 the presence of a point of period three implies chaos in the same situation
 than previously. By chaos, they mean the existence of points of any 
 period: this kind of disorder, which is the first occurrence of the
-term ``chaos'' in the mathematical litterature, is thus related to the 
+term ``chaos'' in the mathematical literature, is thus related to the 
 multiplicity of periods. Since that time, the mathematical theory of
 chaos has known several developments to qualify or quantify the richness
 of chaos presented by a given discrete dynamical system, one of the most
 multiplicity of periods. Since that time, the mathematical theory of
 chaos has known several developments to qualify or quantify the richness
 of chaos presented by a given discrete dynamical system, one of the most
-famous work, although old, being the one of Devaney~\cite{devaney}.
+famous work, although old, being the one of Devaney~\cite{Devaney}.
 
 \subsection{Iterative Systems}
 
 In the distributed computing community, dynamical systems have been
 
 \subsection{Iterative Systems}
 
 In the distributed computing community, dynamical systems have been
-generatized to take into account delay transmission or heterogeneous
+generalized to take into account delay transmission or heterogeneous
 computational powers. Mathematically, the intended result is often one 
 fixed point resulting from the iterations of a given function over a
 Boolean vector, considering that:
 computational powers. Mathematically, the intended result is often one 
 fixed point resulting from the iterations of a given function over a
 Boolean vector, considering that:
@@ -117,6 +117,7 @@ are defined as follows~\cite{Robert}.
  
 
 \begin{definition}
  
 
 \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:
 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:
@@ -211,301 +212,316 @@ X^0 = (S,x^0) \in \mathcal{X}, \\
 \end{array}
 \right.$$
 Their topological disorder can then be studied.
 \end{array}
 \right.$$
 Their topological disorder can then be studied.
+To do so, a relevant distance must be defined of $\mathcal{X}$, as
+follows~\cite{GuyeuxThese10,bgw09:ip}:
+$$d((S,E);(\check{S};\check{E})) = d_e(E,\check{E}) +  d_s(S,\check{S})$$
+\noindent where $\displaystyle{d_e(E,\check{E}) = \sum_{k=1}^\mathsf{N} \delta (E_k, \check{E}_k)}$, ~~and~ $\displaystyle{d_s(S,\check{S}) = \dfrac{9}{\textsf{N}} \sum_{k = 1}^\infty \dfrac{|S^k-\check{S}^k|}{10^k}}$.
 
 
+This new distance has been introduced in \cite{bgw09:ip} to satisfy the following requirements.
+\begin{itemize}
+\item When the number of different cells between two systems is increasing, then their distance should increase too.
+\item In addition, if two systems present the same cells and their respective strategies start with the same terms, then the distance between these two points must be small because the evolution of the two systems will be the same for a while. Indeed, the two dynamical systems start with the same initial condition, use the same update function, and as strategies are the same for a while, then components that are updated are the same too.
+\end{itemize}
+The distance presented above follows these recommendations. Indeed, if the floor value $\lfloor d(X,Y)\rfloor $ is equal to $n$, then the systems $E, \check{E}$ differ in $n$ cells. In addition, $d(X,Y) - \lfloor d(X,Y) \rfloor $ is a measure of the differences between strategies $S$ and $\check{S}$. More precisely, this floating part is less than $10^{-k}$ if and only if the first $k$ terms of the two strategies are equal. Moreover, if the $k^{th}$ digit is nonzero, then the $k^{th}$ terms of the two strategies are different.
 
 
+It has then be stated that
+\begin{proposition}
+$G_f : (\mathcal{X},d) \to  (\mathcal{X},d)$ is a continuous function
+\end{proposition}
 
 
+With all this material, the study of chaotic iterations as a discrete
+dynamical system has then be realized. 
+This study is summarized in the next section.
 
 
+\subsection{A Topology for Chaotic Iterations}
 
 
-%\frame{
-% \frametitle{Métrique et continuité}
-
-%Distance sur $\mathcal{X}:$
-%$$d((S,E);(\check{S};\check{E})) = d_e(E,\check{E}) +  d_s(S,\check{S})$$
-
-%\noindent où $\displaystyle{d_e(E,\check{E}) = \sum_{k=1}^\mathsf{N} \delta (E_k, \check{E}_k)}$, ~~et~ $\displaystyle{d_s(S,\check{S}) = \dfrac{9}{\textsf{N}} \sum_{k = 1}^\infty \dfrac{|S^k-\check{S}^k|}{10^k}}$.
-%%\end{block}
-
-%\vspace{0.5cm}
-
-%\begin{alertblock}{Théorème}
-%La fonction $G_f : (\mathcal{X},d) \to  (\mathcal{X},d)$ est continue.
-%\end{alertblock}
-
-%}
-
-
-
-% \frame{
-%  \frametitle{\'Etude de $(\mathcal{X},d)$}
-%  \begin{block}{Propriétés de $(\mathcal{X},d)$}
-%  \begin{itemize}
-%    \item $\mathcal{X}$ est infini indénombrable
-%    \vspace{0.15cm}
-%    \item $(\mathcal{X},d)$ est un espace métrique compact, complet et parfait
-%  \end{itemize}
-%  \end{block}
-% 
-%  \vspace{0.5cm}
-% 
-%    \begin{block}{\'Etude de $G_{f_0}$}
-%    $G_{f_0}$ est surjective, mais pas injective \vspace{0.3cm}\newline $\Rightarrow (\mathcal{X},G_{f_0})$ pas réversible.
-%  \end{block}
-
-% }
-
-
-
-%%\frame{
-%% \frametitle{Etude des périodes}
-%% \begin{block}{Multiplicité des périodes ?}
-%% Soit $f_0:\mathds{B}^\mathsf{N} \rightarrow \mathds{B}^\mathsf{N}$ la négation vectorielle.
-%%   \begin{itemize}
-%%     \item $\forall k \in \mathds{N}, Per_{2k+1}(G_{f_0}) = \varnothing, card\left(Per_{2k+2}(G_{f_0})\right)>0$ \vspace{0.3cm} \linebreak  $\Rightarrow G_{f_0}$ pas chaotique sur $\mathcal{X}$
-%%     \item Cependant :
-%%     \begin{itemize}
-%%       \item Il y a chaos sur $\mathcal{X}^G = \mathcal{P}\left(\llbracket 1,\mathsf{N}\rrbracket\right)^\mathds{N}\times \mathds{B}^\mathsf{N}$.
-%%       \item $G_{f_0}$ possède plus de $n^2$ points périodiques de période $2n$.
-%%     \end{itemize}
-%%   \end{itemize}
-%% \end{block}
-%% \uncover<2->{
-%%    Cette multiplicité des périodes n'est pas le désordre complet...
-%% }
-%%}
-
-
-
-%\subsection*{Approche type Devaney/Knudsen}
-
-%\frame{
-%  \frametitle{Les approches Devaney et Knudsen}
-%  \begin{block}{3 propriétés pour de l'imprévisibilité}
-%    \begin{enumerate}
-%      \item \emph{Indécomposabilité.} On ne doit pas pouvoir simplifier le système
-%      \begin{itemize}
-%        \item Impossible de diviser pour régner
-%        \item Des orbites doivent visiter tout l'espace
-%      \end{itemize}
-%      \item \emph{Élément de régularité.}
-%      \begin{itemize}
-%        \item Contrecarre l'effet précédent
-%        \item Des points proches \textit{peuvent} se comporter complètement différemment
-%      \end{itemize}
-%      \item \emph{Sensibilité.} Des points proches \textit{peuvent} finir éloignés
-%    \end{enumerate}
-%  \end{block}
-%}
-
-
-%\frame{
-% \frametitle{Exemple : définition de Devaney}
-%\begin{enumerate}
-%\item \emph{Transitivité:} Pour chaque couple d'ouverts non vides $A,B \subset \mathcal{X}$, il existe $k \in \mathbb{N}$ tel que $f^{(k)}(A)\cap B \neq \varnothing$
-%\item \emph{Régularité:} Les points périodiques sont denses
-%\item \emph{Sensibilité aux conditions initiales:} Il existe $\varepsilon>0$ tel que $$\forall x \in \mathcal{X}, \forall \delta >0, \exists y \in \mathcal{X}, \exists n \in \mathbb{N}, d(x,y)<\delta \textrm{ et } d(f^{(n)}(x),f^{(n)}(y)) \geqslant \varepsilon$$
-%\end{enumerate}
-%}
-
-%\frame{
-%   \frametitle{Systèmes intrinsèquement compliqués}
-%   \begin{block}{Définitions de l'indécomposabilité}
-%   \begin{itemize}
-%     \item \emph{Indécomposable}: pas la réunion de deux parties non vides, fermées et t.q. $f(A) \subset A$
-%     \item \emph{Totalement transitive}: $\forall n \geqslant 1$, l'application composée $f^{(n)}$ est transitive.
-%     \item \emph{Fortement transitif}:
-%$\forall x,y \in \mathcal{X},$ $\forall r>0,$ $\exists z \in B(x,r),$ $\exists n \in \mathbb{N},$ $f^{(n)}(z)=y.$
-%     \item \emph{Topologiquement mélangeant}:  pour toute paire d'ouverts disjoints et non vides $U$ et $V$, il existe $n_0 \in \mathbb{N}$ tel que $\forall n \geqslant n_0, f^{(n)}(U) \cap V \neq \varnothing$.
-%   \end{itemize}
-%   \end{block}
-%}
-
-
-
-
-%\frame{
-%\frametitle{Stabilité et expansivité}
-%   \begin{block}{Définitions de la sensibilité}
-%     \begin{itemize}
-%       \item $(\mathcal{X},f)$ est \emph{instable} si tous ses points le sont: $\forall x \in \mathcal{X},$ $\exists \varepsilon >0,$ $\forall \delta > 0,$ $\exists y \in \mathcal{X},$ $\exists n \in \mathbb{N},$ $d(x,y)<\delta$  et $d(f^{(n)}(x),f^{(n)}(y)) \geqslant \varepsilon$
-%       \item $(\mathcal{X},f)$ est \emph{expansif} si
-%$\exists \varepsilon >0,$ $\forall x \neq y,$ $\exists n \in \mathbb{N},$ $d(f^{(n)}(x),f^{(n)}(y)) \geqslant \varepsilon$
-%     \end{itemize}
-%   \end{block}
-%}
-
-%%\frame{
-%%  \frametitle{Des systèmes imprévisibles}
-%%    \begin{block}{Définitions des systèmes dynamiques désordonnés}
-%%    \begin{itemize}
-%%      \item \emph{Devaney:} $(\mathcal{X},f)$ est sensible aux conditions initiales, régulier et transitif
-%%       \item \emph{Wiggins:} $(\mathcal{X},f)$ est transitif et sensible aux conditions initiales
-%%       \item \emph{Knudsen:} $(\mathcal{X},f)$ a une orbite dense et s'il est sensible aux conditions initiales
-%%       \item \emph{expansif:} $(\mathcal{X},f)$ est transitif, régulier et expansif
-%%    \end{itemize}
-%%    \end{block}
-%%}
-
-
-
-%\subsection*{Autres approches}
-
-
-%\frame{
-%  \frametitle{Selon Li et Yorke}
-%    \begin{block}{Définitions}
-%    \begin{description}
-%\item[Couple de Li-Yorke.] $(x,y)$ en est un quand: $\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.$
-
-%\item[Ensemble brouillé.] $B \subset \mathcal{X}$ en est un si tout couple de points distincts de $B$ est de Li-Yorke.
-
-%\item[Systèmes de Li-Yorke.] $\mathcal{X}$ est compact et contient un ensemble brouillé indénombrable.
-%\end{description}
-%\end{block}
-%}
-
-
-
-
-
-
-%\frame{
-% \frametitle{Approche entropie topologique}
-%   \begin{block}{Entropie topologique}
-%   \begin{itemize}
-%   \item $x,y \in \mathcal{X}$ sont ~$\varepsilon-$\emph{séparés en temps $n$} s'il existe $k \leqslant n$ tel que $d\left(f^{(k)}(x),f^{(k)}(y)\right)>\varepsilon$.
-%   \item Les ensembles $(n,\varepsilon)-$séparé sont des ensembles de points qui seront tous $\varepsilon-$séparés en temps $n$
-%   \item $s_n(\varepsilon,Y)$: cardinal maximal d'un ensemble $(n,\varepsilon)-$séparé $$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]}$$
-%   \end{itemize}
-%   \end{block}
-%}
-
-
-
-
-%\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}
-%}
-
-
-
-
+The topological space on which chaotic iterations are defined has
+firstly been investigated, leading to the following result~\cite{gb11:bc,GuyeuxThese10}:
+\begin{proposition}
+$\mathcal{X}$ is an infinitely countable metric space, being both
+compact, complete, and perfect (each point is an accumulation point).
+\end{proposition}
+These properties are required in some topological specific 
+formalization of a chaotic dynamical system, justifying their
+proofs.
 
 
+Concerning $G_{f_0}$, it has been stated that~\cite{GuyeuxThese10}.
+\begin{proposition}
+$G_{f_0}$ is surjective, but not injective, and so the dynamical system $(\mathcal{X},G_{f_0})$ is not reversible.
 
 
+Furthermore, if we denote by $Per_k(f)$ the set of periodic points 
+of period $k$ for $f$, we have 
+ $\forall k \in \mathds{N}, Per_{2k+1}(G_{f_0}) = \varnothing, card\left(Per_{2k+2}(G_{f_0})\right)>0$.
+\end{proposition}
+So $ G_{f_0}$ does not present the existence of points of any period referred as chaos in the article of Li and Yorke~\cite{Li75}.
+However~\cite{GuyeuxThese10}:
+     \begin{itemize}
+       \item This kind of disorder can be stated on $\mathcal{X}^G = \mathcal{P}\left(\llbracket 1,\mathsf{N}\rrbracket\right)^\mathds{N}\times \mathds{B}^\mathsf{N}$.
+       \item $G_{f_0}$ possesses more than $n^2$ points of period $2n$.
+     \end{itemize}
+Additionally, this existence of points of any period has been rejected
+by the community to the benefit of more recent notions of chaos, 
+like those developed these last decades by Devaney~\cite{Devaney}, Knudsen~\cite{Knudsen94}, etc.
+These approaches are recalled in the next section.
+
+\section{The Mathematical Theory of Chaos}
+
+We will present in this section various understanding of a chaotic behavior for a discrete
+dynamical system.
+
+\subsection{Approaches Similar to Devaney}
+
+In these approaches, three ingredients are required for unpredictability. 
+Firstly, the system must be intrinsically complicated, undecomposable: it cannot be simplified into two
+subsystems that do not interact, making any divide and conquer strategy 
+applied to the system inefficient. In particular, a lot of orbits must visit
+the whole space. Secondly, an element of regularity is added, to counteract
+the effects of the first ingredient, leading to the fact that closed points
+can behave in a completely different manner, and this behavior cannot be predicted.
+Finally, sensibility of the system is demanded as a third ingredient, making that
+closed points can finally become distant during iterations of the system.
+This last requirement is, indeed, often implied by the two first ingredients.
+
+Having this understanding of an unpredictable dynamical system, Devaney has
+formalized in~\cite{Devaney} the following definition of chaos.
 
 
+\begin{definition}
+A discrete dynamical system $x^0 \in \mathcal{X}, x^{n+1}=f(x^n)$ on a
+metric space $(\mathcal{X},d)$ is said to be chaotic according to Devaney
+if it satisfies the three following properties:
+    \begin{enumerate}
+\item \emph{Transitivity:} For each couple of open sets $A,B \subset \mathcal{X}$, there exists $k \in \mathbb{N}$ such that $f^{(k)}(A)\cap B \neq \varnothing$.
+\item \emph{Regularity:} Periodic points are dense in $\mathcal{X}$.
+\item \emph{Sensibility to the initial conditions:} There exists $\varepsilon>0$ such that $$\forall x \in \mathcal{X}, \forall \delta >0, \exists y \in \mathcal{X}, \exists n \in \mathbb{N}, d(x,y)<\delta \textrm{ and } d(f^{(n)}(x),f^{(n)}(y)) \geqslant \varepsilon.$$
+\end{enumerate}
+\end{definition}
 
 
+The system can be intrinsically complicated for various other understanding of this wish, that are 
+not equivalent one another, like:
+\begin{itemize}
+    \item \emph{Undecomposable}: it is not the union of two nonempty closed subsets that are positively invariant ($f(A) \subset A$).
+  \item \emph{Total transitivity}: $\forall n \geqslant 1$, the function composition $f^{(n)}$ is transitive.
+  \item \emph{Strong transitivity}: $\forall x,y \in \mathcal{X},$ $\forall r>0,$ $\exists z \in B(x,r),$ $\exists n \in \mathbb{N},$ $f^{(n)}(z)=y.$
+  \item \emph{Topological mixing}:  for all pairs of disjoint open nonempty sets $U$ and $V$, there exists $n_0 \in \mathbb{N}$ such that $\forall n \geqslant n_0, f^{(n)}(U) \cap V \neq \varnothing$.
+\end{itemize}
 
 
 
 
+Concerning the ingredient of sensibility, it can be reformulated as follows.
+\begin{itemize}
+  \item $(\mathcal{X},f)$ is \emph{unstable} is all its points are unstable: $\forall x \in \mathcal{X},$ $\exists \varepsilon >0,$ $\forall \delta > 0,$ $\exists y \in \mathcal{X},$ $\exists n \in \mathbb{N},$ $d(x,y)<\delta$ and $d(f^{(n)}(x),f^{(n)}(y)) \geqslant \varepsilon$.
+  \item $(\mathcal{X},f)$ is \emph{expansive} is $\exists \varepsilon >0,$ $\forall x \neq y,$ $\exists n \in \mathbb{N},$ $d(f^{(n)}(x),f^{(n)}(y)) \geqslant \varepsilon$
+\end{itemize}
 
 
+These variety of definitions lead to various notions of chaos. For instance, 
+a dynamical system is chaotic according to Wiggins if it is transitive and
+sensible to the initial conditions. It is said chaotic according to Knudsen
+if it has a dense orbit while being sensible. Finally, we speak about
+expansive chaos when the properties of transitivity, regularity, and expansivity
+are satisfied.
+
+
+
+\subsection{Li-Yorke approach}
+
+The approach for chaos presented in the previous section, considering that
+a chaotic system is a system intrinsically complicated (undecomposable),
+with possibly an element of regularity and/or sensibility, has been
+completed by other understanding of chaos. Indeed, as ``randomness''
+or ``infiniteness'', a single universal definition of chaos is cannot
+be found. The kind of behaviors that are attempted to be described are
+too much complicated to enter into only one definition. Instead, a 
+large panel of mathematical descriptions have been proposed these last
+decades, being all theoretically justified. Each of these definitions
+give illustration to some particular aspects of a chaotic behavior.
+
+The first of these parallel approaches can be found in the pioneer
+work of Li and Yorke~\cite{Li75}. In their well-known article entitled
+``Period three implies chaos'', they rediscovered a weaker formulation of 
+the Sarkovskii's theorem, meaning that when a discrete dynamical system 
+$(f,[0,1])$, with $f$ continuous, has a 3-cycle, then it has too a 
+$n-$cycle, $\forall n \leqslant 2$. The community has not adopted this
+definition of chaos, as several degenerated systems satisfy this property.
+However, on their article~\cite{Li75}, Li and Yorke have studied too 
+another interesting property, which has led to a notion of chaos 
+``according to Li and Yorke'', which is recalled below.
+
+Let us firstly introduce the definition of Li-Yorke scrambled couple
+of points. This is points that never stop to oscillate.
 
 
+\begin{definition}
+Let $(\mathcal{X},d)$ a metric space and $f:\mathcal{X} \longrightarrow
+\mathcal{X}$ a continuous map. $(x,y)\in \mathcal{X}^2$ is a scrambled 
+couple of points if $lim inf_{n\rightarrow \infty} d(f^n(x),f^n(y))=0$
+and  $lim sup_{n\rightarrow \infty} d(f^n(x),f^n(y))>0$.
+\end{definition}
 
 
+A scrambled set is a set in which any couple of points oscillate (are
+a scrambled couple), whereas a Li-Yorke chaotic system is a system 
+possessing an uncountable scrambled set.
 
 
 
 
+\subsection{Topological Entropy Approach}
 
 
+The topological entropy of a topological dynamical system,
+firstly introduced in 1965 by Adler, Konheim, and McAndrew~\cite{Adler65}, 
+is a nonnegative real number that measures the complexity of the system. 
+It represents the exponential growth rate of the number of distinguishable 
+orbits of the iterates, for a system given by an iterated function.
+It can be formulated as follows.
 
 
+Let $f:\mathcal{X} \longrightarrow \mathcal{X}$ be a continuous map on
+a compact metric space $(\mathcal{X},d)$. For each natural 
+number $n$, a new metric $d_n$ is defined on $\mathcal{X}$ by 
+$$d_n(x,y)=\max\{d(f^i(x),f^i(y)): 0\leq i<n\}.$$
 
 
+Given any $\varepsilon >0$ and $n \geqslant 1$, two points of 
+$\mathcal{X}$ are $\varepsilon$-close with respect to 
+this metric if their first $n$ iterates are $\varepsilon$-close. This 
+metric allows one to distinguish in a neighborhood of an orbit the 
+points that move  away from each other during the iteration from the 
+points that travel together. 
 
 
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%\section*{Topologie des programmes}
-%\frame{
-%% 'transition': Crossfade,
-% \begin{center}
-%   \Huge{Topologie des programmes}
-%   
-%  \end{center}
-%}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+A subset $E$ of $\mathcal{X}$ is said to be $(n,\varepsilon)$-separated 
+if each pair of distinct points of $E$ is at least $\varepsilon$ apart 
+in the metric $d_n$. Denote by $N(n, \varepsilon)$ the 
+maximum cardinality of a $(n,\varepsilon)$-separated set. 
+$N(n, \varepsilon)$ represents the number of distinguishable orbit 
+segments of length $n$, assuming that we cannot distinguish points 
+within $\varepsilon$ of one another. 
 
 
+\begin{definition}
+The topological 
+entropy of the map $f$ is defined by
+$$h(f)=\lim_{\epsilon\to 0} \left(\limsup_{n\to \infty} \frac{1}{n}
+\log N(n,\epsilon)\right).$$
+\end{definition}
 
 
 
 
-%%\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 limit defining $h(f)$ may 
+be interpreted as the measure of the average exponential growth of the 
+number of distinguishable orbit segments. In this sense, it measures 
+complexity of the topological dynamical system $(\mathcal{X}, f)$.
 
 
+\subsection{The Lyapunov Exponent}
 
 
+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.