X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/review_prng.git/blobdiff_plain/62c3786a4c8ba104653ce9d11e4bba511806814e..905e5b647fdc00743e18cb72146a010d5a456287:/review_prng.tex

diff --git a/review_prng.tex b/review_prng.tex
index c6ab2f1..80fece0 100644
--- a/review_prng.tex
+++ b/review_prng.tex
@@ -1,6 +1,2000 @@
 \documentclass{article}
+\usepackage[utf8x]{inputenc}
+\usepackage[standard]{ntheorem}
+\usepackage[english]{babel}
+
+\usepackage{stmaryrd}
+\usepackage{amsmath}
+\usepackage{color}
+\usepackage{dsfont}
+\usepackage{graphicx}
+
+
+\title{A Review of Chaotic Iteration Based Pseudorandom Number Generators}
+\author{Jacques M. Bahi, Jean-Fran\c cois Couchot, RaphaÃ«l Couturier,\\ Nicolas Friot, and Christophe Guyeux~\thanks{Authors in alphabetic order}}
+
+
 
 \begin{document}
 
+\maketitle
+
+\begin{abstract}
+
+\end{abstract}
+
+
+\section{Introduction}
+
+
+\section{Topological Study of Disorder}
+
+\subsection{Historical Context}
+
+Pseudorandom number generators are recurrent sequences having a disordered behavior.
+
+Recurrent sequences, also called discrete dynamical systems, of the form 
+\begin{equation}
+\label{sdd}
+u^0 \in \mathds{R}, u^{n+1} = f(u^n),
+\end{equation}
+with 
+$f$ continuous, have been well studied since the early years of mathematical
+analysis. They are widely used, for instance to resolve equations using a
+Newton method, or when approximating the solutions to differential equations 
+using finite difference equations to approximate derivatives.
+The context study was the seek for convergence, which is for instance guarantee
+when using monotonic functions or contractions. 
+In the middle of the last century, Coppel has 
+established a link between this desire of convergence
+and the existence of a cycle in iterations~\cite{Coppel55}. 
+More precisely, his theorem states that, considering Eq.~\eqref{sdd} with a function
+$f:I \longrightarrow I$ continuous on the line segment $I$, the absence of
+any 2-cycle implies the convergence of the discrete dynamical system.
+
+This theorem establish a clear link between the existence of a cycle of 
+a given length and the convergence of the system. In other words, between
+cycles and order. Conversely, Li and Yorke have established in 1975~\cite{Li75} that
+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 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
+famous work, although old, being the one of Devaney~\cite{Devaney}.
+
+\subsection{Iterative Systems}
+
+In the distributed computing community, dynamical systems have been
+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:
+\begin{itemize}
+\item at time $t$, $x^{t}$ is computed using not only $x^{t-1}$, but 
+potentially any $x^{k}, k<t$, due to delay transmission,
+\item not all the components of $x^{t}$ are supposed to be updated at
+each iteration: each component represents a unit of computation, and 
+these units have not the same processing frequency.
+\end{itemize} 
+
+These considerations lead to the following definition of an iterative
+system~\cite{GuyeuxThese10}.
+
+\begin{definition}
+Iterative systems on a set $\mathcal{X}$ are defined by
+$$\left\{
+  \begin{array}{l}
+    x^0 \in \mathcal{X}\\
+    x^{n+1} = f^n(x^0, \hdots, x^n)
+  \end{array}
+ \right.$$
+where $f^n:\mathcal{X}^{n+1}\rightarrow \mathcal{X}$.
+\end{definition}
+
+Some particular cases of these iterative systems are well documented,
+namely the serial, parallel, or chaotic modes.
+In the serial mode, each component is updated one by one, whereas the
+parallel mode consists in updating all the components at each iteration,
+leading to an usual discrete dynamical system.
+These modes are compliant with the definition above, 
+as the parallel mode consists in considering that the sequence
+$f^n$ defined above is constant equal to a given $f: \mathcal{X} 
+\longrightarrow \mathcal{X}$,
+whereas the serial mode can be rewritten as parallel iterations of
+$$ G=F_\mathsf{N} \circ \ldots \circ F_2 \circ F_1 $$
+where, $\forall i \in \llbracket 1, \mathsf{N} \rrbracket $:
+$$\begin{array}{rccc}
+F_i: & \mathcal{X} & \longrightarrow & \mathcal{X}\\
+        & (x_1, \hdots, x_\mathsf{N}) & \longmapsto & \left(x_1, \hdots, x_{i-1},f_i\left(x_1, \hdots, x_\mathsf{N}\right), x_{i+1}, \hdots, x_\mathsf{N}\right).
+\end{array}$$
+
+
+
+Finally, iterative systems in chaotic mode, simply called chaotic iterations,
+are defined as follows~\cite{Robert}.
+ 
+
+\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:
+$$\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^{n}_i = \left\{
+\begin{array}{ll}
+x^{n-1}_{i} & \textrm{ if } i \notin S^n\\
+f(x^{n-1})_{i} & \textrm{ if } i \in S^n
+\end{array}
+\right.
+\end{array}
+\right.$$
+\end{definition}
+
+\emph{A priori}, there is no relation between these chaotic iterations
+and the mathematical theory of chaos recalled in the previous section.
+On our side, we have regarded whether these chaotic iterations can 
+behave chaotically, as it is defined for instance by Devaney, and if so, 
+in which applicative context this behavior can be profitable.
+This questioning has led to a first necessary condition of non convergence~\cite{GuyeuxThese10}.
+
+\begin{proposition}
+Let $f : \mathds{B}^\mathsf{N} \to \mathds{B}^\mathsf{N}$ and 
+$S \in \llbracket 1, \mathsf{N} \rrbracket^{\mathds{N}}$. 
+If the chaotic iterations $\left(f,(x^0,S)\right)$ are not convergent, then:
+\begin{itemize}
+\item either $f$ is not a contraction, meaning that there is no Boolean matrix
+    $M$ of size $\mathsf{N}$ satisfying $\forall x,y\in \mathds{B}^\mathsf{N}$,
+    $d(f(x),f(y)) \leqslant M d(x,y)$, where $d$ is here the ``vectorial distance''
+    defined by $d(x,y) = \left(\begin{array}{c} \delta(x_1,y_1)\\ \vdots \\ \delta(x_\mathsf{N}, 
+    y_\mathsf{N}) \end{array}\right)$, with $\delta$ the discrete metric defined by $\delta(x,y) = \left\{\begin{matrix} 1 &\mbox{if}\ x\neq y , \\ 0 &\mbox{if}\ x = y \end{matrix}\right.$, and $\leqslant$ is the inequality term by term~\cite{Robert}.
+\item or $S$ is not pseudo-periodic: it is not constituted by an infinite succession of finite sequences, each having any element of $\llbracket
+    1, \mathsf{N} \rrbracket$ at least once.
+\end{itemize}
+\end{proposition}
+
+The second alternative of the proposition above concerns the strategy,
+which should be provided by the outside world. Indeed, in our opinion, 
+chaotic iterations can receive a PRNG $S$ as input, and due to 
+properties of disorder of $f$, generate a new pseudorandom sequence
+that presents better statistical properties than $S$. Having this 
+approach in mind, we thus have searched vectorial Boolean iteration
+functions that are not contractions. The vectorial negation function
+$f_0:\mathds{B}^\mathsf{N} \longrightarrow \mathds{N}^\mathsf{N},$
+$(x_1, \hdots, x_\mathsf{N}) \longmapsto (\overline{x_1}, \hdots, 
+\overline{x_\mathsf{N}}) $ is such a function, which served has a
+model in our further studies ($\overline{x}$ stands for the negation
+of the Boolean $x$).
+
+The quantity of disorder generated by such chaotic iterations, when
+satisfying the proposition above, has then been measured. To do so, 
+chaotic iterations have first been rewritten as simple discrete 
+dynamical systems, as follows.
+
+
+\subsection{Chaotic Iterations as Dynamical Systems}
+
+The problems raised by such a formalization can be summarized as 
+follows. 
+Chaotic iterations are defined in the discrete mathematics framework,
+considering $x^0 \in \mathds{B}^\mathds{N}$ and $S \in \mathcal{S} = \llbracket 1,\mathsf{N}\rrbracket^\mathds{N}$, and iterations having the
+form 
+$$x_i^{n+1} = \left\{ \begin{array}{ll} x^{n}_{i} & \textrm{ si } i \neq S^n\\ f(x^{n})_{i} & \textrm{ si } i = S^n \end{array} \right.$$ 
+where $f: \mathds{B}^\mathsf{N} \to \mathds{B}^\mathsf{N}$.
+However, the mathematical theory of chaos takes place into a 
+topological space $(\mathcal{X},\tau)$. It studies the iterations
+$x^0 \in \mathcal{X}$, $\forall n \in \mathds{N}, x^{n+1} = f(x^n)$,
+where $f : \mathcal{X} \to \mathcal{X}$ is continuous for the
+topology $\tau$.
+
+To realize the junction between these two frameworks, the following
+material has been introduced~\cite{GuyeuxThese10,bgw09:ip}:
+\begin{itemize}
+\item the shift function: $\sigma : \mathcal{S} \longrightarrow \mathcal{S}, (S^n)_{n \in \mathds{N}} \mapsto (S^{n+1})_{n \in \mathds{N}}$.
+\item the initial function, defined by $i : \mathcal{S} \longrightarrow \llbracket 1 ; \mathsf{N} \rrbracket, (S^n)_{n \in \mathds{N}} \mapsto S^0$
+\item and $F_f : \llbracket 1 ; \mathsf{N} \rrbracket \times \mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N},$ $$(k,E) \longmapsto  \left( E_j.\delta(k,j) + f(E)_k.\overline{\delta (k,j)} \right)_{j \in \llbracket 1 ; \mathsf{N} \rrbracket}$$
+\end{itemize}
+where $\delta$ is the discrete metric.
+
+
+
+
+Let $\mathcal{X} = \llbracket 1 ; \mathsf{N} \rrbracket^\mathds{N} \times \mathds{B}^\mathsf{N},$ and $G_f\left(S,E\right) = \left(\sigma(S), F_f(i(S),E)\right).$ 
+Chaotic iterations $\left(f, (S,x^0)\right)$ can be modeled by the 
+discrete dynamical system:
+$$\left\{
+\begin{array}{l}
+X^0 = (S,x^0) \in \mathcal{X}, \\
+\forall k \in \mathds{N}, X^{k+1} = G_f(X^k).
+\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}
+
+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. 
+
+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}
+
+
+
+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.
+
+
+
+
+%%\frame{
+%%  \frametitle{Mode d'emploi}
+%%  \begin{alertblock}{Chaos sur machine: quelques rÃ¨gles}
+%%    \begin{enumerate}
+%%      \item Ne pas laisser la machine travailler en vase clos %\newline
+%%      %$\Rightarrow$ Une nouvelle entrÃ©e Ã  chaque itÃ©rÃ©e
+%%      \item Utiliser les mÃ©dias sur lesquels on travaille %\newline
+%%      %$\Rightarrow$ Ensemble infini dÃ©nombrable
+%%      \item Ne manipuler que des entiers 
+%%      \item \'Eviter les tailles fixes %(graine, nombre d'itÃ©rations, etc.)
+%%    \end{enumerate}
+%%  \end{alertblock}
+%%}
+
+
+
+
+
+%\frame{
+%  \frametitle{Introduction}
+%  \begin{block}{Deux cas de figure}
+%    \begin{itemize}
+%      \item En vase clos :
+%      \begin{itemize}
+%        \item 4 Go de mÃ©moire $\Rightarrow 2^{4000000000}$ Ã©tats possibles...
+%        \item Lemme de filature/lemme fantÃ´me
+%      \end{itemize}
+%      \item $\mathcal{X}=\mathds{B}^\mathsf{N}\times \mathcal{P}\left(\llbracket 1;\mathsf{N}\rrbracket\right)^\mathds{N}$:
+%      \begin{itemize}
+%        \item Pas de rÃ©els, que des entiers bornÃ©s par $\mathsf{N}$
+%        \item On peut utiliser le mÃ©dia Ã  chaque itÃ©rÃ©e
+%      \end{itemize}
+%    \end{itemize}
+%  \end{block}
+%}
+
+
+
+
+
+
+%\frame{
+%  \frametitle{Introduction}
+%  \begin{exampleblock}{Deux questions}
+%%  Vos ICs sont chaotiques, mais pour moi c'est pas Ã§a une machine, un programme.
+%\begin{itemize}
+%      \item Peut-on construire des automates chaotiques ?
+%      \item Peut-on Ã©valuer si un programme est chaotique ?
+%\end{itemize}
+%  \end{exampleblock}
+%}
+
+
+
+
+
+%\frame{
+% \frametitle{Une machine de Moore chaotique}
+%  \begin{center}
+%   \includegraphics[scale=0.55]{14.Caracterisation_des_IC_chaotiques_selon_Devaney/grapheTPICver2.pdf}
+%  \end{center}
+%}
+
+
+
+
+
+%\frame{
+%\frametitle{Le chaos d'un programme}
+%\begin{block}{Machines de Turing et systÃ¨mes itÃ©ratifs}
+%Soit $(w,i,q)$ la configuration actuelle de la machine de Turing\\
+%\begin{center}
+%\includegraphics[scale=0.3]{Steganalyse/Medias/Turing.pdf} 
+%\end{center}
+%\begin{itemize}
+%\item $w=\sharp^{-\omega} w(0) \hdots w(k)\sharp^{\omega}$ est la bande de lecture,
+%\item $i$ est la position de la tÃªte de lecture,
+%\item $q$ dÃ©crit l'Ã©tat de la machine,
+%\item  et $\delta$ est sa fonction de transition. 
+%\end{itemize}
+%\end{block}
+%}
+
+
+
+%\frame{
+%\frametitle{Le chaos d'un programme}
+%\begin{block}{Machines de Turing et systÃ¨mes itÃ©ratifs}
+%On dÃ©finit $f$ par: 
+
+%\begin{itemize}
+%\item Si $\delta(q;w(i)) = (q'; a; \rightarrow)$, alors $f(w(0) \hdots w(k);i;q) = ( w(0) \hdots w(i-1) ~ a ~ w(i+1) \hdots w(k); i+1; q')$
+%\item Si $\delta(q;w(i)) = (q'; a; \leftarrow)$, alors $f( w(0) \hdots w(k);i;q) = (w(0) \hdots w(i-1) ~ a ~ w(i+1) \hdots w(k); i-1; q')$
+%\end{itemize} 
+
+%La machine peut Ãªtre Ã©crite sous la forme $x^{n+1}=f(x^n)$
+%\end{block}
+%}
+
+
+
+
+
+
+
+%\frame{
+%  \frametitle{A quoi Ã§a sert ?}
+%  \begin{exampleblock}{Un programme chaotique, pour quoi faire ?}
+%\begin{itemize}
+%      \item Se placer dans de bonnes conditions lors de conception de nouveaux algorithmes 
+%      \item Renforcer les attaques (virus chaotique) 
+%      \item Simuler numÃ©riquement des processus chaotiques
+%      \item Renforcer la sÃ©curitÃ©     
+%      \item Battre l'intelligence artificielle
+%\end{itemize}
+%  \end{exampleblock}
+%  
+%%  \uncover<3->{
+%%  Tentons une premiÃ¨re illustration
+%%  }
+%}
+
+
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%\section{Applications aux PRNGs}
+%\subsection*{PRNGs}
+%\begin{frame}{Applications}
+%% 'transition': Crossfade,
+%  \begin{center}
+%   \Huge{Applications}
+
+%\medskip
+%   \huge{GÃ©nÃ©rateurs pseudo-alÃ©atoires}
+%  \end{center}
+%\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%\frame{
+%  \frametitle{Chaos et alÃ©as}
+%    \begin{block}{Motivations: La batterie du NIST}
+%      \begin{itemize}
+%\item \textbf{TransitivitÃ©s}
+%    \begin{itemize}
+%        \item \textbf{Random Excursions Variant Test.} To detect deviations from the expected number of visits to various states in the random walk.
+%        \item \textbf{Random Excursions Test.} To 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 selon Li-Yorke}
+%    \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}
+%\end{itemize}
+%\end{block}
+%}    
+
+%\frame{
+%  \frametitle{Chaos et alÃ©as}
+%    \begin{block}{Motivations: La batterie du NIST}
+%      \begin{itemize}
+%    \item \textbf{RÃ©gularitÃ©}
+%    \begin{itemize}
+%        \item \textbf{Non-overlapping Template Matching Test} To detect generators that produce too many occurrences of a given non-periodic (aperiodic) pattern (m is the length in bits of each template which is the target string).
+%        \item \textbf{Discrete Fourier Transform (Spectral) Test} To detect periodic features (i.e., repetitive patterns that are near each other) in the tested sequence that would indicate a deviation from the assumption of randomness.
+%    \end{itemize}
+%    \item \textbf{Entropie}
+%    \begin{itemize}
+%\item \textbf{Approximate Entropy Test} To compare the frequency of overlapping blocks of two consecutive/adjacent lengths (m and m+1) against the expected result for a random sequence (m is the length of each block).
+%    \end{itemize}
+%    \end{itemize}
+%\end{block}
+%}    
+
+%\frame{
+%  \frametitle{Chaos et alÃ©as}
+%    \begin{block}{Motivations: La batterie du NIST}
+%      \begin{itemize}
+%    \item \textbf{Non-linÃ©aritÃ©, complexitÃ©}
+%    \begin{itemize}
+%\item \textbf{Binary Matrix Rank Test} To check for linear dependence among fixed length substrings of the original sequence.
+%\item \textbf{Linear Complexity Test} To determine whether or not the sequence is complex enough to be considered random (M is the length in bits of a block).
+%      \end{itemize}
+%\end{itemize}
+%    \end{block}
+%}
+
+
+%\subsection*{Le Old CI PRNG}
+%\frame{
+%  \frametitle{Notre PRNG}
+% \begin{alertblock}{Le PRNG $CI_f(PRNG_1,PRNG_2)$}
+% \begin{description}
+%\item[\underline{ParamÃ¨tres:}] Une fonction $f: \mathds{B}^\mathsf{N} \rightarrow  \mathds{B}^\mathsf{N}$, et deux PRNGs:\\
+%\begin{itemize}
+%\item $S\in\llbracket 1,\mathsf{N}\rrbracket^\mathds{N}$
+%\item et $m\in S^\mathds{N}, S \subset \mathds{N}$
+%\end{itemize}
+%\item[\underline{Graine:}] Les graines de $S$ et $m$, et $E\in \mathds{B}^\mathsf{N}$\\
+%\item[\underline{PRNG:}] $\left(G_f(E,S)^{m^i}\right)_{i\in\mathds{N}}$
+%\end{description}
+% \end{alertblock}
+% 
+%% \uncover<2->{
+%% \begin{exampleblock}{Exemple: $X^{n+1} = X^n \oplus Y^n$}
+%%  oÃ¹ $Y \in \llbracket 0, 2^{\mathsf{N}}-1 \rrbracket^\mathds{N}$
+%% \end{exampleblock}
+%% }
+%}
+
+
+
+%%\frame{
+%%  \frametitle{Old CI PRNG: Illustration}
+%%  \begin{block}{}
+%%\begin{figure}
+%%\centering
+%%  \includegraphics[scale=0.4]{OldCI1.png}
+%%  \caption{Le Old CI PRNG}
+%%  \end{figure}
+%%  \end{block}
+%%}
+
+
+
+%%\frame{
+%%  \frametitle{Old CI PRNG: Illustration}
+%%  \begin{block}{}
+%%\begin{figure}
+%%\centering
+%%  \includegraphics[scale=0.41]{OldCI2.png}
+%%  \caption{Le Old CI PRNG}
+%%  \end{figure}
+%%  \end{block}
+%%}
+
+
+%%\frame{
+%%  \frametitle{Old CI PRNG: Illustration}
+%%  \begin{block}{}
+%%\begin{figure}
+%%\centering
+%%  \includegraphics[scale=0.4]{OldCI3.png}
+%%  \caption{Le Old CI PRNG}
+%%  \end{figure}
+%%  \end{block}
+%%}
+
+
+
+
+%%\frame{
+%%  \frametitle{Old CI PRNG: Illustration}
+%%  \begin{block}{}
+%%\begin{figure}
+%%\centering
+%%  \includegraphics[scale=0.4]{OldCI4.png}
+%%  \caption{Le Old CI PRNG}
+%%  \end{figure}
+%%  \end{block}
+%%}
+
+
+
+%%\frame{
+%%  \frametitle{Old CI PRNG: Illustration}
+%%  \begin{block}{}
+%%\begin{figure}
+%%\centering
+%%  \includegraphics[scale=0.4]{OldCI5.png}
+%%  \caption{Le Old CI PRNG}
+%%  \end{figure}
+%%  \end{block}
+%%}
+
+
+
+
+%%\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}
+%%}
+
+
+
+
+
+%\begin{frame}{Le Old $CI_{f_0}$(logistic,logistic)}
+%\begin{block}{}
+%\begin{tabular}{llllllllll}
+%m (logistic map):&\uncover<1->{2}	&\uncover<3->{~}		&\uncover<4->{~}	&\uncover<5->{~1}&\uncover<8->{~4}&\uncover<9->{~}&\uncover<10->{~}&\uncover<11->{~}& \uncover<13->{...}\\
+%S (logistic map):&\uncover<2->{1}	&\uncover<3->{~3}		&\uncover<4->{~}	&\uncover<6->{~2}&\uncover<9->{~1}&\uncover<10->{~1}&\uncover<11->{~2}&\uncover<12->{~1}& \uncover<14->{...}\\
+%\end{tabular}
+%\end{block}
+% 
+%\begin{block}{\'Etat interne du systÃ¨me x:}
+%\begin{equation}
+%\label{Basic equations}
+%\begin{array}{r@{\;}l}
+%\ \textbf{0}\uncover<2->{\rightarrow \textbf{1}} \uncover<3->{\rightarrow 1}  \uncover<6->{\rightarrow 1} \uncover<9->{\rightarrow \textbf{0}} \uncover<10->{\rightarrow \textbf{1}} \uncover<11->{\rightarrow 1} \uncover<12->{\rightarrow \textbf{0}} \uncover<14->{...}\\
+%\ \textbf{0}\uncover<2->{\rightarrow 0} \uncover<3->{\rightarrow 0} \uncover<6->{\rightarrow \textbf{1}} \uncover<9->{\rightarrow 1} \uncover<10->{\rightarrow 1} \uncover<11->{\rightarrow \textbf{0}} \uncover<12->{\rightarrow 0} \uncover<14->{...}\\
+%\ \textbf{0}\uncover<2->{\rightarrow 0} \uncover<3->{\rightarrow \textbf{1}} \uncover<6->{\rightarrow 1} \uncover<9->{\rightarrow 1}\uncover<10->{\rightarrow 1} \uncover<11->{\rightarrow 1} \uncover<12->{\rightarrow 1} \uncover<14->{...}\\
+%\ \textbf{0}\uncover<2->{\rightarrow 0} \uncover<3->{\rightarrow 0} \uncover<6->{\rightarrow 0} \uncover<9->{\rightarrow 0} \uncover<10->{\rightarrow 0} \uncover<11->{\rightarrow 0} \uncover<12->{\rightarrow 0} \uncover<14->{...}\\
+%\end{array}
+%\end{equation}
+%\end{block}
+
+%\begin{block}{}
+
+%\alert{Sortie:} \uncover<4->{1 0 1 0 }\uncover<7->{1 1 1 0 }\uncover<13->{0 0 1 0 }\uncover<14->{...}
+
+%\end{block}
+%\end{frame}
+
+
+
+
+%\begin{frame}{Choix de l'ensemble $\mathcal{M}$}
+% \begin{figure}[!t]
+% \centering
+% \includegraphics[width=3.5in,height=2in]{lesM.png}
+% \DeclareGraphicsExtensions.
+% \caption{Nombre d'itÃ©rations entre deux sorties}
+% \label{Premiers tests Ã©lÃ©mentaires}
+% \end{figure}
+%\end{frame}
+
+
+
+
+%\begin{frame}{Choix de l'ensemble $\mathcal{M}$}
+% \begin{figure}[!t]
+% \centering
+% \includegraphics[width=3.5in,height=2in]{leM.png}
+% \DeclareGraphicsExtensions.
+% \caption{Choix de $\mathcal{M}$}
+% \end{figure}
+%\end{frame}
+
+
+
+
+
+%\frame{
+%\frametitle{RÃ©sultats}
+%\begin{alertblock}{Premiers rÃ©sultats}
+%\begin{enumerate}
+%  \item GÃ©nÃ©rateur chaotique dÃ¨s que le GTPIC de $G_f$ est fortement connexe
+%  \item Toutes les autres propriÃ©tÃ©s de chaos
+%  \item Sortie uniforme si la matrice d'adjacence rÃ©duite du GTPIC est doublement stochastique
+%  \item Les rÃ©sultats aux tests statistiques sont meilleurs (DieHARD, NIST, TestU01)
+%\end{enumerate}
+%\end{alertblock}
+%}
+
+
+
+
+%\begin{frame}{Premiers tests comparatifs}
+% \begin{figure}[!t]
+% \centering
+% \includegraphics[width=3.5in,height=2in]{1.pdf}
+% \DeclareGraphicsExtensions.
+% \caption{Premiers tests Ã©lÃ©mentaires}
+% \label{Premiers tests Ã©lÃ©mentaires}
+% \end{figure}
+%\end{frame}
+
+
+%\begin{frame}{NIST pour les PRNG en entrÃ©e}
+% \begin{figure}[!t]
+% \centering
+% \includegraphics[scale=0.27]{NistSeul.png}
+% \DeclareGraphicsExtensions.
+% \caption{Le NIST pour 3 PRNG}
+% \end{figure}
+%\end{frame}
+
+
+
+%\begin{frame}{NIST pour le Old CI}
+% \begin{figure}[!t]
+% \centering
+% \includegraphics[scale=0.27]{NistAvec.png}
+% \DeclareGraphicsExtensions.
+% \caption{RÃ©sultats du Old CI PRNG}
+% \end{figure}
+%\end{frame}
+
+
+
+%\begin{frame}{DieHard pour les PRNG en entrÃ©e}
+% \begin{figure}[!t]
+% \centering
+% \includegraphics[scale=0.27]{DieHardSeul.png}
+% \DeclareGraphicsExtensions.
+% \caption{DieHard pour 3 PRNG}
+% \end{figure}
+%\end{frame}
+
+
+
+
+%\begin{frame}{DieHard pour le Old CI}
+% \begin{figure}[!t]
+% \centering
+% \includegraphics[scale=0.24]{DieHarda.png}
+% \DeclareGraphicsExtensions.
+% \caption{RÃ©sultats du Old CI PRNG}
+% \end{figure}
+%\end{frame}
+
+
+
+
+%\begin{frame}{TestU01 pour les PRNG en entrÃ©e}
+% \begin{figure}[!t]
+% \centering
+% \includegraphics[scale=0.3]{TestUSeul.png}
+% \DeclareGraphicsExtensions.
+% \caption{TestU01 pour 3 PRNG}
+% \end{figure}
+%\end{frame}
+
+
+
+
+
+
+
+
+%\begin{frame}{TestU01 pour le Old CI}
+% \begin{figure}[!t]
+% \centering
+% \includegraphics[scale=0.25]{TestUAvec.png}
+% \DeclareGraphicsExtensions.
+% \caption{RÃ©sultats du Old CI PRNG}
+% \end{figure}
+%\end{frame}
+
+
+
+%\subsection*{Le New CI PRNG}
+%\frame{
+%  \frametitle{Variantes}
+%    \begin{block}{Quelques variantes du CI PRNG}
+%      \begin{itemize}
+%        \item $New ~CI_f(PRNG_1,PRNG_2)$: Ã©viter de changer deux fois de suite un mÃªme bit entre deux outputs
+%          \begin{itemize}
+%            \item Ne plus compter le nombre d'itÃ©rÃ©es entre deux outputs
+%            \item Mais le nombre de bits Ã  changer
+%          \end{itemize}
+%        \item $Xor CI PRNG$: $S^{n+1}=S^n \oplus PRNG^n$
+%        \item etc.
+%      \end{itemize}
+%    \end{block}
+%}
+
+
+
+
+
+
+%\begin{frame}{La suite $m$ du New CI}
+%Supposons que $x_0 = (0, 0, 0)$. Alors $m_0 \in \llbracket 0, 3 \rrbracket$: on
+%peut changer de 0 Ã  3 bits dans cet Ã©tat pour produire $x_1$.
+%\begin{itemize}
+%  \item Si $m_0 = 0$, alors aucun bit ne changera entre la premiÃ¨re et la
+%  seconde sortie de notre gÃ©nÃ©rateur. Et donc $x_1 = (0, 0, 0)$.
+%  \item Si $m_0 = 1$, alors exactement 1 bit changera, ce qui conduit Ã  trois
+%  valeurs possibles pour $x_1$, Ã  savoir (1, 0, 0), (0, 1, 0) et (0, 0, 1).
+%  \item etc.
+%\end{itemize}
+%\end{frame}
+
+
+
+%\begin{frame}{La suite $m$ du New CI}
+%\begin{equation}
+%\label{Formula}
+%m^n = f(y^n)=
+%\left\{
+%\begin{array}{l}
+%0 \text{   si   }0				\leqslant\frac{y^n}{2^{32}}<\frac{C^0_N}{2^N},\\
+%1 \text{   si   }\frac{C^0_N}{2^N}		\leqslant\frac{y^n}{2^{32}}<\sum_{i=0}^1\frac{C^i_N}{2^N},\\
+%2 \text{   si   }\sum_{i=0}^1\frac{C^i_N}{2^N}	\leqslant\frac{y^n}{2^{32}}<\sum_{i=0}^2\frac{C^i_N}{2^N},\\
+%\vdots~~~~~					~~\vdots~~~		    ~~~~\\
+%N \text{   si   }\sum_{i=0}^{N-1}\frac{C^i_N}{2^N}	\leqslant\frac{y^n}{2^{32}}<1.\\
+%\end{array}
+%\right.
+%\end{equation}
+%\end{frame}
+
+
+
+
+
+%\begin{frame}{StratÃ©gie chaotique}
+%Une suite de marquage controlera la suite du XORshift $b$ ainsi:
+%\begin{itemize}
+%\item si $d^{b^j} \neq 1$, alors $S^k=b^j$, $d^{b^j} = 1$ et $k = k+1$
+%\item si $d^{b^j}=1$, alors $b^j$ est Ã©cartÃ©.
+%\end{itemize}
+%Par exemple, si $b = 142\underline{2}334
+%142\underline{1} \underline{1}\underline{2}\underline{2}34...$ et $m =
+%4241...$, alors $S=1423~34~1423~4...$
+%\end{frame}
+
+
+
+
+
+
+%%\subsection*{Chaotic iterations as pseudo-random generator}
+%% \begin{frame}{CI(XORshift, XORshift) algorithm}
+%% \begin{tiny}
+%% \begin{table}
+%% \centering
+%% \begin{tabular}{|l|}
+%% \hline
+%% ~\textbf{Input}: the internal state $x$ (an array of $\mathsf{N}$ bits)\\
+%% \hline
+%% ~\textbf{Output}: a state $r$ of $\mathsf{N}$ bits \\
+%% \hline
+%% ~\textbf{for} $i=0,\dots,N$ \textbf{do}\\
+%% ~~~~~~ $d_i\leftarrow{0}$;\\
+%% ~\textbf{end for}\\
+%% ~$a\leftarrow{XORshift1(~)}$;\\
+%% ~$m\leftarrow{f(a)}$\;\\
+%% ~$k\leftarrow{m}$\;\\
+%% ~\textbf{for} $i=0,\dots,k$ \textbf{do}\\
+%% ~~~~~~ $b\leftarrow{XORshift2() mod ~ N}$;\\
+%% ~~~~~~ $S\leftarrow{b}$;\\
+%% ~~~~~~~\textbf{if} $d_S=0$ \textbf{then}\\
+%% ~~~~~~~~~~~~ $x_S\leftarrow{ \overline{x_S}}$;\\
+%% ~~~~~~~~~~~~ $d_S\leftarrow{1}$;\\
+%% ~~~~~~~\textbf{end}\\
+%% ~~~~~~~\textbf{else if} $d_S=1$ \textbf{then}\\
+%% ~~~~~~~~~~~~ $k\leftarrow{k+1}$;\\
+%% ~~~~~~~\textbf{end}\\
+%% ~\textbf{end for}\\
+%% ~$r\leftarrow{x}$\;\\
+%% ~\textbf{return} $r$;\\
+%% \hline
+%% 
+%% \end{tabular}
+%% \caption{An arbitrary round of the proposed generator}
+%% \label{Chaotic iteration}
+%% \end{table}
+%% \end{tiny}
+%% 
+%% \end{frame}
+%% 
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+%%\begin{frame}{Exemple du New CI}
+%%\begin{block}{}
+%%\begin{tabular}{llllll}
+%%m:&\uncover<2->{0~} 	&\uncover<4->{4~~}			&\uncover<6->{2 }	&\uncover<8->{2}&\uncover<10->{...}\\
+%%k:&\uncover<2->{0~}	&\uncover<4->{4~~~~~~+1~}		&\uncover<6->{2 }	&\uncover<8->{2~+1}&\uncover<10->{...}\\
+%%b:&\uncover<2->{~~}	&\uncover<4->{1~4~2~\underline{2}~3}	&\uncover<6->{3~4}	&\uncover<8->{1~\underline{1}~~~4}&\uncover<10->{...}\\
+%%S:&\uncover<2->{~~}	&\uncover<4->{1~4~2~~~~3}		&\uncover<6->{3~4}	&\uncover<8->{1~~~~~~4}&\uncover<10->{...}
+%%\end{tabular}
+%%\end{block}
+%% 
+%%\begin{block}{x:}
+%%\begin{equation}
+%%\label{Basic equations}
+%%% \left\{
+%%\begin{array}{r@{\;}l}
+%%\ \textbf{0}\uncover<2->{\rightarrow \textbf{0}}	\uncover<4->{\rightarrow \textbf{1}\rightarrow 1\rightarrow 1\rightarrow \textbf{1}}	\uncover<6->{\rightarrow 1\rightarrow \textbf{1}}		\uncover<8->{\rightarrow \textbf{0}\rightarrow \textbf{0}}	\uncover<10->{...}\\
+%%\ \textbf{1}\uncover<2->{\rightarrow \textbf{1}}	\uncover<4->{\rightarrow 1\rightarrow 1\rightarrow \textbf{0}\rightarrow \textbf{0}}	\uncover<6->{\rightarrow 0\rightarrow \textbf{0}}		\uncover<8->{\rightarrow 0\rightarrow \textbf{0}}				\uncover<10->{...}\\
+%%\ \textbf{0}\uncover<2->{\rightarrow \textbf{0}}	\uncover<4->{\rightarrow 0\rightarrow 0\rightarrow 0\rightarrow \textbf{1}}				\uncover<6->{\rightarrow \textbf{0}\rightarrow \textbf{0}}	\uncover<8->{\rightarrow 0\rightarrow \textbf{0}}				\uncover<10->{...}\\
+%%\ \textbf{0}\uncover<2->{\rightarrow \textbf{0}}	\uncover<4->{\rightarrow 0\rightarrow \textbf{1}\rightarrow 1\rightarrow \textbf{1}}	\uncover<6->{\rightarrow 1\rightarrow \textbf{0}}		\uncover<8->{\rightarrow 0\rightarrow \textbf{1}}				\uncover<10->{...}
+%%\end{array}
+%%% \right.
+%%\end{equation}
+%%\end{block}
+
+%%\begin{block}{}
+
+%%\alert{Sortie:} 0 1 0 0 \uncover<3->{0 1 0 0 }\uncover<5->{1 0 1 1
+%%}\uncover<7->{1 0 0 0 }\uncover<9->{0 0 0 1 }\uncover<10->{...}
+
+%%\end{block}
+
+%%\end{frame}
+
+
+
+
+
+%\begin{frame}{Nouvelle version de $CI_f(PRNG_1,PRNG_2)$}
+% \begin{figure}[!t]
+% \centering
+% \includegraphics[scale=0.25]{newCI.png}
+% \DeclareGraphicsExtensions.
+% \caption{Le NEW CI PRNG}
+% \end{figure}
+%\end{frame}
+
+
+
+%\begin{frame}{NIST pour le New CI}
+% \begin{figure}[!t]
+% \centering
+% \includegraphics[scale=0.27]{NistNew.png}
+% \DeclareGraphicsExtensions.
+% \caption{RÃ©sultats du New CI PRNG (Nist)}
+% \end{figure}
+%\end{frame}
+
+
+
+
+%\begin{frame}{DieHard pour le New CI}
+% \begin{figure}[!t]
+% \centering
+% \includegraphics[scale=0.24]{DieHardNew.png}
+% \DeclareGraphicsExtensions.
+% \caption{RÃ©sultats du New CI PRNG (DieHard)}
+% \end{figure}
+%\end{frame}
+
+
+
+
+
+
+
+%\begin{frame}{TestU01 pour le New CI}
+% \begin{figure}[!t]
+% \centering
+% \includegraphics[scale=0.37]{TestUNew.png}
+% \DeclareGraphicsExtensions.
+% \caption{RÃ©sultats du New CI PRNG (TestU01)}
+% \end{figure}
+%\end{frame}
+
+
+
+
+
+
+
+%%\begin{frame}{Premiers tests comparatifs}
+%%\begin{tiny}
+%%\begin{table}[!t]
+%%\renewcommand{\arraystretch}{1.3}
+%%\caption{Comparaison avec $2 \times 10^5$ bits}
+%%\label{Comparison2}
+%%\centering
+%%  \begin{tabular}{ccccccc}
+%%    \hline
+%%Method & Monobit & Serial & Poker & Runs & Autocorrelation & Time  \\ \hline
+%%Logistic map &0.1280&0.1302&240.2893&26.5667&0.0373&0.965s \\
+%%XORshift &1.7053&2.1466&248.9318&18.0087&-0.5009&0.096s \\
+%%Old CI(Logistic, Logistic) &1.0765&1.0796&258.1069&20.9272&-1.6994&0.389s \\
+%%New CI(XORshift,XORshift) &0.3328&0.7441&262.8173&16.7877&-0.0805&0.197s\\
+%%    \hline
+%%  \end{tabular}
+%%\end{table}
+%%\end{tiny}
+%%\end{frame}
+
+
+
+
+
+
+
+
+%%\frame{
+%%  \frametitle{RÃ©sultats au TestU01}
+%%  \begin{center}
+%%  \begin{tabular}{|c|c|}
+%%  \hline
+%%  PRNG & Ãchecs (sur 516 tests) \\
+%%  \hline
+%%  Suite logistique & 261 \\
+%%  XORshift & 146 \\
+%%  ISAAC & 0 \\
+%%  \hline
+%%  Old CI(Logistic,Logistic) & 138 \\
+%%  Old CI(XORshift,XORshift) & 9 \\
+%%  Old CI(ISAAC,XORshift) & 0 \\
+%%  Old CI(ISAAC,ISAAC) & 0 \\
+%%  \hline
+%%  New CI(Logistic,Logistic) & 0 \\
+%%  New CI(ISAAC,XORshift) & 0 \\
+%%  New CI(ISAAC,ISAAC) & 0 \\
+%%  \hline
+%%  \end{tabular}
+%%  \end{center}
+%%%  \begin{figure}
+%%%  \centering
+%%%  \includegraphics[scale=0.35]{testU010.png}
+%%%  \caption{Score de quelques PRNGs au TestU01}
+%%%  \end{figure}
+%%}
+
+
+
+%%\frame{
+%%  \frametitle{RÃ©sultats}
+%%  \begin{figure}
+%%  \centering
+%%  \includegraphics[scale=0.35]{testU011.png}
+%%  \caption{AmÃ©liorations via le $Old CI(PRNG_1,PRNG_2)$}
+%%  \end{figure}
+%%}
+
+
+
+%%\frame{
+%%  \frametitle{RÃ©sultats}
+%%  \begin{figure}
+%%  \centering
+%%  \includegraphics[scale=0.35]{testU012.png}
+%%  \caption{AmÃ©liorations via le $New CI(PRNG_1,PRNG_2)$}
+%%  \end{figure}
+%%}
+
+
+
+%\frame{
+%  \frametitle{RÃ©sultats}
+%  \begin{figure}
+%  \centering
+%  \includegraphics[scale=0.27]{prngs.png}
+%  \caption{Autres rÃ©sultats}
+%  \end{figure}
+%  }
+
+
+
+%\frame{
+%  \frametitle{RÃ©sultats}
+%  \begin{figure}
+%  \centering
+%  \includegraphics[scale=0.27]{vitesse.png}
+%  \caption{Perte de vitesse}
+%  \end{figure}
+%  }
+
+
+%%\frame{
+%%  \frametitle{A quel prix ?}
+%%  \begin{figure}
+%%  \centering
+%%  \includegraphics[scale=0.35]{rapide.png}
+%%  \caption{DÃ©gradation de la vitesse}
+%%  \end{figure}
+%%}
+
+
+
+
+
+
+%\subsection*{Une famille pour le Old CI}
+
+
+
+%\frame{
+%  \frametitle{DÃ©finition d'une famille de Old CI}
+%\begin{block}{La matrice associÃ©e Ã  $f$}
+%Matrice de taille $N\times 2^N$ dont l'Ã©lÃ©ment $(p,q)$ est 
+%l'entier ayant la dÃ©compistion binaire:
+%$$q_N, \hdots, q_{N-p}, f(q)_{N-p+1}, q_{N-p+2}, \hdots, q_1$$
+%avec $q_i$: $i-$iÃ¨me chiffre en base 2 de $q$.
+%\end{block}
+%  
+
+%\begin{block}{Vecteur des images}
+%Le vecteur des images de $f$ est:
+%$$\mathcal{F}(f)=(f(0), f(1), \hdots, f(2^N-1)) \in \llbracket 0, 2^N-1 \rrbracket^{2^N}$$
+%\end{block}
+%}
+
+
+
+
+%\frame{
+%  \frametitle{Exemple de matrice associÃ©e}
+%  \begin{figure}
+%  \centering
+%  \includegraphics[scale=0.27]{mappingMatrix.png}
+%  \caption{Matrice associÃ©e et vecteur des images pour $f_0$}
+%  \end{figure}
+%  
+%}
+
+
+
+%\frame{
+%  \frametitle{Une rÃ¨gle pour le Old CI PRNG}
+%  \begin{itemize}
+%    \item Supposons que $\mathcal{F}(f)=(f(0), f(1), \hdots, f(2^N-1)) \in \llbracket 0, 2^N-1 \rrbracket^{2^N}$, avec $Old~ CI_f$ Ã©quilibrÃ©
+%    \item Si on veut changer $\mathcal{F}(f)_j$ en $C$, alors il faut aussi que $\mathcal{F}(f)_{2^N-C}=2^N-j$
+%  \end{itemize}
+%  
+%}
+
+
+
+
+%\frame{
+%  \frametitle{Exemple de fonctions pour le Old CI}
+%  \begin{figure}
+%  \centering
+%  \includegraphics[scale=0.27]{mappingF0.png}
+%  \caption{CrÃ©ation de nouvelles fonctions Ã©quilibrÃ©es}
+%  \end{figure}
+%  }
+
+
+%\frame{
+%  \frametitle{Un thÃ©orÃ¨me pour l'Ã©quilibrage}
+%\begin{alertblock}{ThÃ©orÃ¨me}
+%Soit $f: \mathds{B}^{n} \rightarrow \mathds{B}^{n}$, $\Gamma(f)$ son graphe d'itÃ©ration, 
+%$\check{M}$ sa matrice d'adjacence.
+
+%Si $\Gamma(f)$ est fortement connexe, alors la sortie produite par le Old CI PRNG
+%suit une loi qui tend vers l'uniforme rÃ©partition si et seulement si $M$ est 
+%doublement stochastique.
+%\end{alertblock}
+%}
+
+
+
+
+%\frame{
+%  \frametitle{D'autres Old CI chaotiques}
+%  \begin{block}{Pour obtenir d'autres Old CI chaotiques}
+%  \begin{enumerate}
+%    \item Partir du graphe de tous les possibles de $f_0$
+%    \item Tant que le taux ne suppression n'est pas atteint:
+%    \begin{itemize}
+%      \item tirer une arÃªte au sort
+%      \item la supprimer si le graphe reste fortement connexe (algorithme de Tarjan)
+%    \end{itemize}
+%  \end{enumerate}
+%  (ProblÃ¨me avec les graphes isomorphes)
+%  \end{block}
+%}
+
+
+%\frame{
+%  \frametitle{Exemple de fonctions pour le Old CI}
+%  \begin{figure}
+%  \centering
+%  \includegraphics[scale=0.27]{SCC.png}
+%  \caption{CrÃ©ation de nouvelles fonctions au gÃ©nÃ©rateur chaotique}
+%  \end{figure}
+%  
+%}
+
+
+
+%\frame{
+%  \frametitle{Condition suffisante de chaoticitÃ©}
+%\begin{alertblock}{ThÃ©orÃ¨me}
+%Soit $f$ une fonction de $\mathds{B}^n$ dans lui-mÃªme telle que:
+%\begin{enumerate}
+%\item 
+%Le graphe de connexion $G(f)$ n'a pas de cycle de longueur au moins 2;
+%\item 
+%Chaque arÃªte de $G(f)$ ayant une boucle positive a aussi une boucle nÃ©gative;
+%\item
+%Chaque arÃªte de $G(f)$ est joignable Ã  partir d'un noeud ayant une boucle nÃ©gative.
+%\end{enumerate}
+%Alors $\Gamma(f)$ est fortement connexe. 
+%\end{alertblock}
+%}
+
+
+
+%%\begin{theorem}
+%%  Let $f: \mathds{B}^{n} \rightarrow \mathds{B}^{n}$, $\Gamma(f)$ its
+%%  iteration graph, $\check{M}$ its adjacency
+%%  matrix and $M$ a $n\times n$ matrix defined as in the previous lemma.
+%%  If $\Gamma(f)$ is SCC then 
+%%  the output of the PRNG detailed in Algorithm~\ref{CI Algorithm} follows 
+%%  a law that tends to the uniform distribution 
+%%  if and only if $M$ is a double stochastic matrix.
+%%\end{theorem} 
+
+
+%\subsection*{PRNG cryptographiquement sÃ»r}
+%    
+
+%\frame{
+%\frametitle{Les PRNG cryptographiquement sÃ»rs}
+%\begin{block}{DÃ©finition: GÃ©nÃ©rateur $G$ \emph{cryptographiquement sÃ»r}}
+%%Pour tout 
+%%algorithme probabiliste polynomial en temps $\mathcal{D}$, pour tout
+%%polynome $\mathfrak{p}>0$, et pour tout $n$ suffisamment large,
+%$$\left| \mathrm{Pr}[\mathcal{D}(\mathcal{G}(\mathfrak{U}_n))=1]-Pr[\mathcal{D}(\mathfrak{U}_{\ell_\mathcal{G}(n)})=1]\right|< \frac{1}{\mathfrak{p}(n)},$$
+%%oÃ¹ $\mathfrak{U}_r$ est la loi de probabilitÃ© uniforme sur $\{0,1\}^r$ et les
+%%probabilitÃ©s sont prises sur $\mathfrak{U}_n$, $\mathfrak{U}_{\ell_G(n)}$ de la mÃªme maniÃ¨re
+%%que pour le lancer d'une piÃ¨ce de monnaie dans $\mathcal{D}$. 
+%\end{block}
+%}
+
+
+
+%\subsection*{Version GPU}
+
+%\frame{
+%\frametitle{Derniers RÃ©sultats}
+%\begin{alertblock}{Nos derniers rÃ©sultats}
+%\begin{enumerate}
+%  \item Si le premier PRNG en entrÃ©e est polynomialement indistinguable d'une suite alÃ©atoire, alors notre PRNG l'est aussi
+%  \item Implantation sur GPU $\Rightarrow$ 20 milliards de nombres (32 bits) par seconde sur un PC
+%  \item Utilisation de BBS $\Rightarrow$ 1 milliards de nombres sÃ»rs par seconde
+%  \item Version chaotique du cryptosystÃ¨me asymÃ©trique probabiliste de Blum-Goldwasser
+%  \item Mixage avec dispositif optique (Larger, OPTO)
+%\end{enumerate}
+%\end{alertblock}
+%}
+
+
+
+
+
+%%\frame{
+%%  \frametitle{Notre gÃ©nÃ©rateur GPU}
+%%  \begin{figure}
+%%  \centering
+%%  \includegraphics[scale=0.3]{gpu.png}
+%%%  \caption{Version GPU de notre gÃ©nÃ©rateur}
+%%  \end{figure}
+%%}
+
+
+
+
+%%\frame{
+%%  \frametitle{Notre gÃ©nÃ©rateur GPU}
+%%  \begin{figure}
+%%  \centering
+%%  \includegraphics[scale=0.25]{bbs.png}
+%% % \caption{Version GPU de notre gÃ©nÃ©rateur, avec bbs}
+%%  \end{figure}
+%%}
+
+
+
+%\frame{
+%  \frametitle{Notre gÃ©nÃ©rateur GPU}
+%  \begin{tabular}{cc}
+%  \includegraphics[scale=0.3]{gpu.png} & \includegraphics[scale=0.275]{bbs.png}
+%  \end{tabular}
+%}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%\section{Nouvelles pistes}
+%%\subsection*{PRNGs}
+%\begin{frame}{}
+%% 'transition': Crossfade,
+%  \begin{center}
+%   \Huge{Nouvelles pistes}
+
+%\medskip
+%   %\huge{soulevÃ©s par l'approche}
+%  \end{center}
+%\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+
+
+
+
+%\frame{
+% \frametitle{Le gÃ©nÃ©rateur optique}
+% \begin{block}{CÃ´tÃ© OPTO}
+%  \begin{figure}
+%  \centering
+%  \includegraphics[scale=0.5]{setup_opto_RNG.eps}
+%   \caption{GÃ©nÃ©rateur optique (laser chaotique)}
+%  \end{figure}
+%  \end{block}
+%}
+
+
+
+
+
+
+
+
+
+
+
+%\frame{
+% \frametitle{Le gÃ©nÃ©rateur mixÃ©}
+% \begin{block}{CÃ´tÃ© DISC}
+%  \begin{figure}
+%  \centering
+%  \includegraphics[scale=0.5]{improve.eps}
+%   \caption{Mixage analogique-numÃ©rique}
+%  \end{figure}
+%  \end{block}
+%}
+
+
+
+
+
+%\frame{
+% \frametitle{Le gÃ©nÃ©rateur mixÃ©}
+% \begin{block}{AmÃ©liorations (NIST)}
+%  \begin{figure}
+%  \centering
+%  \includegraphics[scale=0.35]{NistLaurent.png}
+%   \caption{RÃ©sultat au NIST}
+%  \end{figure}
+%  \end{block}
+%}
+
+
+
+
+
+%\frame{
+% \frametitle{Le gÃ©nÃ©rateur mixÃ©}
+% \begin{block}{AmÃ©liorations (DieHARD)}
+%  \begin{figure}
+%  \centering
+%  \includegraphics[scale=0.25]{DieHardLaurent.png}
+%   \caption{RÃ©sultat au DieHARD}
+%  \end{figure}
+%  \end{block}
+%}
+
+
+
+%\frame{
+% \frametitle{Le gÃ©nÃ©rateur mixÃ©}
+% \begin{block}{CÃ´tÃ© DISC}
+%  \begin{figure}
+%  \centering
+%  \includegraphics[scale=0.35]{method.eps}
+%   \caption{Premier PRNG mixÃ© rÃ©alisÃ©}
+
+%  \end{figure}
+%  \end{block}
+%}
+
+
+%\frame{
+% \frametitle{Premiers rÃ©sultats}
+%  \begin{tabular}{|l||c|c|c|c|c|}
+%    \hline
+%\textbf{Tests} {\textbf{$n$}}&1 &10&20&30&40 \\ \hline\hline
+%NIST suite & 0/15 &14/15 & 15/15 & 15/15 & 15/15\\ \hline
+%DieHARD suite &1/18 &11/18 & 14/18 &18/18&18/18\\ \hline
+%  \end{tabular}
+%}
+
+
+%\frame{
+% \frametitle{Le gÃ©nÃ©rateur mixÃ©}
+% \begin{block}{CÃ´tÃ© DISC}
+%  \begin{figure}
+%  \centering
+%  \includegraphics[scale=0.25]{paralel.png}
+%   \caption{DeuxiÃ¨me PRNG mixÃ© rÃ©alisÃ©}
+%  \end{figure}
+%  \end{block}
+%}
+
+
+%\frame{
+%  \frametitle{Une piste ?}
+%  $$X^{mn+1} = X^{mn} \oplus O^{mn} \oplus C^m$$
+%}
+
+
+
+
+
+
+
+
+
+%\begin{frame}{}
+% \begin{center}
+% \huge{Merci pour votre attention}
+% \end{center}
+%\end{frame}
+
+
+
+
+
+
+
+
+%%\frame{
+%%% 'transition': Crossfade,
+%% \frametitle{Une menace en guise d'illustration}
+%% \begin{block}{Les attaques par canal auxiliaire}
+%% \begin{enumerate}
+%%\item Certains processeurs peuvent laisser fuire de l'information. \newline $\Rightarrow$ En 2006 [Acimez07], 508 bits d'une clÃ© d'authentification sur 512.  
+%%\item Variation de tension appliquÃ©e au processeur [Pellegrini10]\newline $\Rightarrow$ \'Emission d'une signature (RSA 1024) corrompue. 
+%%\item Mesure du temps de dÃ©chiffrement [Kocher95] \newline $\Rightarrow$ Obtention de la clÃ© de dÃ©chiffrement.
+%%\item Optimisations appliquÃ©es au thÃ©orÃ¨me des restes chinois [Brumley03] \newline $\Rightarrow$ Factorisation RSA trouvÃ©e.
+%%\end{enumerate}
+%%\end{block}
+%%}
+
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+%%\frame{
+%%% 'transition': Crossfade,
+%%  \frametitle{Une menace en guise d'illustration}
+%%  \begin{block}{Les attaques par canal auxiliaire}
+%%  \begin{itemize}
+%%    \item Failles matÃ©rielles ou logicielles
+%%    \item Une partie du secret
+%%    \item Algorithmes prouvÃ©s sÃ»rs
+%%  \end{itemize}
+%%  \end{block}
+%%  
+%%  \vspace{0.25cm}
+%%  \uncover<2->{
+%%  \begin{exampleblock}{Tentatives de solution}
+%%  \begin{itemize}
+%%    \item Ne plus rÃ©pondre au cas par cas
+%%    \item Une sÃ©curitÃ© complÃ©mentaire ?
+%%    \item Pourquoi ne pas utiliser des programmes imprÃ©dictibles ?
+%%  \end{itemize}
+%%  \end{exampleblock}
+%%}
+%%}
+
+
+
+
+
+
+
+
+%%\frame{
+%% \frametitle{Nos contributions}
+%%\begin{block}{Nos contributions}
+%%\begin{itemize}
+%%\item Construire des machines, des programmes imprÃ©visibles
+%%\item Etudier des algorithmes existants sous d'autres aspects (comparaison, autres menaces ?)
+%%\item Rajouter des propriÃ©tÃ©s (topologiques) Ã  des outils prÃ©existants, \emph{sans perte de sÃ©curitÃ©}
+%% \end{itemize}
+%%\end{block}
+%%}
+
+
+
+
+
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%\section*{ProblÃ¨mes}
+%\begin{frame}{}
+%% 'transition': Crossfade,
+%  \begin{center}
+%   \Huge{ProblÃ¨mes}
+
+%\medskip
+%   \huge{soulevÃ©s par l'approche}
+%  \end{center}
+%\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+
+
+
+
+%% %%%%%%%%%%%%% 16. De la relativitÃ© du chaos %%%%%%%%%%%%%%%
+%\subsection*{Tout est relatif (est-ce encore vrai ?)}
+
+%% \frame{
+%%   \frametitle{ProblÃ¨me soulevÃ© par l'approche}
+%%   \begin{block}{Quels problÃ¨mes pose cette approche ?}
+%%   \begin{itemize}
+%%   \item RÃ´le prÃ©pondÃ©rant de la topologie
+%%   \item De sa finesse dÃ©pendent les propriÃ©tÃ©s de dÃ©sordre
+%%   \item Comment bien la choisir ?
+%%   \end{itemize}
+%%   $\Rightarrow$ Se ramener Ã  la topologie de l'ordre sur $\mathds{R}$
+%%   \end{block}
+%% }
+
+
+%\frame{
+% \frametitle{De l'importance de la topologie}
+%%\begin{block}{Les questions qui se posent}
+%%\begin{enumerate}
+%%\item Si un systÃ¨me $(\mathcal{X},f)$ est chaotique, et pour quelle topologie.
+%%\item Si un systÃ¨me $(\mathcal{X},f)$ est plus chaotique qu'un systÃ¨me $(\mathcal{Y},g)$.
+%%\end{enumerate}
+%%\end{block}
+
+%%\vspace{0.5cm}
+%%\uncover<2>{
+%\begin{exampleblock}{ProblÃ¨mes soulevÃ©s}
+%\begin{enumerate}
+%\item Le dÃ©sordre dÃ©pend de la topologie (?)
+%\item Comparaison de deux systÃ¨mes:
+%\begin{itemize}
+%\item Les ensembles $\mathcal{X}$ et $\mathcal{Y}$ ne sont pas forcÃ©ment les mÃªmes.
+%\item Les topologies ne sont pas forcÃ©ment les mÃªmes.
+%\item Sont-elles comparables ? Et quelles consÃ©quences ?
+%\end{itemize}
+%\end{enumerate}
+%\end{exampleblock}
+%%}
+%}
+
+
+
+%\frame{
+% \frametitle{Mon dÃ©sordre n'est pas le tien}
+%   \begin{exampleblock}{ThÃ©orÃ¨me: Impact de la finesse de la topologie}
+%   Soient $\tau, \tau'$ deux topologies sur $\mathcal{X}$ telles que $\tau \subset \tau'$.
+
+%Si $(\mathcal{X}_{\tau'},f)$ satisfait Devaney, alors $(\mathcal{X}_\tau,f)$ aussi.
+%   \end{exampleblock}
+%}
+
+%\frame{
+% \frametitle{Mon dÃ©sordre n'est pas le tien}    
+%   \begin{exampleblock}{Un systÃ¨me peut toujours Ãªtre chaotique}
+%   Soit $\mathcal{X}$ un ensemble non vide, et $f: \mathcal{X} \to \mathcal{X}$ une application possÃ©dant au moins un point fixe.
+%Alors $f$ est $\tau_0-$chaotique, oÃ¹ $\tau_0$ est la topologie grossiÃ¨re sur $\mathcal{X}$.
+%   \end{exampleblock}
+%   
+%   \vspace{0.5cm}
+%   
+%     \begin{exampleblock}{Un systÃ¨me peut toujours ne jamais Ãªtre chaotique}
+%Soit $\mathcal{X}$ un ensemble, et $f: \mathcal{X} \to \mathcal{X}$ une application.
+%Si $\mathcal{X}$ est infini, alors $\left( \mathcal{X}_{\tau_\infty}, f\right)$ n'est pas chaotique selon Devaney, oÃ¹ $\tau_\infty$ dÃ©signe la topologie discrÃ¨te.
+%   \end{exampleblock}
+%}
+
+
+
+
+
+%\frame{
+% \frametitle{RÃ©flexions autour d'un dÃ©sordre absolu}
+%  \begin{block}{Reformulation des problÃ¨mes}
+%    \begin{itemize}
+%      \item $(\mathcal{X},f)$ peut ou non Ãªtre chaotique, suivant la richesse de la topologie.
+%      \item L'ensemble des topologies sur $\mathcal{X}$, muni de la relation Â« Ãªtre plus fine que Â» est un espace rÃ©ticulÃ©.
+%    \end{itemize}
+%  \end{block}
+%  
+%  \vspace{0.4cm}
+%  
+% \begin{block}{Quelques pistes}
+%   \begin{enumerate}
+%     \item La plus fine topologie rendant une fonction imprÃ©dictible
+%     \item \^Etre imprÃ©dictible, c'est l'Ãªtre pour la topologie de l'ordre.
+%       \begin{itemize}
+%         \item Approche lÃ©gitime (mais, pour quel ordre ?)
+%         \item Peut conduire Ã  se ramener Ã  $\mathds{R}$
+%       \end{itemize}
+%   \end{enumerate}
+% \end{block}
+%}
+
+
+%%%%%%%%%%%%%%% 17. Une semi-conjugaison topologique %%%%%%%%
+%%%%%%%%%% ou comment passer de X Ã  un intervalle rÃ©el %%%%%%
+%\subsection*{Une semi-conjugaison topologique}
+
+
+
+%\frame{
+%  \frametitle{Une semi-conjugaison topologique}
+%  
+%  
+%\begin{exampleblock}{Une semi-conjugaison topologique}
+%IC $G_{f_0}$ sur $\mathcal{X}$ = IC $g$ sur $\mathds{R}$:
+%\begin{equation*}
+%\begin{CD}
+%\left(~\mathcal{S}_{10} \times\mathds{B}^{10}, d~\right) @>G_{f_0}>> \left(~\mathcal{S}_{10} \times\mathds{B}^{10}, d~\right)\\
+%    @V{\varphi}VV                    @VV{\varphi}V\\
+%\left( ~\big[ 0, 2^{10} \big[, D~\right)  @>>g> \left(~\big[ 0, 2^{10} \big[, D~\right)
+%\end{CD}
+%\end{equation*}
+%\begin{enumerate}
+%\item Prendre la premiÃ¨re dÃ©cimale $d$ de $x \in \big[ 0, 2^{10} \big[$
+%\item Nier le bit numÃ©ro $d$ de $E(x)$
+%\item Supprimer $d$
+%\end{enumerate}
+%\end{exampleblock}
+%}
+
+
+
+
+%\frame{
+%  \frametitle{Comparaison des distances}
+
+%\begin{exampleblock}{Comparaison de distances}
+%$D$ est plus fine que la distance euclidienne.
+%\end{exampleblock}
+
+%\begin{figure}[t]
+%\begin{center}
+%  \subfigure[Application $x \to dist(x;1,234)$.]{\includegraphics[scale=.25]{17.Semi_conjugaison_topologique/distances/DvsEuclidien.pdf}}\quad
+%  \subfigure[Application $x \to dist(x;3) $.]{\includegraphics[scale=.25]{17.Semi_conjugaison_topologique/distances/DvsEuclidien2.pdf}}
+%\end{center}
+%\caption{Comparaison des distances $D$ et euclidienne.}
+%\label{fig:comparaison de distances}
+%\end{figure}
+%}
+
+
+
+
+
+
+
+
+%\frame{
+% \frametitle{\'Etude des ICs sur $\mathds{R}$}
+% \begin{exampleblock}{Analyse des itÃ©rations chaotiques rÃ©elles}
+%Les itÃ©rations chaotiques $g$ dÃ©finies sur $\mathds{R}$ sont:
+%\begin{itemize}
+%\item Infiniment dÃ©rivables sur $\big[ 0, 2^{10} \big[$, sauf aux 10241 points de l'ensemble $I$ dÃ©fini par $\left\{ \dfrac{n}{10} ~\big/~ n \in \llbracket 0;2^{10}\times 10\rrbracket \right\}$.
+%\item Affine, de pente 10, sur chaque sous-intervalle.
+%\end{itemize}
+%\end{exampleblock}
+%}
+
+
+
+%%\frame{
+%%  \frametitle{Exemples de fonctions chaotiques}
+%%\begin{figure}[t]
+%%\begin{center}
+%%  \subfigure[Doublement de l'angle.]{\includegraphics[scale=.16]{17.Semi_conjugaison_topologique/fonctions/doublement.pdf}}\quad
+%%  \subfigure[Fonction logistique.]{\includegraphics[scale=.16]{17.Semi_conjugaison_topologique/fonctions/logistique.pdf}}\quad
+%%  \subfigure[Fonction tente.]{\includegraphics[scale=.16]{17.Semi_conjugaison_topologique/fonctions/tente.pdf}}
+%%\end{center}
+%%\caption{Exemples de fonctions chaotiques.}
+%%\end{figure}
+%%}
+
+
+
+
+
+%\frame{
+%  \frametitle{Les itÃ©rations chaotiques $G_{f_0}$ sur $\mathds{R}$}
+%\begin{figure}[t]
+%\begin{center}
+%%  \subfigure[Sur (0,9 ; 1).]{\includegraphics[scale=.16]{17.Semi_conjugaison_topologique/fonctions/ICs09a1.pdf}}\quad
+%  \subfigure[Sur (0,7 ; 1).]{\includegraphics[scale=.16]{17.Semi_conjugaison_topologique/fonctions/ICs07a95.pdf}}\quad
+%  \subfigure[Sur (0 ; 1).]{\includegraphics[scale=.19]{17.Semi_conjugaison_topologique/fonctions/ICs0a1.pdf}}\quad
+%    \subfigure[Sur (510 ; 514).]{\includegraphics[scale=.19]{17.Semi_conjugaison_topologique/fonctions/ICs510a514.pdf}}\quad
+%  \subfigure[Sur (1000 ; 1008).]{\includegraphics[scale=.19]{17.Semi_conjugaison_topologique/fonctions/ICs1000a1008.pdf}}
+%\end{center}
+%\caption{Les itÃ©rations chaotiques.}
+%\end{figure}
+%}
+
+
+
+
+%\frame{
+%  \frametitle{Les itÃ©rations chaotiques sur $\mathds{R}$}
+%\begin{figure}[t]
+%\begin{center}
+%  \subfigure[Sur (510 ; 514).]{\includegraphics[scale=.16]{17.Semi_conjugaison_topologique/fonctions/ICs510a514.pdf}}\quad
+%  \subfigure[Sur (1000 ; 1008).]{\includegraphics[scale=.16]{17.Semi_conjugaison_topologique/fonctions/ICs1000a1008.pdf}}\quad
+%  \subfigure[Sur (40 ; 70).]{\includegraphics[scale=.16]{17.Semi_conjugaison_topologique/fonctions/ICs40a70.pdf}}
+%\end{center}
+%\caption{Les itÃ©rations chaotiques.}
+%\end{figure}
+%}
+
+
+
+
+
+
+% \frame{
+%   \frametitle{Chaos des IC $G_{f_0}$ sur $\mathds{R}$}
+%   \begin{exampleblock}{Chaos de Devaney sur $\mathds{R}$}
+% Les IC sur $\mathds{R}$ sont chaotiques selon Devaney, quand $\mathds{R}$ a sa topologie usuelle.
+% \end{exampleblock}
+
+% \vspace{0.5cm}
+
+%   \begin{exampleblock}{Exposant de Lyapunov}
+% %$\forall x^0 \in \mathcal{L}$, l'exposant de Lyapunov des itÃ©rations chaotiques ayant $x^0$ pour condition initiale vaut 
+% $$\forall x^0 \in \mathcal{L}, \lambda(x^0) = \displaystyle{\lim_{n \to +\infty} \dfrac{1}{n} \sum_{i=1}^n \ln \left| ~g'\left(x^{i-1}\right)\right|} = \ln (10).$$
+% \end{exampleblock}
+% }
+
+
+
+
+
+
+
+
+
+
+
+
+%\frame{
+%  \frametitle{SystÃ¨mes itÃ©ratifs et suites rÃ©currentes}  
+%  \begin{alertblock}{Les systÃ¨mes itÃ©ratifs sont des suites rÃ©currentes}
+%  On pose $F:\mathcal{X}^\mathds{N} \longleftrightarrow\mathcal{X}^\mathds{N}$, qui Ã  la suite $(x^k)_{k \in \mathds{N}}$ associe $\left(x^0, f^0(x^0), f^1(x^0,x^1), f^2(x^0,x^1,x^0),\hdots\right)$. Alors le systÃ¨me
+%    $$\left\{
+%  \begin{array}{l}
+%    X^0 = (x^0,0,0, \hdots) \in \mathcal{X}^\mathds{N}\\
+%    X^{n+1} = F(X^n)
+%  \end{array}
+%  \right.$$
+%  tend vers la suite $(x^0,x^1,x^2,\hdots)$.
+%  \end{alertblock}
+%  \uncover<2->{
+%  Etudions un cas particulier : les Â« ItÃ©rations chaotiques Â»}
+%}
+
+\section{Conclusion}
+
+
+\bibliographystyle{plain}
+\bibliography{mabase}
 
 \end{document}
