avancées

[review_prng.git] / review_prng.tex

\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}