X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/review_prng.git/blobdiff_plain/62c3786a4c8ba104653ce9d11e4bba511806814e..af5ccdc8b87c569ce32f355e5c631e0c2c0574ed:/review_prng.tex?ds=sidebyside diff --git a/review_prng.tex b/review_prng.tex index c6ab2f1..1ddc487 100644 --- a/review_prng.tex +++ b/review_prng.tex @@ -1,6 +1,1984 @@ \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}, k0$ \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}