Import initial

[review_prng.git] / review_prng.tex

\documentclass{article}
\usepackage[utf8x]{inputenc}
\usepackage[standard]{ntheorem}
\usepackage[english]{babel}


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

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


%  
%  
%    \begin{block}{Convergence}
%      \begin{itemize}
%        \item $f$ monotone
%        \item Applications contractantes
%        \item Coppel: Pas de 2-cycle $\Rightarrow$ convergence
%      \end{itemize}
%    \end{block}
%}



%\frame{
%  \frametitle{3-cycle implique chaos}
%  \begin{alertblock}{Period Three Implies Chaos (Li et Yorke, 1975)}
%S'il y a un point de période 3, alors il y a un point de n'importe quelle période
%  \end{alertblock}
%  
%  \uncover<2->{
%  \begin{exampleblock}{Remarques}
%  \begin{itemize}
%    \item Désordre lié à la multiplicité des périodes
%    \item \`A AND, on étudie des ``systèmes itératifs'' pour le calcul distribué, généralisation des suites récurrentes
%  \end{itemize}
%  \end{exampleblock}
%  }
%}





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

%%\frame{
%%  \frametitle{Les systèmes itératifs: généralisation}
%%  \begin{block}{Les systèmes itératifs en toute généralité}
%%  La formulation suivante englobe tous les modes d'itérations imaginables:
%%  $$\left\{
%%  \begin{array}{l}
%%    x^0 \in \mathcal{X}\\
%%    x^{n+1} = f^n(x^0, \hdots, x^n)
%%  \end{array}
%%  \right.$$
%%  où $f^n:\mathcal{X}^{n+1}\rightarrow \mathcal{X}$
%%  \end{block}
%%\uncover<2->{
%%Différents modes d'itérations: séries, parallèles, chaotiques, asynchrones...
%%}
%%}










%\subsection*{Cas des Itérations chaotiques}
%\frame{
%  \frametitle{Les « itérations chaotiques »}
%    \begin{block}{Définition (Itérations chaotiques)}
% Soient $f: \mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N}$ et $S \subset \mathcal{P} \left(\llbracket1,\mathsf{N}\rrbracket\right)^\mathds{N}$. Les \emph{itérations chaotiques} sont:
%$$\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{ si } i \notin S^n\\
%f(x^{n-1})_{i} & \textrm{ si } i \in S^n
%\end{array}
%\right.
%\end{array}
%\right.$$
%\end{block}
%%\uncover<2->{
%%Itérations chaotiques et théorie du chaos: a priori, rien à voir.
%%}
%%\uncover<3->{Y a-t-il un lien ?}\uncover<4->{ Pour quoi faire ?}
%}





%\frame{
%  \frametitle{Non-convergence des IC}
%   \begin{alertblock}{Théorème (Condition nécessaire de non-convergence)}
%    % Soit $f : \mathds{B}^\mathsf{N} \to \mathds{B}^\mathsf{N}$ et $S \in \mathcal{S}$. 
%    Si les itérations chaotiques $\left(f,(x^0,S)\right)$ sont non convergentes, alors:
%\begin{itemize}
%\item soit $f$ n'est pas contractante,
%\item soit $S$ n'est pas pseudo-périodique (complète).
%\end{itemize}
%   \end{alertblock}
%   \uncover<2->{
%   Quelle quantité de désordre ?
%   }
%}










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