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

diff --git a/review_prng.tex b/review_prng.tex
index c6ab2f1..158f90b 100644
--- a/review_prng.tex
+++ b/review_prng.tex
@@ -1,6 +1,1987 @@
 \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.
+
+\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 compiliant with the definition above, 
+
+On appelle \emph{itérations parallèles} \index{itérations!parallèles} de $f$ sur 
+$\mathcal{X}$ toute itération synchrone $\Sigma = (\mathcal{X}, \mathcal{F})$ 
+telle que la suite $\mathcal{F}$ est constante égale à $f: \X \to \X$.
+On parle encore d'itérations parallèles $\left(\mathcal{X},f\right)$.
+
+
+
+Finally, iterative systems in chaotic mode, simply called chaotic iterations,
+ are defined as follows.
+ 
+
+\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} 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 questionning has led to a first necessary condition of non convergence.
+
+\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,
+\item or $S$ is not pseudo-periodic.
+\end{itemize}
+\end{proposition}
+
+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 rewriten as simple discrete dynamical systems, as follows.
+
+
+
+
+
+
+%\frame{
+%\frametitle{Présentation du problème}
+
+%\begin{tabular}{c||c}
+%MATHS DISCRÈTES & TOPOLOGIE MATHÉMATIQUE \tabularnewline
+%\hline
+%\multirow{2}{5cm}{\centering $f: \mathds{B}^\mathsf{N} \to \mathds{B}^\mathsf{N}$} & $(\mathcal{X},\tau)$ espace topologique\\
+%& $f : \mathcal{X} \to \mathcal{X}$ continue pour $\tau$\\
+%\hline
+%$S \in \mathcal{S} = \llbracket 1,\mathsf{N}\rrbracket^\mathds{N}$ & \multirow{2}{5cm}{\centering $x^0 \in \mathcal{X}$} \\
+%$x^0 \in \mathds{B}^\mathds{N}$ & \\ 
+%\hline
+%$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.$ & $\forall n \in \mathds{N}, x^{n+1} = f(x^n)$ \\ 
+%\end{tabular}
+
+%}
+
+
+
+
+
+
+%\frame{
+%\frametitle{Définitions et notations}
+%\begin{block}{Introduisons quelques fonctions...}
+%\begin{itemize}
+%\item décalage: $\sigma : \mathcal{S} \longrightarrow \mathcal{S}, (S^n)_{n \in \mathds{N}} \mapsto (S^{n+1})_{n \in \mathds{N}}$.
+%\item initiale: $i : \mathcal{S} \longrightarrow \llbracket 1 ; \mathsf{N} \rrbracket, (S^n)_{n \in \mathds{N}} \mapsto S^0$
+%\item $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}
+%où $\delta(x,y) = \left\{\begin{array}{ll}
+%0 & \textrm{ si } x=y, \\
+%1 & \textrm{ sinon.}
+% \end{array}\right.
+%$
+%\end{block}
+%}
+
+
+
+
+%\frame{
+%\frametitle{Modélisation des IC}
+%\begin{alertblock}{Modélisation des IC en topologie}
+%Soit $\mathcal{X} = \llbracket 1 ; \mathsf{N} \rrbracket^\mathds{N} \times \mathds{B}^\mathsf{N},$ et $G_f\left(S,E\right) = \left(\sigma(S), F_f(i(S),E)\right).$ 
+
+
+%On modélise les itérations chaotiques $\left(f, (S,x^0)\right)$ par le système dynamique discret:
+%$$\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.$$
+%\end{alertblock}
+
+% \uncover<2>{
+% On peut donc étudier leur désordre topologique.
+% }
+%}
+
+
+
+
+
+%\frame{
+% \frametitle{Métrique et continuité}
+
+%Distance sur $\mathcal{X}:$
+%$$d((S,E);(\check{S};\check{E})) = d_e(E,\check{E}) +  d_s(S,\check{S})$$
+
+%\noindent où $\displaystyle{d_e(E,\check{E}) = \sum_{k=1}^\mathsf{N} \delta (E_k, \check{E}_k)}$, ~~et~ $\displaystyle{d_s(S,\check{S}) = \dfrac{9}{\textsf{N}} \sum_{k = 1}^\infty \dfrac{|S^k-\check{S}^k|}{10^k}}$.
+%%\end{block}
+
+%\vspace{0.5cm}
+
+%\begin{alertblock}{Théorème}
+%La fonction $G_f : (\mathcal{X},d) \to  (\mathcal{X},d)$ est continue.
+%\end{alertblock}
+
+%}
+
+
+
+% \frame{
+%  \frametitle{\'Etude de $(\mathcal{X},d)$}
+%  \begin{block}{Propriétés de $(\mathcal{X},d)$}
+%  \begin{itemize}
+%    \item $\mathcal{X}$ est infini indénombrable
+%    \vspace{0.15cm}
+%    \item $(\mathcal{X},d)$ est un espace métrique compact, complet et parfait
+%  \end{itemize}
+%  \end{block}
+% 
+%  \vspace{0.5cm}
+% 
+%    \begin{block}{\'Etude de $G_{f_0}$}
+%    $G_{f_0}$ est surjective, mais pas injective \vspace{0.3cm}\newline $\Rightarrow (\mathcal{X},G_{f_0})$ pas réversible.
+%  \end{block}
+
+% }
+
+
+
+%%\frame{
+%% \frametitle{Etude des périodes}
+%% \begin{block}{Multiplicité des périodes ?}
+%% Soit $f_0:\mathds{B}^\mathsf{N} \rightarrow \mathds{B}^\mathsf{N}$ la négation vectorielle.
+%%   \begin{itemize}
+%%     \item $\forall k \in \mathds{N}, Per_{2k+1}(G_{f_0}) = \varnothing, card\left(Per_{2k+2}(G_{f_0})\right)>0$ \vspace{0.3cm} \linebreak  $\Rightarrow G_{f_0}$ pas chaotique sur $\mathcal{X}$
+%%     \item Cependant :
+%%     \begin{itemize}
+%%       \item Il y a chaos sur $\mathcal{X}^G = \mathcal{P}\left(\llbracket 1,\mathsf{N}\rrbracket\right)^\mathds{N}\times \mathds{B}^\mathsf{N}$.
+%%       \item $G_{f_0}$ possède plus de $n^2$ points périodiques de période $2n$.
+%%     \end{itemize}
+%%   \end{itemize}
+%% \end{block}
+%% \uncover<2->{
+%%    Cette multiplicité des périodes n'est pas le désordre complet...
+%% }
+%%}
+
+
+
+%\subsection*{Approche type Devaney/Knudsen}
+
+%\frame{
+%  \frametitle{Les approches Devaney et Knudsen}
+%  \begin{block}{3 propriétés pour de l'imprévisibilité}
+%    \begin{enumerate}
+%      \item \emph{Indécomposabilité.} On ne doit pas pouvoir simplifier le système
+%      \begin{itemize}
+%        \item Impossible de diviser pour régner
+%        \item Des orbites doivent visiter tout l'espace
+%      \end{itemize}
+%      \item \emph{Élément de régularité.}
+%      \begin{itemize}
+%        \item Contrecarre l'effet précédent
+%        \item Des points proches \textit{peuvent} se comporter complètement différemment
+%      \end{itemize}
+%      \item \emph{Sensibilité.} Des points proches \textit{peuvent} finir éloignés
+%    \end{enumerate}
+%  \end{block}
+%}
+
+
+%\frame{
+% \frametitle{Exemple : définition de Devaney}
+%\begin{enumerate}
+%\item \emph{Transitivité:} Pour chaque couple d'ouverts non vides $A,B \subset \mathcal{X}$, il existe $k \in \mathbb{N}$ tel que $f^{(k)}(A)\cap B \neq \varnothing$
+%\item \emph{Régularité:} Les points périodiques sont denses
+%\item \emph{Sensibilité aux conditions initiales:} Il existe $\varepsilon>0$ tel que $$\forall x \in \mathcal{X}, \forall \delta >0, \exists y \in \mathcal{X}, \exists n \in \mathbb{N}, d(x,y)<\delta \textrm{ et } d(f^{(n)}(x),f^{(n)}(y)) \geqslant \varepsilon$$
+%\end{enumerate}
+%}
+
+%\frame{
+%   \frametitle{Systèmes intrinsèquement compliqués}
+%   \begin{block}{Définitions de l'indécomposabilité}
+%   \begin{itemize}
+%     \item \emph{Indécomposable}: pas la réunion de deux parties non vides, fermées et t.q. $f(A) \subset A$
+%     \item \emph{Totalement transitive}: $\forall n \geqslant 1$, l'application composée $f^{(n)}$ est transitive.
+%     \item \emph{Fortement transitif}:
+%$\forall x,y \in \mathcal{X},$ $\forall r>0,$ $\exists z \in B(x,r),$ $\exists n \in \mathbb{N},$ $f^{(n)}(z)=y.$
+%     \item \emph{Topologiquement mélangeant}:  pour toute paire d'ouverts disjoints et non vides $U$ et $V$, il existe $n_0 \in \mathbb{N}$ tel que $\forall n \geqslant n_0, f^{(n)}(U) \cap V \neq \varnothing$.
+%   \end{itemize}
+%   \end{block}
+%}
+
+
+
+
+%\frame{
+%\frametitle{Stabilité et expansivité}
+%   \begin{block}{Définitions de la sensibilité}
+%     \begin{itemize}
+%       \item $(\mathcal{X},f)$ est \emph{instable} si tous ses points le sont: $\forall x \in \mathcal{X},$ $\exists \varepsilon >0,$ $\forall \delta > 0,$ $\exists y \in \mathcal{X},$ $\exists n \in \mathbb{N},$ $d(x,y)<\delta$  et $d(f^{(n)}(x),f^{(n)}(y)) \geqslant \varepsilon$
+%       \item $(\mathcal{X},f)$ est \emph{expansif} si
+%$\exists \varepsilon >0,$ $\forall x \neq y,$ $\exists n \in \mathbb{N},$ $d(f^{(n)}(x),f^{(n)}(y)) \geqslant \varepsilon$
+%     \end{itemize}
+%   \end{block}
+%}
+
+%%\frame{
+%%  \frametitle{Des systèmes imprévisibles}
+%%    \begin{block}{Définitions des systèmes dynamiques désordonnés}
+%%    \begin{itemize}
+%%      \item \emph{Devaney:} $(\mathcal{X},f)$ est sensible aux conditions initiales, régulier et transitif
+%%       \item \emph{Wiggins:} $(\mathcal{X},f)$ est transitif et sensible aux conditions initiales
+%%       \item \emph{Knudsen:} $(\mathcal{X},f)$ a une orbite dense et s'il est sensible aux conditions initiales
+%%       \item \emph{expansif:} $(\mathcal{X},f)$ est transitif, régulier et expansif
+%%    \end{itemize}
+%%    \end{block}
+%%}
+
+
+
+%\subsection*{Autres approches}
+
+
+%\frame{
+%  \frametitle{Selon Li et Yorke}
+%    \begin{block}{Définitions}
+%    \begin{description}
+%\item[Couple de Li-Yorke.] $(x,y)$ en est un quand: $\limsup_{n \rightarrow +\infty} d(f^{(n)}(x), f^{(n)}(y))>0$ et $\liminf_{n \rightarrow +\infty} d(f^{(n)}(x), f^{(n)}(y))=0.$
+
+%\item[Ensemble brouillé.] $B \subset \mathcal{X}$ en est un si tout couple de points distincts de $B$ est de Li-Yorke.
+
+%\item[Systèmes de Li-Yorke.] $\mathcal{X}$ est compact et contient un ensemble brouillé indénombrable.
+%\end{description}
+%\end{block}
+%}
+
+
+
+
+
+
+%\frame{
+% \frametitle{Approche entropie topologique}
+%   \begin{block}{Entropie topologique}
+%   \begin{itemize}
+%   \item $x,y \in \mathcal{X}$ sont ~$\varepsilon-$\emph{séparés en temps $n$} s'il existe $k \leqslant n$ tel que $d\left(f^{(k)}(x),f^{(k)}(y)\right)>\varepsilon$.
+%   \item Les ensembles $(n,\varepsilon)-$séparé sont des ensembles de points qui seront tous $\varepsilon-$séparés en temps $n$
+%   \item $s_n(\varepsilon,Y)$: cardinal maximal d'un ensemble $(n,\varepsilon)-$séparé $$h_{top}(\mathcal{X},f)  = \displaystyle{\lim_{\varepsilon \rightarrow 0} \Big[ \limsup_{n \rightarrow +\infty} \dfrac{1}{n} \log s_n(\varepsilon,\mathcal{X})\Big]}$$
+%   \end{itemize}
+%   \end{block}
+%}
+
+
+
+
+%\frame{
+% \frametitle{Exposant de Lyapunov}
+%\begin{block}{L'exposant de Lyapunov}
+%$$\lambda(x^0) = \displaystyle{\lim_{n \to +\infty} \dfrac{1}{n} \sum_{i=1}^n \ln \left| ~f'\left(x^{i-1}\right)\right|}$$
+%Il doit être positif pour multiplier les erreurs
+%\end{block}
+%}
+
+
+
+
+
+%\subsection*{Etude des systèmes itératifs}
+
+%%\frame{
+%%  \frametitle{IC et propriété de Devaney}
+%%\begin{alertblock}{Théorème}
+%%$G_{f_0}$ est régulier et transitif (Devaney). 
+
+%%Sa sensibilité est $\geqslant \mathsf{N}-1$.
+%%\end{alertblock}
+
+%%\uncover<2->{
+%% \begin{exampleblock}{Question}
+%% $f_0$ est-elle la seule fonction dont le système itératif vérifie la condition de Devaney ?
+%% \end{exampleblock}
+%% 
+%% \vspace{0.5cm}
+
+%%Pour y répondre, nous avons utilisé le graphe de tous les possibles par itérations chaotiques : le GTPIC.}
+%%}
+
+
+
+
+%%\frame{
+%%  \frametitle{Nombre de fonctions imprévisibles}
+%%  \begin{alertblock}{Caractérisation des IC imprévisibles selon Devaney}
+%%$G_f$ vérifie l'hypothèse de Devaney $\Leftrightarrow$ Son graphe des possibles est fortement connexe.
+
+%%$\Rightarrow$ Il y a $\left(2^\mathsf{N}\right)^{2^\mathsf{N}}$ IC chaotiques.
+%%\end{alertblock}
+%%}
+
+
+
+
+
+
+
+%\frame{
+%  \frametitle{Etude topologique}
+%    \begin{exampleblock}{Etude topologique des ICs}
+%      \begin{itemize}
+%        \item $\forall f \in \mathcal{C}$, $Per\left(G_f\right)$ est infini dénombrable, $G_f$ est fortement transitive,  est chaotique selon Knudsen, 
+%        \item $\left(\mathcal{X}, G_{f_0}\right)$ est topologiquement mélangeant, expansif (constante 1), est chaotique selon Li-Yorke, a une entropie topologique infinie, un exposant de Lyapunov de $ln(\mathsf{N})$
+%        \item Indécomposabilité, instabilité, chaos de Wiggins, de la multiplicité des périodes...
+%      \end{itemize}
+%    \end{exampleblock}
+%}
+
+
+
+
+
+
+
+%\frame{
+% \frametitle{Graphe de tous les possibles par IC}
+%  \begin{center}
+%   \includegraphics[scale=0.55]{14.Caracterisation_des_IC_chaotiques_selon_Devaney/grapheTPICver2.pdf}
+%  \end{center}
+%}
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%\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}