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



\title{A Review of Chaotic Iteration Based Pseudorandom Number Generators}
\author{Jacques M. Bahi, Jean-Fran\c cois Couchot, Raphaël Couturier, and Christophe Guyeux~\thanks{Authors in alphabetic order}}



\begin{document}

\maketitle

\begin{abstract}

\end{abstract}


\section{Introduction}


\section{Topologycal 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 litterature, 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
generatized 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}
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{Topological Properties of 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 $\Rightarrow 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.

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 formulated as follows.

%\frame{
%\frametitle{Stabilité et expansivité}
%   \begin{block}{Définitions de la sensibilité}
%     \begin{itemize}
%       \item $(\mathcal{X},f)$ est \emph{instable} si tous ses points le sont: $\forall x \in \mathcal{X},$ $\exists \varepsilon >0,$ $\forall \delta > 0,$ $\exists y \in \mathcal{X},$ $\exists n \in \mathbb{N},$ $d(x,y)<\delta$  et $d(f^{(n)}(x),f^{(n)}(y)) \geqslant \varepsilon$
%       \item $(\mathcal{X},f)$ est \emph{expansif} si
%$\exists \varepsilon >0,$ $\forall x \neq y,$ $\exists n \in \mathbb{N},$ $d(f^{(n)}(x),f^{(n)}(y)) \geqslant \varepsilon$
%     \end{itemize}
%   \end{block}
%}

%%\frame{
%%  \frametitle{Des systèmes imprévisibles}
%%    \begin{block}{Définitions des systèmes dynamiques désordonnés}
%%    \begin{itemize}
%%      \item \emph{Devaney:} $(\mathcal{X},f)$ est sensible aux conditions initiales, régulier et transitif
%%       \item \emph{Wiggins:} $(\mathcal{X},f)$ est transitif et sensible aux conditions initiales
%%       \item \emph{Knudsen:} $(\mathcal{X},f)$ a une orbite dense et s'il est sensible aux conditions initiales
%%       \item \emph{expansif:} $(\mathcal{X},f)$ est transitif, régulier et expansif
%%    \end{itemize}
%%    \end{block}
%%}



%\subsection*{Autres approches}


%\frame{
%  \frametitle{Selon Li et Yorke}
%    \begin{block}{Définitions}
%    \begin{description}
%\item[Couple de Li-Yorke.] $(x,y)$ en est un quand: $\limsup_{n \rightarrow +\infty} d(f^{(n)}(x), f^{(n)}(y))>0$ et $\liminf_{n \rightarrow +\infty} d(f^{(n)}(x), f^{(n)}(y))=0.$

%\item[Ensemble brouillé.] $B \subset \mathcal{X}$ en est un si tout couple de points distincts de $B$ est de Li-Yorke.

%\item[Systèmes de Li-Yorke.] $\mathcal{X}$ est compact et contient un ensemble brouillé indénombrable.
%\end{description}
%\end{block}
%}






%\frame{
% \frametitle{Approche entropie topologique}
%   \begin{block}{Entropie topologique}
%   \begin{itemize}
%   \item $x,y \in \mathcal{X}$ sont ~$\varepsilon-$\emph{séparés en temps $n$} s'il existe $k \leqslant n$ tel que $d\left(f^{(k)}(x),f^{(k)}(y)\right)>\varepsilon$.
%   \item Les ensembles $(n,\varepsilon)-$séparé sont des ensembles de points qui seront tous $\varepsilon-$séparés en temps $n$
%   \item $s_n(\varepsilon,Y)$: cardinal maximal d'un ensemble $(n,\varepsilon)-$séparé $$h_{top}(\mathcal{X},f)  = \displaystyle{\lim_{\varepsilon \rightarrow 0} \Big[ \limsup_{n \rightarrow +\infty} \dfrac{1}{n} \log s_n(\varepsilon,\mathcal{X})\Big]}$$
%   \end{itemize}
%   \end{block}
%}




%\frame{
% \frametitle{Exposant de Lyapunov}
%\begin{block}{L'exposant de Lyapunov}
%$$\lambda(x^0) = \displaystyle{\lim_{n \to +\infty} \dfrac{1}{n} \sum_{i=1}^n \ln \left| ~f'\left(x^{i-1}\right)\right|}$$
%Il doit être positif pour multiplier les erreurs
%\end{block}
%}





%\subsection*{Etude des systèmes itératifs}

%%\frame{
%%  \frametitle{IC et propriété de Devaney}
%%\begin{alertblock}{Théorème}
%%$G_{f_0}$ est régulier et transitif (Devaney). 

%%Sa sensibilité est $\geqslant \mathsf{N}-1$.
%%\end{alertblock}

%%\uncover<2->{
%% \begin{exampleblock}{Question}
%% $f_0$ est-elle la seule fonction dont le système itératif vérifie la condition de Devaney ?
%% \end{exampleblock}
%% 
%% \vspace{0.5cm}

%%Pour y répondre, nous avons utilisé le graphe de tous les possibles par itérations chaotiques : le GTPIC.}
%%}




%%\frame{
%%  \frametitle{Nombre de fonctions imprévisibles}
%%  \begin{alertblock}{Caractérisation des IC imprévisibles selon Devaney}
%%$G_f$ vérifie l'hypothèse de Devaney $\Leftrightarrow$ Son graphe des possibles est fortement connexe.

%%$\Rightarrow$ Il y a $\left(2^\mathsf{N}\right)^{2^\mathsf{N}}$ IC chaotiques.
%%\end{alertblock}
%%}







%\frame{
%  \frametitle{Etude topologique}
%    \begin{exampleblock}{Etude topologique des ICs}
%      \begin{itemize}
%        \item $\forall f \in \mathcal{C}$, $Per\left(G_f\right)$ est infini dénombrable, $G_f$ est fortement transitive,  est chaotique selon Knudsen, 
%        \item $\left(\mathcal{X}, G_{f_0}\right)$ est topologiquement mélangeant, expansif (constante 1), est chaotique selon Li-Yorke, a une entropie topologique infinie, un exposant de Lyapunov de $ln(\mathsf{N})$
%        \item Indécomposabilité, instabilité, chaos de Wiggins, de la multiplicité des périodes...
%      \end{itemize}
%    \end{exampleblock}
%}







%\frame{
% \frametitle{Graphe de tous les possibles par IC}
%  \begin{center}
%   \includegraphics[scale=0.55]{14.Caracterisation_des_IC_chaotiques_selon_Devaney/grapheTPICver2.pdf}
%  \end{center}
%}



















%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\section*{Topologie des programmes}
%\frame{
%% 'transition': Crossfade,
% \begin{center}
%   \Huge{Topologie des programmes}
%   
%  \end{center}
%}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%%\frame{
%%  \frametitle{Premières questions}
%%  \begin{exampleblock}{Le chaos dans mon PC ?}
%%  Le désordre, l'imprévisibilité (vrai, sans perte) sont-ils possibles sur un ordinateur ?
%%\begin{itemize}
%%      \item Il n'y a pas de réels sur mon PC
%%      \item Toute machine ayant un nombre fini d'états finit par entrer dans un cycle.
%%\end{itemize}
%%  \end{exampleblock}
%%}









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