X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/review_prng.git/blobdiff_plain/62c3786a4c8ba104653ce9d11e4bba511806814e..refs/heads/master:/review_prng.tex?ds=inline diff --git a/review_prng.tex b/review_prng.tex index c6ab2f1..80fece0 100644 --- a/review_prng.tex +++ b/review_prng.tex @@ -1,6 +1,2000 @@ \documentclass{article} +\usepackage[utf8x]{inputenc} +\usepackage[standard]{ntheorem} +\usepackage[english]{babel} + +\usepackage{stmaryrd} +\usepackage{amsmath} +\usepackage{color} +\usepackage{dsfont} +\usepackage{graphicx} + + +\title{A Review of Chaotic Iteration Based Pseudorandom Number Generators} +\author{Jacques M. Bahi, Jean-Fran\c cois Couchot, Raphaël Couturier,\\ Nicolas Friot, and Christophe Guyeux~\thanks{Authors in alphabetic order}} + + \begin{document} +\maketitle + +\begin{abstract} + +\end{abstract} + + +\section{Introduction} + + +\section{Topological Study of Disorder} + +\subsection{Historical Context} + +Pseudorandom number generators are recurrent sequences having a disordered behavior. + +Recurrent sequences, also called discrete dynamical systems, of the form +\begin{equation} +\label{sdd} +u^0 \in \mathds{R}, u^{n+1} = f(u^n), +\end{equation} +with +$f$ continuous, have been well studied since the early years of mathematical +analysis. They are widely used, for instance to resolve equations using a +Newton method, or when approximating the solutions to differential equations +using finite difference equations to approximate derivatives. +The context study was the seek for convergence, which is for instance guarantee +when using monotonic functions or contractions. +In the middle of the last century, Coppel has +established a link between this desire of convergence +and the existence of a cycle in iterations~\cite{Coppel55}. +More precisely, his theorem states that, considering Eq.~\eqref{sdd} with a function +$f:I \longrightarrow I$ continuous on the line segment $I$, the absence of +any 2-cycle implies the convergence of the discrete dynamical system. + +This theorem establish a clear link between the existence of a cycle of +a given length and the convergence of the system. In other words, between +cycles and order. Conversely, Li and Yorke have established in 1975~\cite{Li75} that +the presence of a point of period three implies chaos in the same situation +than previously. By chaos, they mean the existence of points of any +period: this kind of disorder, which is the first occurrence of the +term ``chaos'' in the mathematical literature, is thus related to the +multiplicity of periods. Since that time, the mathematical theory of +chaos has known several developments to qualify or quantify the richness +of chaos presented by a given discrete dynamical system, one of the most +famous work, although old, being the one of Devaney~\cite{Devaney}. + +\subsection{Iterative Systems} + +In the distributed computing community, dynamical systems have been +generalized to take into account delay transmission or heterogeneous +computational powers. Mathematically, the intended result is often one +fixed point resulting from the iterations of a given function over a +Boolean vector, considering that: +\begin{itemize} +\item at time $t$, $x^{t}$ is computed using not only $x^{t-1}$, but +potentially any $x^{k}, k0$. +\end{proposition} + +So $ G_{f_0}$ does not present the existence of points of any period referred as chaos in the article of Li and Yorke~\cite{Li75}. +However~\cite{GuyeuxThese10}: + \begin{itemize} + \item This kind of disorder can be stated on $\mathcal{X}^G = \mathcal{P}\left(\llbracket 1,\mathsf{N}\rrbracket\right)^\mathds{N}\times \mathds{B}^\mathsf{N}$. + \item $G_{f_0}$ possesses more than $n^2$ points of period $2n$. + \end{itemize} +Additionally, this existence of points of any period has been rejected +by the community to the benefit of more recent notions of chaos, +like those developed these last decades by Devaney~\cite{Devaney}, Knudsen~\cite{Knudsen94}, etc. +These approaches are recalled in the next section. + +\section{The Mathematical Theory of Chaos} + +We will present in this section various understanding of a chaotic behavior for a discrete +dynamical system. + +\subsection{Approaches Similar to Devaney} + +In these approaches, three ingredients are required for unpredictability. +Firstly, the system must be intrinsically complicated, undecomposable: it cannot be simplified into two +subsystems that do not interact, making any divide and conquer strategy +applied to the system inefficient. In particular, a lot of orbits must visit +the whole space. Secondly, an element of regularity is added, to counteract +the effects of the first ingredient, leading to the fact that closed points +can behave in a completely different manner, and this behavior cannot be predicted. +Finally, sensibility of the system is demanded as a third ingredient, making that +closed points can finally become distant during iterations of the system. +This last requirement is, indeed, often implied by the two first ingredients. + +Having this understanding of an unpredictable dynamical system, Devaney has +formalized in~\cite{Devaney} the following definition of chaos. + +\begin{definition} +A discrete dynamical system $x^0 \in \mathcal{X}, x^{n+1}=f(x^n)$ on a +metric space $(\mathcal{X},d)$ is said to be chaotic according to Devaney +if it satisfies the three following properties: + \begin{enumerate} +\item \emph{Transitivity:} For each couple of open sets $A,B \subset \mathcal{X}$, there exists $k \in \mathbb{N}$ such that $f^{(k)}(A)\cap B \neq \varnothing$. +\item \emph{Regularity:} Periodic points are dense in $\mathcal{X}$. +\item \emph{Sensibility to the initial conditions:} There exists $\varepsilon>0$ such that $$\forall x \in \mathcal{X}, \forall \delta >0, \exists y \in \mathcal{X}, \exists n \in \mathbb{N}, d(x,y)<\delta \textrm{ and } d(f^{(n)}(x),f^{(n)}(y)) \geqslant \varepsilon.$$ +\end{enumerate} +\end{definition} + +The system can be intrinsically complicated for various other understanding of this wish, that are +not equivalent one another, like: +\begin{itemize} + \item \emph{Undecomposable}: it is not the union of two nonempty closed subsets that are positively invariant ($f(A) \subset A$). + \item \emph{Total transitivity}: $\forall n \geqslant 1$, the function composition $f^{(n)}$ is transitive. + \item \emph{Strong transitivity}: $\forall x,y \in \mathcal{X},$ $\forall r>0,$ $\exists z \in B(x,r),$ $\exists n \in \mathbb{N},$ $f^{(n)}(z)=y.$ + \item \emph{Topological mixing}: for all pairs of disjoint open nonempty sets $U$ and $V$, there exists $n_0 \in \mathbb{N}$ such that $\forall n \geqslant n_0, f^{(n)}(U) \cap V \neq \varnothing$. +\end{itemize} + + +Concerning the ingredient of sensibility, it can be reformulated as follows. +\begin{itemize} + \item $(\mathcal{X},f)$ is \emph{unstable} is all its points are unstable: $\forall x \in \mathcal{X},$ $\exists \varepsilon >0,$ $\forall \delta > 0,$ $\exists y \in \mathcal{X},$ $\exists n \in \mathbb{N},$ $d(x,y)<\delta$ and $d(f^{(n)}(x),f^{(n)}(y)) \geqslant \varepsilon$. + \item $(\mathcal{X},f)$ is \emph{expansive} is $\exists \varepsilon >0,$ $\forall x \neq y,$ $\exists n \in \mathbb{N},$ $d(f^{(n)}(x),f^{(n)}(y)) \geqslant \varepsilon$ +\end{itemize} + +These variety of definitions lead to various notions of chaos. For instance, +a dynamical system is chaotic according to Wiggins if it is transitive and +sensible to the initial conditions. It is said chaotic according to Knudsen +if it has a dense orbit while being sensible. Finally, we speak about +expansive chaos when the properties of transitivity, regularity, and expansivity +are satisfied. + + + +\subsection{Li-Yorke approach} + +The approach for chaos presented in the previous section, considering that +a chaotic system is a system intrinsically complicated (undecomposable), +with possibly an element of regularity and/or sensibility, has been +completed by other understanding of chaos. Indeed, as ``randomness'' +or ``infiniteness'', a single universal definition of chaos is cannot +be found. The kind of behaviors that are attempted to be described are +too much complicated to enter into only one definition. Instead, a +large panel of mathematical descriptions have been proposed these last +decades, being all theoretically justified. Each of these definitions +give illustration to some particular aspects of a chaotic behavior. + +The first of these parallel approaches can be found in the pioneer +work of Li and Yorke~\cite{Li75}. In their well-known article entitled +``Period three implies chaos'', they rediscovered a weaker formulation of +the Sarkovskii's theorem, meaning that when a discrete dynamical system +$(f,[0,1])$, with $f$ continuous, has a 3-cycle, then it has too a +$n-$cycle, $\forall n \leqslant 2$. The community has not adopted this +definition of chaos, as several degenerated systems satisfy this property. +However, on their article~\cite{Li75}, Li and Yorke have studied too +another interesting property, which has led to a notion of chaos +``according to Li and Yorke'', which is recalled below. + +Let us firstly introduce the definition of Li-Yorke scrambled couple +of points. This is points that never stop to oscillate. + +\begin{definition} +Let $(\mathcal{X},d)$ a metric space and $f:\mathcal{X} \longrightarrow +\mathcal{X}$ a continuous map. $(x,y)\in \mathcal{X}^2$ is a scrambled +couple of points if $lim inf_{n\rightarrow \infty} d(f^n(x),f^n(y))=0$ +and $lim sup_{n\rightarrow \infty} d(f^n(x),f^n(y))>0$. +\end{definition} + +A scrambled set is a set in which any couple of points oscillate (are +a scrambled couple), whereas a Li-Yorke chaotic system is a system +possessing an uncountable scrambled set. + + +\subsection{Topological Entropy Approach} + +The topological entropy of a topological dynamical system, +firstly introduced in 1965 by Adler, Konheim, and McAndrew~\cite{Adler65}, +is a nonnegative real number that measures the complexity of the system. +It represents the exponential growth rate of the number of distinguishable +orbits of the iterates, for a system given by an iterated function. +It can be formulated as follows. + +Let $f:\mathcal{X} \longrightarrow \mathcal{X}$ be a continuous map on +a compact metric space $(\mathcal{X},d)$. For each natural +number $n$, a new metric $d_n$ is defined on $\mathcal{X}$ by +$$d_n(x,y)=\max\{d(f^i(x),f^i(y)): 0\leq i0$ and $n \geqslant 1$, two points of +$\mathcal{X}$ are $\varepsilon$-close with respect to +this metric if their first $n$ iterates are $\varepsilon$-close. This +metric allows one to distinguish in a neighborhood of an orbit the +points that move away from each other during the iteration from the +points that travel together. + +A subset $E$ of $\mathcal{X}$ is said to be $(n,\varepsilon)$-separated +if each pair of distinct points of $E$ is at least $\varepsilon$ apart +in the metric $d_n$. Denote by $N(n, \varepsilon)$ the +maximum cardinality of a $(n,\varepsilon)$-separated set. +$N(n, \varepsilon)$ represents the number of distinguishable orbit +segments of length $n$, assuming that we cannot distinguish points +within $\varepsilon$ of one another. + +\begin{definition} +The topological +entropy of the map $f$ is defined by +$$h(f)=\lim_{\epsilon\to 0} \left(\limsup_{n\to \infty} \frac{1}{n} +\log N(n,\epsilon)\right).$$ +\end{definition} + + + +The limit defining $h(f)$ may +be interpreted as the measure of the average exponential growth of the +number of distinguishable orbit segments. In this sense, it measures +complexity of the topological dynamical system $(\mathcal{X}, f)$. + +\subsection{The Lyapunov Exponent} + +The last measure of chaos that has been regarded for our proposed family +of pseudorandom number generators is the Lyapunov exponent. This +quantity characterizes the rate of separation of infinitesimally close +trajectories. Indeed, two trajectories in phase space with initial +separation $\delta$ diverge at a rate approximately +equal to $\delta e^{\lambda t}$, +where $\lambda$ is the Lyapunov exponent, which is defined by: + +\begin{definition} +Let $f:\mathds{R} \longrightarrow \mathds{R}$ be a differentiable +function, and $x^0\in \mathds{R}$. The Lyapunov exponent is given by +$$\lambda(x^0) = \displaystyle{\lim_{n \to +\infty} \dfrac{1}{n} \sum_{i=1}^n \ln \left| ~f'\left(x^{i-1}\right)\right|}.$$ +\end{definition} + +Obviously, this exponent must be positive to have a multiplication of +initial errors, and thus chaos in this understanding. + +Having all these definitions in mind, we have studied the topological +behavior of chaotic iterations presented in Definition~\ref{defIC}. + +\section{The Study of Iterative Systems} + +We have firstly stated that~\cite{gb11:bc,GuyeuxThese10}: + +\begin{theorem} + $G_{f_0}$ is regular and transitive on $(\mathcal{X},d)$, thus it is + chaotic according to Devaney. +Furthermore, its constant of sensibility is greater than $\mathsf{N}-1$. +\end{theorem} + +Thus the set $\mathcal{C}$ of functions $f:\mathds{B}^\mathsf{N} +\longrightarrow \mathds{B}^\mathsf{N}$ making the chaotic iterations of +Definition~\ref{defIC} a case of chaos according to Devaney, is a nonempty +set. To characterize functions of $\mathcal{C}$, we have firstly stated +that transitivity implies regularity for these particular iterated +systems~\cite{bcgr11:ip}. To achieve characterization, we then have introduced the +following graph. + +\begin{figure} + \centering + \includegraphics[scale=0.55]{grapheTPICver2.pdf} + \caption{Example of an asynchronous iteration graph} + \label{GTPIC} + \end{figure} + + + +Let $f$ be a map from $\mathds{B}^\mathsf{N}$ to itself. The +{\emph{asynchronous iteration graph}} associated with $f$ is the +directed graph $\Gamma(f)$ defined by: the set of vertices is +$\mathds{B}^\mathsf{N}$; for all $x\in\mathds{B}^\mathsf{N}$ and +$i\in \llbracket1;\mathsf{N}\rrbracket$, +the graph $\Gamma(f)$ contains an arc from $x$ to $F_f(i,x)$. +The relation between $\Gamma(f)$ and $G_f$ is clear: there exists a +path from $x$ to $x'$ in $\Gamma(f)$ if and only if there exists a +strategy $s$ such that the parallel iteration of $G_f$ from the +initial point $(s,x)$ reaches the point $x'$. Figure~\ref{GTPIC} presents +such an asynchronous iteration graph. +We thus have proven that~\cite{bcgr11:ip}. + + +\begin{theorem} +$G_f$ is transitive, and thus chaotic according to Devaney, +if and only if $\Gamma(f)$ is strongly connected. +\end{theorem} + +This characterization makes it possible to quantify the number of +functions in $\mathcal{C}$: it is equal to + $\left(2^\mathsf{N}\right)^{2^\mathsf{N}}$. +Then the study of the topological properties of disorder of these +iterative systems has been further investigated, leading to the following +results. + +\begin{theorem} + $\forall f \in \mathcal{C}$, $Per\left(G_f\right)$ is infinitely countable, $G_f$ is strongly transitive and is chaotic according to Knudsen. It is thus undecomposable, unstable, and chaotic as defined by Wiggins. + \end{theorem} + + \begin{theorem} +$\left(\mathcal{X}, G_{f_0}\right)$ is topologically mixing, + expansive (with a constant equal to 1), chaotic as defined by + Li and Yorke, and has a topological entropy and an exponent of Lyapunov + both equal to $ln(\mathsf{N})$. +\end{theorem} + +At this stage, a new kind of iterative systems that only manipulates +integers have been discovered, leading to the questioning of their +computing for security applications. In order to do so, the possibility +of their computation without any loss of chaotic properties has first +been investigated. These chaotic machines are presented in the next +section. + + + + +\section{Topology of Programs} + + +The next stage was to prove that chaos was possible in finite machine. +The two main problems were that: (1) Chaotic sequences are usually +defined in the real line whereas define real numbers on computers +is impossible. (2) All finite state machines always enter into a cycle +when iterating, and this periodic behavior cannot be stated as chaotic. + +The first problem is disputable, as the shadow lemma proves that, when +considering the sequence $x^{n+1} = trunc_k\left(f(x^n)\right)$, where +$(f,[0,1])$ is a chaotic dynamical system and $trunc_k(x) = +\dfrac{\lfloor 10^k x \rfloor}{10^k}$ is the truncated version of +$x\in \mathds{R}$ at its $k-$th digits, then the sequence $(x^n)$ is as +close as possible to a real chaotic orbit. Thus iterating a chaotic +function on floating point numbers does not deflate the chaotic behavior +as much. However, even if this first claim is not really a problem, we +have prevent from any disputation by considering a tool (the chaotic +iterations) that only manipulates integers bounded by $\mathsf{N}$. + +The second claim is surprisingly never considered as an issue when +considering the generation of randomness on computers. + + + + +%%\frame{ +%% \frametitle{Mode d'emploi} +%% \begin{alertblock}{Chaos sur machine: quelques règles} +%% \begin{enumerate} +%% \item Ne pas laisser la machine travailler en vase clos %\newline +%% %$\Rightarrow$ Une nouvelle entrée à chaque itérée +%% \item Utiliser les médias sur lesquels on travaille %\newline +%% %$\Rightarrow$ Ensemble infini dénombrable +%% \item Ne manipuler que des entiers +%% \item \'Eviter les tailles fixes %(graine, nombre d'itérations, etc.) +%% \end{enumerate} +%% \end{alertblock} +%%} + + + + + +%\frame{ +% \frametitle{Introduction} +% \begin{block}{Deux cas de figure} +% \begin{itemize} +% \item En vase clos : +% \begin{itemize} +% \item 4 Go de mémoire $\Rightarrow 2^{4000000000}$ états possibles... +% \item Lemme de filature/lemme fantôme +% \end{itemize} +% \item $\mathcal{X}=\mathds{B}^\mathsf{N}\times \mathcal{P}\left(\llbracket 1;\mathsf{N}\rrbracket\right)^\mathds{N}$: +% \begin{itemize} +% \item Pas de réels, que des entiers bornés par $\mathsf{N}$ +% \item On peut utiliser le média à chaque itérée +% \end{itemize} +% \end{itemize} +% \end{block} +%} + + + + + + +%\frame{ +% \frametitle{Introduction} +% \begin{exampleblock}{Deux questions} +%% Vos ICs sont chaotiques, mais pour moi c'est pas ça une machine, un programme. +%\begin{itemize} +% \item Peut-on construire des automates chaotiques ? +% \item Peut-on évaluer si un programme est chaotique ? +%\end{itemize} +% \end{exampleblock} +%} + + + + + +%\frame{ +% \frametitle{Une machine de Moore chaotique} +% \begin{center} +% \includegraphics[scale=0.55]{14.Caracterisation_des_IC_chaotiques_selon_Devaney/grapheTPICver2.pdf} +% \end{center} +%} + + + + + +%\frame{ +%\frametitle{Le chaos d'un programme} +%\begin{block}{Machines de Turing et systèmes itératifs} +%Soit $(w,i,q)$ la configuration actuelle de la machine de Turing\\ +%\begin{center} +%\includegraphics[scale=0.3]{Steganalyse/Medias/Turing.pdf} +%\end{center} +%\begin{itemize} +%\item $w=\sharp^{-\omega} w(0) \hdots w(k)\sharp^{\omega}$ est la bande de lecture, +%\item $i$ est la position de la tête de lecture, +%\item $q$ décrit l'état de la machine, +%\item et $\delta$ est sa fonction de transition. +%\end{itemize} +%\end{block} +%} + + + +%\frame{ +%\frametitle{Le chaos d'un programme} +%\begin{block}{Machines de Turing et systèmes itératifs} +%On définit $f$ par: + +%\begin{itemize} +%\item Si $\delta(q;w(i)) = (q'; a; \rightarrow)$, alors $f(w(0) \hdots w(k);i;q) = ( w(0) \hdots w(i-1) ~ a ~ w(i+1) \hdots w(k); i+1; q')$ +%\item Si $\delta(q;w(i)) = (q'; a; \leftarrow)$, alors $f( w(0) \hdots w(k);i;q) = (w(0) \hdots w(i-1) ~ a ~ w(i+1) \hdots w(k); i-1; q')$ +%\end{itemize} + +%La machine peut être écrite sous la forme $x^{n+1}=f(x^n)$ +%\end{block} +%} + + + + + + + +%\frame{ +% \frametitle{A quoi ça sert ?} +% \begin{exampleblock}{Un programme chaotique, pour quoi faire ?} +%\begin{itemize} +% \item Se placer dans de bonnes conditions lors de conception de nouveaux algorithmes +% \item Renforcer les attaques (virus chaotique) +% \item Simuler numériquement des processus chaotiques +% \item Renforcer la sécurité +% \item Battre l'intelligence artificielle +%\end{itemize} +% \end{exampleblock} +% +%% \uncover<3->{ +%% Tentons une première illustration +%% } +%} + + + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%\section{Applications aux PRNGs} +%\subsection*{PRNGs} +%\begin{frame}{Applications} +%% 'transition': Crossfade, +% \begin{center} +% \Huge{Applications} + +%\medskip +% \huge{Générateurs pseudo-aléatoires} +% \end{center} +%\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%\frame{ +% \frametitle{Chaos et aléas} +% \begin{block}{Motivations: La batterie du NIST} +% \begin{itemize} +%\item \textbf{Transitivités} +% \begin{itemize} +% \item \textbf{Random Excursions Variant Test.} To detect deviations from the expected number of visits to various states in the random walk. +% \item \textbf{Random Excursions Test.} To determine if the number of visits to a particular state within a cycle deviates from what one would expect for a random sequence. +% \end{itemize} +%\item \textbf{Chaos selon Li-Yorke} +% \begin{itemize} +% \item \textbf{Runs Test.} To determine whether the number of runs of ones and zeros of various lengths is as expected for a random sequence. In particular, this test determines whether the oscillation between such zeros and ones is too fast or too slow. +% \end{itemize} +%\end{itemize} +%\end{block} +%} + +%\frame{ +% \frametitle{Chaos et aléas} +% \begin{block}{Motivations: La batterie du NIST} +% \begin{itemize} +% \item \textbf{Régularité} +% \begin{itemize} +% \item \textbf{Non-overlapping Template Matching Test} To detect generators that produce too many occurrences of a given non-periodic (aperiodic) pattern (m is the length in bits of each template which is the target string). +% \item \textbf{Discrete Fourier Transform (Spectral) Test} To detect periodic features (i.e., repetitive patterns that are near each other) in the tested sequence that would indicate a deviation from the assumption of randomness. +% \end{itemize} +% \item \textbf{Entropie} +% \begin{itemize} +%\item \textbf{Approximate Entropy Test} To compare the frequency of overlapping blocks of two consecutive/adjacent lengths (m and m+1) against the expected result for a random sequence (m is the length of each block). +% \end{itemize} +% \end{itemize} +%\end{block} +%} + +%\frame{ +% \frametitle{Chaos et aléas} +% \begin{block}{Motivations: La batterie du NIST} +% \begin{itemize} +% \item \textbf{Non-linéarité, complexité} +% \begin{itemize} +%\item \textbf{Binary Matrix Rank Test} To check for linear dependence among fixed length substrings of the original sequence. +%\item \textbf{Linear Complexity Test} To determine whether or not the sequence is complex enough to be considered random (M is the length in bits of a block). +% \end{itemize} +%\end{itemize} +% \end{block} +%} + + +%\subsection*{Le Old CI PRNG} +%\frame{ +% \frametitle{Notre PRNG} +% \begin{alertblock}{Le PRNG $CI_f(PRNG_1,PRNG_2)$} +% \begin{description} +%\item[\underline{Paramètres:}] Une fonction $f: \mathds{B}^\mathsf{N} \rightarrow \mathds{B}^\mathsf{N}$, et deux PRNGs:\\ +%\begin{itemize} +%\item $S\in\llbracket 1,\mathsf{N}\rrbracket^\mathds{N}$ +%\item et $m\in S^\mathds{N}, S \subset \mathds{N}$ +%\end{itemize} +%\item[\underline{Graine:}] Les graines de $S$ et $m$, et $E\in \mathds{B}^\mathsf{N}$\\ +%\item[\underline{PRNG:}] $\left(G_f(E,S)^{m^i}\right)_{i\in\mathds{N}}$ +%\end{description} +% \end{alertblock} +% +%% \uncover<2->{ +%% \begin{exampleblock}{Exemple: $X^{n+1} = X^n \oplus Y^n$} +%% où $Y \in \llbracket 0, 2^{\mathsf{N}}-1 \rrbracket^\mathds{N}$ +%% \end{exampleblock} +%% } +%} + + + +%%\frame{ +%% \frametitle{Old CI PRNG: Illustration} +%% \begin{block}{} +%%\begin{figure} +%%\centering +%% \includegraphics[scale=0.4]{OldCI1.png} +%% \caption{Le Old CI PRNG} +%% \end{figure} +%% \end{block} +%%} + + + +%%\frame{ +%% \frametitle{Old CI PRNG: Illustration} +%% \begin{block}{} +%%\begin{figure} +%%\centering +%% \includegraphics[scale=0.41]{OldCI2.png} +%% \caption{Le Old CI PRNG} +%% \end{figure} +%% \end{block} +%%} + + +%%\frame{ +%% \frametitle{Old CI PRNG: Illustration} +%% \begin{block}{} +%%\begin{figure} +%%\centering +%% \includegraphics[scale=0.4]{OldCI3.png} +%% \caption{Le Old CI PRNG} +%% \end{figure} +%% \end{block} +%%} + + + + +%%\frame{ +%% \frametitle{Old CI PRNG: Illustration} +%% \begin{block}{} +%%\begin{figure} +%%\centering +%% \includegraphics[scale=0.4]{OldCI4.png} +%% \caption{Le Old CI PRNG} +%% \end{figure} +%% \end{block} +%%} + + + +%%\frame{ +%% \frametitle{Old CI PRNG: Illustration} +%% \begin{block}{} +%%\begin{figure} +%%\centering +%% \includegraphics[scale=0.4]{OldCI5.png} +%% \caption{Le Old CI PRNG} +%% \end{figure} +%% \end{block} +%%} + + + + +%%\frame{ +%% \frametitle{Graphe de tous les possibles par IC} +%% \begin{center} +%% \includegraphics[scale=0.55]{14.Caracterisation_des_IC_chaotiques_selon_Devaney/grapheTPICver2.pdf} +%% \end{center} +%%} + + + + + +%\begin{frame}{Le Old $CI_{f_0}$(logistic,logistic)} +%\begin{block}{} +%\begin{tabular}{llllllllll} +%m (logistic map):&\uncover<1->{2} &\uncover<3->{~} &\uncover<4->{~} &\uncover<5->{~1}&\uncover<8->{~4}&\uncover<9->{~}&\uncover<10->{~}&\uncover<11->{~}& \uncover<13->{...}\\ +%S (logistic map):&\uncover<2->{1} &\uncover<3->{~3} &\uncover<4->{~} &\uncover<6->{~2}&\uncover<9->{~1}&\uncover<10->{~1}&\uncover<11->{~2}&\uncover<12->{~1}& \uncover<14->{...}\\ +%\end{tabular} +%\end{block} +% +%\begin{block}{\'Etat interne du système x:} +%\begin{equation} +%\label{Basic equations} +%\begin{array}{r@{\;}l} +%\ \textbf{0}\uncover<2->{\rightarrow \textbf{1}} \uncover<3->{\rightarrow 1} \uncover<6->{\rightarrow 1} \uncover<9->{\rightarrow \textbf{0}} \uncover<10->{\rightarrow \textbf{1}} \uncover<11->{\rightarrow 1} \uncover<12->{\rightarrow \textbf{0}} \uncover<14->{...}\\ +%\ \textbf{0}\uncover<2->{\rightarrow 0} \uncover<3->{\rightarrow 0} \uncover<6->{\rightarrow \textbf{1}} \uncover<9->{\rightarrow 1} \uncover<10->{\rightarrow 1} \uncover<11->{\rightarrow \textbf{0}} \uncover<12->{\rightarrow 0} \uncover<14->{...}\\ +%\ \textbf{0}\uncover<2->{\rightarrow 0} \uncover<3->{\rightarrow \textbf{1}} \uncover<6->{\rightarrow 1} \uncover<9->{\rightarrow 1}\uncover<10->{\rightarrow 1} \uncover<11->{\rightarrow 1} \uncover<12->{\rightarrow 1} \uncover<14->{...}\\ +%\ \textbf{0}\uncover<2->{\rightarrow 0} \uncover<3->{\rightarrow 0} \uncover<6->{\rightarrow 0} \uncover<9->{\rightarrow 0} \uncover<10->{\rightarrow 0} \uncover<11->{\rightarrow 0} \uncover<12->{\rightarrow 0} \uncover<14->{...}\\ +%\end{array} +%\end{equation} +%\end{block} + +%\begin{block}{} + +%\alert{Sortie:} \uncover<4->{1 0 1 0 }\uncover<7->{1 1 1 0 }\uncover<13->{0 0 1 0 }\uncover<14->{...} + +%\end{block} +%\end{frame} + + + + +%\begin{frame}{Choix de l'ensemble $\mathcal{M}$} +% \begin{figure}[!t] +% \centering +% \includegraphics[width=3.5in,height=2in]{lesM.png} +% \DeclareGraphicsExtensions. +% \caption{Nombre d'itérations entre deux sorties} +% \label{Premiers tests élémentaires} +% \end{figure} +%\end{frame} + + + + +%\begin{frame}{Choix de l'ensemble $\mathcal{M}$} +% \begin{figure}[!t] +% \centering +% \includegraphics[width=3.5in,height=2in]{leM.png} +% \DeclareGraphicsExtensions. +% \caption{Choix de $\mathcal{M}$} +% \end{figure} +%\end{frame} + + + + + +%\frame{ +%\frametitle{Résultats} +%\begin{alertblock}{Premiers résultats} +%\begin{enumerate} +% \item Générateur chaotique dès que le GTPIC de $G_f$ est fortement connexe +% \item Toutes les autres propriétés de chaos +% \item Sortie uniforme si la matrice d'adjacence réduite du GTPIC est doublement stochastique +% \item Les résultats aux tests statistiques sont meilleurs (DieHARD, NIST, TestU01) +%\end{enumerate} +%\end{alertblock} +%} + + + + +%\begin{frame}{Premiers tests comparatifs} +% \begin{figure}[!t] +% \centering +% \includegraphics[width=3.5in,height=2in]{1.pdf} +% \DeclareGraphicsExtensions. +% \caption{Premiers tests élémentaires} +% \label{Premiers tests élémentaires} +% \end{figure} +%\end{frame} + + +%\begin{frame}{NIST pour les PRNG en entrée} +% \begin{figure}[!t] +% \centering +% \includegraphics[scale=0.27]{NistSeul.png} +% \DeclareGraphicsExtensions. +% \caption{Le NIST pour 3 PRNG} +% \end{figure} +%\end{frame} + + + +%\begin{frame}{NIST pour le Old CI} +% \begin{figure}[!t] +% \centering +% \includegraphics[scale=0.27]{NistAvec.png} +% \DeclareGraphicsExtensions. +% \caption{Résultats du Old CI PRNG} +% \end{figure} +%\end{frame} + + + +%\begin{frame}{DieHard pour les PRNG en entrée} +% \begin{figure}[!t] +% \centering +% \includegraphics[scale=0.27]{DieHardSeul.png} +% \DeclareGraphicsExtensions. +% \caption{DieHard pour 3 PRNG} +% \end{figure} +%\end{frame} + + + + +%\begin{frame}{DieHard pour le Old CI} +% \begin{figure}[!t] +% \centering +% \includegraphics[scale=0.24]{DieHarda.png} +% \DeclareGraphicsExtensions. +% \caption{Résultats du Old CI PRNG} +% \end{figure} +%\end{frame} + + + + +%\begin{frame}{TestU01 pour les PRNG en entrée} +% \begin{figure}[!t] +% \centering +% \includegraphics[scale=0.3]{TestUSeul.png} +% \DeclareGraphicsExtensions. +% \caption{TestU01 pour 3 PRNG} +% \end{figure} +%\end{frame} + + + + + + + + +%\begin{frame}{TestU01 pour le Old CI} +% \begin{figure}[!t] +% \centering +% \includegraphics[scale=0.25]{TestUAvec.png} +% \DeclareGraphicsExtensions. +% \caption{Résultats du Old CI PRNG} +% \end{figure} +%\end{frame} + + + +%\subsection*{Le New CI PRNG} +%\frame{ +% \frametitle{Variantes} +% \begin{block}{Quelques variantes du CI PRNG} +% \begin{itemize} +% \item $New ~CI_f(PRNG_1,PRNG_2)$: éviter de changer deux fois de suite un même bit entre deux outputs +% \begin{itemize} +% \item Ne plus compter le nombre d'itérées entre deux outputs +% \item Mais le nombre de bits à changer +% \end{itemize} +% \item $Xor CI PRNG$: $S^{n+1}=S^n \oplus PRNG^n$ +% \item etc. +% \end{itemize} +% \end{block} +%} + + + + + + +%\begin{frame}{La suite $m$ du New CI} +%Supposons que $x_0 = (0, 0, 0)$. Alors $m_0 \in \llbracket 0, 3 \rrbracket$: on +%peut changer de 0 à 3 bits dans cet état pour produire $x_1$. +%\begin{itemize} +% \item Si $m_0 = 0$, alors aucun bit ne changera entre la première et la +% seconde sortie de notre générateur. Et donc $x_1 = (0, 0, 0)$. +% \item Si $m_0 = 1$, alors exactement 1 bit changera, ce qui conduit à trois +% valeurs possibles pour $x_1$, à savoir (1, 0, 0), (0, 1, 0) et (0, 0, 1). +% \item etc. +%\end{itemize} +%\end{frame} + + + +%\begin{frame}{La suite $m$ du New CI} +%\begin{equation} +%\label{Formula} +%m^n = f(y^n)= +%\left\{ +%\begin{array}{l} +%0 \text{ si }0 \leqslant\frac{y^n}{2^{32}}<\frac{C^0_N}{2^N},\\ +%1 \text{ si }\frac{C^0_N}{2^N} \leqslant\frac{y^n}{2^{32}}<\sum_{i=0}^1\frac{C^i_N}{2^N},\\ +%2 \text{ si }\sum_{i=0}^1\frac{C^i_N}{2^N} \leqslant\frac{y^n}{2^{32}}<\sum_{i=0}^2\frac{C^i_N}{2^N},\\ +%\vdots~~~~~ ~~\vdots~~~ ~~~~\\ +%N \text{ si }\sum_{i=0}^{N-1}\frac{C^i_N}{2^N} \leqslant\frac{y^n}{2^{32}}<1.\\ +%\end{array} +%\right. +%\end{equation} +%\end{frame} + + + + + +%\begin{frame}{Stratégie chaotique} +%Une suite de marquage controlera la suite du XORshift $b$ ainsi: +%\begin{itemize} +%\item si $d^{b^j} \neq 1$, alors $S^k=b^j$, $d^{b^j} = 1$ et $k = k+1$ +%\item si $d^{b^j}=1$, alors $b^j$ est écarté. +%\end{itemize} +%Par exemple, si $b = 142\underline{2}334 +%142\underline{1} \underline{1}\underline{2}\underline{2}34...$ et $m = +%4241...$, alors $S=1423~34~1423~4...$ +%\end{frame} + + + + + + +%%\subsection*{Chaotic iterations as pseudo-random generator} +%% \begin{frame}{CI(XORshift, XORshift) algorithm} +%% \begin{tiny} +%% \begin{table} +%% \centering +%% \begin{tabular}{|l|} +%% \hline +%% ~\textbf{Input}: the internal state $x$ (an array of $\mathsf{N}$ bits)\\ +%% \hline +%% ~\textbf{Output}: a state $r$ of $\mathsf{N}$ bits \\ +%% \hline +%% ~\textbf{for} $i=0,\dots,N$ \textbf{do}\\ +%% ~~~~~~ $d_i\leftarrow{0}$;\\ +%% ~\textbf{end for}\\ +%% ~$a\leftarrow{XORshift1(~)}$;\\ +%% ~$m\leftarrow{f(a)}$\;\\ +%% ~$k\leftarrow{m}$\;\\ +%% ~\textbf{for} $i=0,\dots,k$ \textbf{do}\\ +%% ~~~~~~ $b\leftarrow{XORshift2() mod ~ N}$;\\ +%% ~~~~~~ $S\leftarrow{b}$;\\ +%% ~~~~~~~\textbf{if} $d_S=0$ \textbf{then}\\ +%% ~~~~~~~~~~~~ $x_S\leftarrow{ \overline{x_S}}$;\\ +%% ~~~~~~~~~~~~ $d_S\leftarrow{1}$;\\ +%% ~~~~~~~\textbf{end}\\ +%% ~~~~~~~\textbf{else if} $d_S=1$ \textbf{then}\\ +%% ~~~~~~~~~~~~ $k\leftarrow{k+1}$;\\ +%% ~~~~~~~\textbf{end}\\ +%% ~\textbf{end for}\\ +%% ~$r\leftarrow{x}$\;\\ +%% ~\textbf{return} $r$;\\ +%% \hline +%% +%% \end{tabular} +%% \caption{An arbitrary round of the proposed generator} +%% \label{Chaotic iteration} +%% \end{table} +%% \end{tiny} +%% +%% \end{frame} +%% + + + + + + + + + + + + + + + + +%%\begin{frame}{Exemple du New CI} +%%\begin{block}{} +%%\begin{tabular}{llllll} +%%m:&\uncover<2->{0~} &\uncover<4->{4~~} &\uncover<6->{2 } &\uncover<8->{2}&\uncover<10->{...}\\ +%%k:&\uncover<2->{0~} &\uncover<4->{4~~~~~~+1~} &\uncover<6->{2 } &\uncover<8->{2~+1}&\uncover<10->{...}\\ +%%b:&\uncover<2->{~~} &\uncover<4->{1~4~2~\underline{2}~3} &\uncover<6->{3~4} &\uncover<8->{1~\underline{1}~~~4}&\uncover<10->{...}\\ +%%S:&\uncover<2->{~~} &\uncover<4->{1~4~2~~~~3} &\uncover<6->{3~4} &\uncover<8->{1~~~~~~4}&\uncover<10->{...} +%%\end{tabular} +%%\end{block} +%% +%%\begin{block}{x:} +%%\begin{equation} +%%\label{Basic equations} +%%% \left\{ +%%\begin{array}{r@{\;}l} +%%\ \textbf{0}\uncover<2->{\rightarrow \textbf{0}} \uncover<4->{\rightarrow \textbf{1}\rightarrow 1\rightarrow 1\rightarrow \textbf{1}} \uncover<6->{\rightarrow 1\rightarrow \textbf{1}} \uncover<8->{\rightarrow \textbf{0}\rightarrow \textbf{0}} \uncover<10->{...}\\ +%%\ \textbf{1}\uncover<2->{\rightarrow \textbf{1}} \uncover<4->{\rightarrow 1\rightarrow 1\rightarrow \textbf{0}\rightarrow \textbf{0}} \uncover<6->{\rightarrow 0\rightarrow \textbf{0}} \uncover<8->{\rightarrow 0\rightarrow \textbf{0}} \uncover<10->{...}\\ +%%\ \textbf{0}\uncover<2->{\rightarrow \textbf{0}} \uncover<4->{\rightarrow 0\rightarrow 0\rightarrow 0\rightarrow \textbf{1}} \uncover<6->{\rightarrow \textbf{0}\rightarrow \textbf{0}} \uncover<8->{\rightarrow 0\rightarrow \textbf{0}} \uncover<10->{...}\\ +%%\ \textbf{0}\uncover<2->{\rightarrow \textbf{0}} \uncover<4->{\rightarrow 0\rightarrow \textbf{1}\rightarrow 1\rightarrow \textbf{1}} \uncover<6->{\rightarrow 1\rightarrow \textbf{0}} \uncover<8->{\rightarrow 0\rightarrow \textbf{1}} \uncover<10->{...} +%%\end{array} +%%% \right. +%%\end{equation} +%%\end{block} + +%%\begin{block}{} + +%%\alert{Sortie:} 0 1 0 0 \uncover<3->{0 1 0 0 }\uncover<5->{1 0 1 1 +%%}\uncover<7->{1 0 0 0 }\uncover<9->{0 0 0 1 }\uncover<10->{...} + +%%\end{block} + +%%\end{frame} + + + + + +%\begin{frame}{Nouvelle version de $CI_f(PRNG_1,PRNG_2)$} +% \begin{figure}[!t] +% \centering +% \includegraphics[scale=0.25]{newCI.png} +% \DeclareGraphicsExtensions. +% \caption{Le NEW CI PRNG} +% \end{figure} +%\end{frame} + + + +%\begin{frame}{NIST pour le New CI} +% \begin{figure}[!t] +% \centering +% \includegraphics[scale=0.27]{NistNew.png} +% \DeclareGraphicsExtensions. +% \caption{Résultats du New CI PRNG (Nist)} +% \end{figure} +%\end{frame} + + + + +%\begin{frame}{DieHard pour le New CI} +% \begin{figure}[!t] +% \centering +% \includegraphics[scale=0.24]{DieHardNew.png} +% \DeclareGraphicsExtensions. +% \caption{Résultats du New CI PRNG (DieHard)} +% \end{figure} +%\end{frame} + + + + + + + +%\begin{frame}{TestU01 pour le New CI} +% \begin{figure}[!t] +% \centering +% \includegraphics[scale=0.37]{TestUNew.png} +% \DeclareGraphicsExtensions. +% \caption{Résultats du New CI PRNG (TestU01)} +% \end{figure} +%\end{frame} + + + + + + + +%%\begin{frame}{Premiers tests comparatifs} +%%\begin{tiny} +%%\begin{table}[!t] +%%\renewcommand{\arraystretch}{1.3} +%%\caption{Comparaison avec $2 \times 10^5$ bits} +%%\label{Comparison2} +%%\centering +%% \begin{tabular}{ccccccc} +%% \hline +%%Method & Monobit & Serial & Poker & Runs & Autocorrelation & Time \\ \hline +%%Logistic map &0.1280&0.1302&240.2893&26.5667&0.0373&0.965s \\ +%%XORshift &1.7053&2.1466&248.9318&18.0087&-0.5009&0.096s \\ +%%Old CI(Logistic, Logistic) &1.0765&1.0796&258.1069&20.9272&-1.6994&0.389s \\ +%%New CI(XORshift,XORshift) &0.3328&0.7441&262.8173&16.7877&-0.0805&0.197s\\ +%% \hline +%% \end{tabular} +%%\end{table} +%%\end{tiny} +%%\end{frame} + + + + + + + + +%%\frame{ +%% \frametitle{Résultats au TestU01} +%% \begin{center} +%% \begin{tabular}{|c|c|} +%% \hline +%% PRNG & Échecs (sur 516 tests) \\ +%% \hline +%% Suite logistique & 261 \\ +%% XORshift & 146 \\ +%% ISAAC & 0 \\ +%% \hline +%% Old CI(Logistic,Logistic) & 138 \\ +%% Old CI(XORshift,XORshift) & 9 \\ +%% Old CI(ISAAC,XORshift) & 0 \\ +%% Old CI(ISAAC,ISAAC) & 0 \\ +%% \hline +%% New CI(Logistic,Logistic) & 0 \\ +%% New CI(ISAAC,XORshift) & 0 \\ +%% New CI(ISAAC,ISAAC) & 0 \\ +%% \hline +%% \end{tabular} +%% \end{center} +%%% \begin{figure} +%%% \centering +%%% \includegraphics[scale=0.35]{testU010.png} +%%% \caption{Score de quelques PRNGs au TestU01} +%%% \end{figure} +%%} + + + +%%\frame{ +%% \frametitle{Résultats} +%% \begin{figure} +%% \centering +%% \includegraphics[scale=0.35]{testU011.png} +%% \caption{Améliorations via le $Old CI(PRNG_1,PRNG_2)$} +%% \end{figure} +%%} + + + +%%\frame{ +%% \frametitle{Résultats} +%% \begin{figure} +%% \centering +%% \includegraphics[scale=0.35]{testU012.png} +%% \caption{Améliorations via le $New CI(PRNG_1,PRNG_2)$} +%% \end{figure} +%%} + + + +%\frame{ +% \frametitle{Résultats} +% \begin{figure} +% \centering +% \includegraphics[scale=0.27]{prngs.png} +% \caption{Autres résultats} +% \end{figure} +% } + + + +%\frame{ +% \frametitle{Résultats} +% \begin{figure} +% \centering +% \includegraphics[scale=0.27]{vitesse.png} +% \caption{Perte de vitesse} +% \end{figure} +% } + + +%%\frame{ +%% \frametitle{A quel prix ?} +%% \begin{figure} +%% \centering +%% \includegraphics[scale=0.35]{rapide.png} +%% \caption{Dégradation de la vitesse} +%% \end{figure} +%%} + + + + + + +%\subsection*{Une famille pour le Old CI} + + + +%\frame{ +% \frametitle{Définition d'une famille de Old CI} +%\begin{block}{La matrice associée à $f$} +%Matrice de taille $N\times 2^N$ dont l'élément $(p,q)$ est +%l'entier ayant la décompistion binaire: +%$$q_N, \hdots, q_{N-p}, f(q)_{N-p+1}, q_{N-p+2}, \hdots, q_1$$ +%avec $q_i$: $i-$ième chiffre en base 2 de $q$. +%\end{block} +% + +%\begin{block}{Vecteur des images} +%Le vecteur des images de $f$ est: +%$$\mathcal{F}(f)=(f(0), f(1), \hdots, f(2^N-1)) \in \llbracket 0, 2^N-1 \rrbracket^{2^N}$$ +%\end{block} +%} + + + + +%\frame{ +% \frametitle{Exemple de matrice associée} +% \begin{figure} +% \centering +% \includegraphics[scale=0.27]{mappingMatrix.png} +% \caption{Matrice associée et vecteur des images pour $f_0$} +% \end{figure} +% +%} + + + +%\frame{ +% \frametitle{Une règle pour le Old CI PRNG} +% \begin{itemize} +% \item Supposons que $\mathcal{F}(f)=(f(0), f(1), \hdots, f(2^N-1)) \in \llbracket 0, 2^N-1 \rrbracket^{2^N}$, avec $Old~ CI_f$ équilibré +% \item Si on veut changer $\mathcal{F}(f)_j$ en $C$, alors il faut aussi que $\mathcal{F}(f)_{2^N-C}=2^N-j$ +% \end{itemize} +% +%} + + + + +%\frame{ +% \frametitle{Exemple de fonctions pour le Old CI} +% \begin{figure} +% \centering +% \includegraphics[scale=0.27]{mappingF0.png} +% \caption{Création de nouvelles fonctions équilibrées} +% \end{figure} +% } + + +%\frame{ +% \frametitle{Un théorème pour l'équilibrage} +%\begin{alertblock}{Théorème} +%Soit $f: \mathds{B}^{n} \rightarrow \mathds{B}^{n}$, $\Gamma(f)$ son graphe d'itération, +%$\check{M}$ sa matrice d'adjacence. + +%Si $\Gamma(f)$ est fortement connexe, alors la sortie produite par le Old CI PRNG +%suit une loi qui tend vers l'uniforme répartition si et seulement si $M$ est +%doublement stochastique. +%\end{alertblock} +%} + + + + +%\frame{ +% \frametitle{D'autres Old CI chaotiques} +% \begin{block}{Pour obtenir d'autres Old CI chaotiques} +% \begin{enumerate} +% \item Partir du graphe de tous les possibles de $f_0$ +% \item Tant que le taux ne suppression n'est pas atteint: +% \begin{itemize} +% \item tirer une arête au sort +% \item la supprimer si le graphe reste fortement connexe (algorithme de Tarjan) +% \end{itemize} +% \end{enumerate} +% (Problème avec les graphes isomorphes) +% \end{block} +%} + + +%\frame{ +% \frametitle{Exemple de fonctions pour le Old CI} +% \begin{figure} +% \centering +% \includegraphics[scale=0.27]{SCC.png} +% \caption{Création de nouvelles fonctions au générateur chaotique} +% \end{figure} +% +%} + + + +%\frame{ +% \frametitle{Condition suffisante de chaoticité} +%\begin{alertblock}{Théorème} +%Soit $f$ une fonction de $\mathds{B}^n$ dans lui-même telle que: +%\begin{enumerate} +%\item +%Le graphe de connexion $G(f)$ n'a pas de cycle de longueur au moins 2; +%\item +%Chaque arête de $G(f)$ ayant une boucle positive a aussi une boucle négative; +%\item +%Chaque arête de $G(f)$ est joignable à partir d'un noeud ayant une boucle négative. +%\end{enumerate} +%Alors $\Gamma(f)$ est fortement connexe. +%\end{alertblock} +%} + + + +%%\begin{theorem} +%% Let $f: \mathds{B}^{n} \rightarrow \mathds{B}^{n}$, $\Gamma(f)$ its +%% iteration graph, $\check{M}$ its adjacency +%% matrix and $M$ a $n\times n$ matrix defined as in the previous lemma. +%% If $\Gamma(f)$ is SCC then +%% the output of the PRNG detailed in Algorithm~\ref{CI Algorithm} follows +%% a law that tends to the uniform distribution +%% if and only if $M$ is a double stochastic matrix. +%%\end{theorem} + + +%\subsection*{PRNG cryptographiquement sûr} +% + +%\frame{ +%\frametitle{Les PRNG cryptographiquement sûrs} +%\begin{block}{Définition: Générateur $G$ \emph{cryptographiquement sûr}} +%%Pour tout +%%algorithme probabiliste polynomial en temps $\mathcal{D}$, pour tout +%%polynome $\mathfrak{p}>0$, et pour tout $n$ suffisamment large, +%$$\left| \mathrm{Pr}[\mathcal{D}(\mathcal{G}(\mathfrak{U}_n))=1]-Pr[\mathcal{D}(\mathfrak{U}_{\ell_\mathcal{G}(n)})=1]\right|< \frac{1}{\mathfrak{p}(n)},$$ +%%où $\mathfrak{U}_r$ est la loi de probabilité uniforme sur $\{0,1\}^r$ et les +%%probabilités sont prises sur $\mathfrak{U}_n$, $\mathfrak{U}_{\ell_G(n)}$ de la même manière +%%que pour le lancer d'une pièce de monnaie dans $\mathcal{D}$. +%\end{block} +%} + + + +%\subsection*{Version GPU} + +%\frame{ +%\frametitle{Derniers Résultats} +%\begin{alertblock}{Nos derniers résultats} +%\begin{enumerate} +% \item Si le premier PRNG en entrée est polynomialement indistinguable d'une suite aléatoire, alors notre PRNG l'est aussi +% \item Implantation sur GPU $\Rightarrow$ 20 milliards de nombres (32 bits) par seconde sur un PC +% \item Utilisation de BBS $\Rightarrow$ 1 milliards de nombres sûrs par seconde +% \item Version chaotique du cryptosystème asymétrique probabiliste de Blum-Goldwasser +% \item Mixage avec dispositif optique (Larger, OPTO) +%\end{enumerate} +%\end{alertblock} +%} + + + + + +%%\frame{ +%% \frametitle{Notre générateur GPU} +%% \begin{figure} +%% \centering +%% \includegraphics[scale=0.3]{gpu.png} +%%% \caption{Version GPU de notre générateur} +%% \end{figure} +%%} + + + + +%%\frame{ +%% \frametitle{Notre générateur GPU} +%% \begin{figure} +%% \centering +%% \includegraphics[scale=0.25]{bbs.png} +%% % \caption{Version GPU de notre générateur, avec bbs} +%% \end{figure} +%%} + + + +%\frame{ +% \frametitle{Notre générateur GPU} +% \begin{tabular}{cc} +% \includegraphics[scale=0.3]{gpu.png} & \includegraphics[scale=0.275]{bbs.png} +% \end{tabular} +%} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%\section{Nouvelles pistes} +%%\subsection*{PRNGs} +%\begin{frame}{} +%% 'transition': Crossfade, +% \begin{center} +% \Huge{Nouvelles pistes} + +%\medskip +% %\huge{soulevés par l'approche} +% \end{center} +%\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + + + + + +%\frame{ +% \frametitle{Le générateur optique} +% \begin{block}{Côté OPTO} +% \begin{figure} +% \centering +% \includegraphics[scale=0.5]{setup_opto_RNG.eps} +% \caption{Générateur optique (laser chaotique)} +% \end{figure} +% \end{block} +%} + + + + + + + + + + + +%\frame{ +% \frametitle{Le générateur mixé} +% \begin{block}{Côté DISC} +% \begin{figure} +% \centering +% \includegraphics[scale=0.5]{improve.eps} +% \caption{Mixage analogique-numérique} +% \end{figure} +% \end{block} +%} + + + + + +%\frame{ +% \frametitle{Le générateur mixé} +% \begin{block}{Améliorations (NIST)} +% \begin{figure} +% \centering +% \includegraphics[scale=0.35]{NistLaurent.png} +% \caption{Résultat au NIST} +% \end{figure} +% \end{block} +%} + + + + + +%\frame{ +% \frametitle{Le générateur mixé} +% \begin{block}{Améliorations (DieHARD)} +% \begin{figure} +% \centering +% \includegraphics[scale=0.25]{DieHardLaurent.png} +% \caption{Résultat au DieHARD} +% \end{figure} +% \end{block} +%} + + + +%\frame{ +% \frametitle{Le générateur mixé} +% \begin{block}{Côté DISC} +% \begin{figure} +% \centering +% \includegraphics[scale=0.35]{method.eps} +% \caption{Premier PRNG mixé réalisé} + +% \end{figure} +% \end{block} +%} + + +%\frame{ +% \frametitle{Premiers résultats} +% \begin{tabular}{|l||c|c|c|c|c|} +% \hline +%\textbf{Tests} {\textbf{$n$}}&1 &10&20&30&40 \\ \hline\hline +%NIST suite & 0/15 &14/15 & 15/15 & 15/15 & 15/15\\ \hline +%DieHARD suite &1/18 &11/18 & 14/18 &18/18&18/18\\ \hline +% \end{tabular} +%} + + +%\frame{ +% \frametitle{Le générateur mixé} +% \begin{block}{Côté DISC} +% \begin{figure} +% \centering +% \includegraphics[scale=0.25]{paralel.png} +% \caption{Deuxième PRNG mixé réalisé} +% \end{figure} +% \end{block} +%} + + +%\frame{ +% \frametitle{Une piste ?} +% $$X^{mn+1} = X^{mn} \oplus O^{mn} \oplus C^m$$ +%} + + + + + + + + + +%\begin{frame}{} +% \begin{center} +% \huge{Merci pour votre attention} +% \end{center} +%\end{frame} + + + + + + + + +%%\frame{ +%%% 'transition': Crossfade, +%% \frametitle{Une menace en guise d'illustration} +%% \begin{block}{Les attaques par canal auxiliaire} +%% \begin{enumerate} +%%\item Certains processeurs peuvent laisser fuire de l'information. \newline $\Rightarrow$ En 2006 [Acimez07], 508 bits d'une clé d'authentification sur 512. +%%\item Variation de tension appliquée au processeur [Pellegrini10]\newline $\Rightarrow$ \'Emission d'une signature (RSA 1024) corrompue. +%%\item Mesure du temps de déchiffrement [Kocher95] \newline $\Rightarrow$ Obtention de la clé de déchiffrement. +%%\item Optimisations appliquées au théorème des restes chinois [Brumley03] \newline $\Rightarrow$ Factorisation RSA trouvée. +%%\end{enumerate} +%%\end{block} +%%} + + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + +%%\frame{ +%%% 'transition': Crossfade, +%% \frametitle{Une menace en guise d'illustration} +%% \begin{block}{Les attaques par canal auxiliaire} +%% \begin{itemize} +%% \item Failles matérielles ou logicielles +%% \item Une partie du secret +%% \item Algorithmes prouvés sûrs +%% \end{itemize} +%% \end{block} +%% +%% \vspace{0.25cm} +%% \uncover<2->{ +%% \begin{exampleblock}{Tentatives de solution} +%% \begin{itemize} +%% \item Ne plus répondre au cas par cas +%% \item Une sécurité complémentaire ? +%% \item Pourquoi ne pas utiliser des programmes imprédictibles ? +%% \end{itemize} +%% \end{exampleblock} +%%} +%%} + + + + + + + + +%%\frame{ +%% \frametitle{Nos contributions} +%%\begin{block}{Nos contributions} +%%\begin{itemize} +%%\item Construire des machines, des programmes imprévisibles +%%\item Etudier des algorithmes existants sous d'autres aspects (comparaison, autres menaces ?) +%%\item Rajouter des propriétés (topologiques) à des outils préexistants, \emph{sans perte de sécurité} +%% \end{itemize} +%%\end{block} +%%} + + + + + + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%\section*{Problèmes} +%\begin{frame}{} +%% 'transition': Crossfade, +% \begin{center} +% \Huge{Problèmes} + +%\medskip +% \huge{soulevés par l'approche} +% \end{center} +%\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + + + + + +%% %%%%%%%%%%%%% 16. De la relativité du chaos %%%%%%%%%%%%%%% +%\subsection*{Tout est relatif (est-ce encore vrai ?)} + +%% \frame{ +%% \frametitle{Problème soulevé par l'approche} +%% \begin{block}{Quels problèmes pose cette approche ?} +%% \begin{itemize} +%% \item Rôle prépondérant de la topologie +%% \item De sa finesse dépendent les propriétés de désordre +%% \item Comment bien la choisir ? +%% \end{itemize} +%% $\Rightarrow$ Se ramener à la topologie de l'ordre sur $\mathds{R}$ +%% \end{block} +%% } + + +%\frame{ +% \frametitle{De l'importance de la topologie} +%%\begin{block}{Les questions qui se posent} +%%\begin{enumerate} +%%\item Si un système $(\mathcal{X},f)$ est chaotique, et pour quelle topologie. +%%\item Si un système $(\mathcal{X},f)$ est plus chaotique qu'un système $(\mathcal{Y},g)$. +%%\end{enumerate} +%%\end{block} + +%%\vspace{0.5cm} +%%\uncover<2>{ +%\begin{exampleblock}{Problèmes soulevés} +%\begin{enumerate} +%\item Le désordre dépend de la topologie (?) +%\item Comparaison de deux systèmes: +%\begin{itemize} +%\item Les ensembles $\mathcal{X}$ et $\mathcal{Y}$ ne sont pas forcément les mêmes. +%\item Les topologies ne sont pas forcément les mêmes. +%\item Sont-elles comparables ? Et quelles conséquences ? +%\end{itemize} +%\end{enumerate} +%\end{exampleblock} +%%} +%} + + + +%\frame{ +% \frametitle{Mon désordre n'est pas le tien} +% \begin{exampleblock}{Théorème: Impact de la finesse de la topologie} +% Soient $\tau, \tau'$ deux topologies sur $\mathcal{X}$ telles que $\tau \subset \tau'$. + +%Si $(\mathcal{X}_{\tau'},f)$ satisfait Devaney, alors $(\mathcal{X}_\tau,f)$ aussi. +% \end{exampleblock} +%} + +%\frame{ +% \frametitle{Mon désordre n'est pas le tien} +% \begin{exampleblock}{Un système peut toujours être chaotique} +% Soit $\mathcal{X}$ un ensemble non vide, et $f: \mathcal{X} \to \mathcal{X}$ une application possédant au moins un point fixe. +%Alors $f$ est $\tau_0-$chaotique, où $\tau_0$ est la topologie grossière sur $\mathcal{X}$. +% \end{exampleblock} +% +% \vspace{0.5cm} +% +% \begin{exampleblock}{Un système peut toujours ne jamais être chaotique} +%Soit $\mathcal{X}$ un ensemble, et $f: \mathcal{X} \to \mathcal{X}$ une application. +%Si $\mathcal{X}$ est infini, alors $\left( \mathcal{X}_{\tau_\infty}, f\right)$ n'est pas chaotique selon Devaney, où $\tau_\infty$ désigne la topologie discrète. +% \end{exampleblock} +%} + + + + + +%\frame{ +% \frametitle{Réflexions autour d'un désordre absolu} +% \begin{block}{Reformulation des problèmes} +% \begin{itemize} +% \item $(\mathcal{X},f)$ peut ou non être chaotique, suivant la richesse de la topologie. +% \item L'ensemble des topologies sur $\mathcal{X}$, muni de la relation « être plus fine que » est un espace réticulé. +% \end{itemize} +% \end{block} +% +% \vspace{0.4cm} +% +% \begin{block}{Quelques pistes} +% \begin{enumerate} +% \item La plus fine topologie rendant une fonction imprédictible +% \item \^Etre imprédictible, c'est l'être pour la topologie de l'ordre. +% \begin{itemize} +% \item Approche légitime (mais, pour quel ordre ?) +% \item Peut conduire à se ramener à $\mathds{R}$ +% \end{itemize} +% \end{enumerate} +% \end{block} +%} + + +%%%%%%%%%%%%%%% 17. Une semi-conjugaison topologique %%%%%%%% +%%%%%%%%%% ou comment passer de X à un intervalle réel %%%%%% +%\subsection*{Une semi-conjugaison topologique} + + + +%\frame{ +% \frametitle{Une semi-conjugaison topologique} +% +% +%\begin{exampleblock}{Une semi-conjugaison topologique} +%IC $G_{f_0}$ sur $\mathcal{X}$ = IC $g$ sur $\mathds{R}$: +%\begin{equation*} +%\begin{CD} +%\left(~\mathcal{S}_{10} \times\mathds{B}^{10}, d~\right) @>G_{f_0}>> \left(~\mathcal{S}_{10} \times\mathds{B}^{10}, d~\right)\\ +% @V{\varphi}VV @VV{\varphi}V\\ +%\left( ~\big[ 0, 2^{10} \big[, D~\right) @>>g> \left(~\big[ 0, 2^{10} \big[, D~\right) +%\end{CD} +%\end{equation*} +%\begin{enumerate} +%\item Prendre la première décimale $d$ de $x \in \big[ 0, 2^{10} \big[$ +%\item Nier le bit numéro $d$ de $E(x)$ +%\item Supprimer $d$ +%\end{enumerate} +%\end{exampleblock} +%} + + + + +%\frame{ +% \frametitle{Comparaison des distances} + +%\begin{exampleblock}{Comparaison de distances} +%$D$ est plus fine que la distance euclidienne. +%\end{exampleblock} + +%\begin{figure}[t] +%\begin{center} +% \subfigure[Application $x \to dist(x;1,234)$.]{\includegraphics[scale=.25]{17.Semi_conjugaison_topologique/distances/DvsEuclidien.pdf}}\quad +% \subfigure[Application $x \to dist(x;3) $.]{\includegraphics[scale=.25]{17.Semi_conjugaison_topologique/distances/DvsEuclidien2.pdf}} +%\end{center} +%\caption{Comparaison des distances $D$ et euclidienne.} +%\label{fig:comparaison de distances} +%\end{figure} +%} + + + + + + + + +%\frame{ +% \frametitle{\'Etude des ICs sur $\mathds{R}$} +% \begin{exampleblock}{Analyse des itérations chaotiques réelles} +%Les itérations chaotiques $g$ définies sur $\mathds{R}$ sont: +%\begin{itemize} +%\item Infiniment dérivables sur $\big[ 0, 2^{10} \big[$, sauf aux 10241 points de l'ensemble $I$ défini par $\left\{ \dfrac{n}{10} ~\big/~ n \in \llbracket 0;2^{10}\times 10\rrbracket \right\}$. +%\item Affine, de pente 10, sur chaque sous-intervalle. +%\end{itemize} +%\end{exampleblock} +%} + + + +%%\frame{ +%% \frametitle{Exemples de fonctions chaotiques} +%%\begin{figure}[t] +%%\begin{center} +%% \subfigure[Doublement de l'angle.]{\includegraphics[scale=.16]{17.Semi_conjugaison_topologique/fonctions/doublement.pdf}}\quad +%% \subfigure[Fonction logistique.]{\includegraphics[scale=.16]{17.Semi_conjugaison_topologique/fonctions/logistique.pdf}}\quad +%% \subfigure[Fonction tente.]{\includegraphics[scale=.16]{17.Semi_conjugaison_topologique/fonctions/tente.pdf}} +%%\end{center} +%%\caption{Exemples de fonctions chaotiques.} +%%\end{figure} +%%} + + + + + +%\frame{ +% \frametitle{Les itérations chaotiques $G_{f_0}$ sur $\mathds{R}$} +%\begin{figure}[t] +%\begin{center} +%% \subfigure[Sur (0,9 ; 1).]{\includegraphics[scale=.16]{17.Semi_conjugaison_topologique/fonctions/ICs09a1.pdf}}\quad +% \subfigure[Sur (0,7 ; 1).]{\includegraphics[scale=.16]{17.Semi_conjugaison_topologique/fonctions/ICs07a95.pdf}}\quad +% \subfigure[Sur (0 ; 1).]{\includegraphics[scale=.19]{17.Semi_conjugaison_topologique/fonctions/ICs0a1.pdf}}\quad +% \subfigure[Sur (510 ; 514).]{\includegraphics[scale=.19]{17.Semi_conjugaison_topologique/fonctions/ICs510a514.pdf}}\quad +% \subfigure[Sur (1000 ; 1008).]{\includegraphics[scale=.19]{17.Semi_conjugaison_topologique/fonctions/ICs1000a1008.pdf}} +%\end{center} +%\caption{Les itérations chaotiques.} +%\end{figure} +%} + + + + +%\frame{ +% \frametitle{Les itérations chaotiques sur $\mathds{R}$} +%\begin{figure}[t] +%\begin{center} +% \subfigure[Sur (510 ; 514).]{\includegraphics[scale=.16]{17.Semi_conjugaison_topologique/fonctions/ICs510a514.pdf}}\quad +% \subfigure[Sur (1000 ; 1008).]{\includegraphics[scale=.16]{17.Semi_conjugaison_topologique/fonctions/ICs1000a1008.pdf}}\quad +% \subfigure[Sur (40 ; 70).]{\includegraphics[scale=.16]{17.Semi_conjugaison_topologique/fonctions/ICs40a70.pdf}} +%\end{center} +%\caption{Les itérations chaotiques.} +%\end{figure} +%} + + + + + + +% \frame{ +% \frametitle{Chaos des IC $G_{f_0}$ sur $\mathds{R}$} +% \begin{exampleblock}{Chaos de Devaney sur $\mathds{R}$} +% Les IC sur $\mathds{R}$ sont chaotiques selon Devaney, quand $\mathds{R}$ a sa topologie usuelle. +% \end{exampleblock} + +% \vspace{0.5cm} + +% \begin{exampleblock}{Exposant de Lyapunov} +% %$\forall x^0 \in \mathcal{L}$, l'exposant de Lyapunov des itérations chaotiques ayant $x^0$ pour condition initiale vaut +% $$\forall x^0 \in \mathcal{L}, \lambda(x^0) = \displaystyle{\lim_{n \to +\infty} \dfrac{1}{n} \sum_{i=1}^n \ln \left| ~g'\left(x^{i-1}\right)\right|} = \ln (10).$$ +% \end{exampleblock} +% } + + + + + + + + + + + + +%\frame{ +% \frametitle{Systèmes itératifs et suites récurrentes} +% \begin{alertblock}{Les systèmes itératifs sont des suites récurrentes} +% On pose $F:\mathcal{X}^\mathds{N} \longleftrightarrow\mathcal{X}^\mathds{N}$, qui à la suite $(x^k)_{k \in \mathds{N}}$ associe $\left(x^0, f^0(x^0), f^1(x^0,x^1), f^2(x^0,x^1,x^0),\hdots\right)$. Alors le système +% $$\left\{ +% \begin{array}{l} +% X^0 = (x^0,0,0, \hdots) \in \mathcal{X}^\mathds{N}\\ +% X^{n+1} = F(X^n) +% \end{array} +% \right.$$ +% tend vers la suite $(x^0,x^1,x^2,\hdots)$. +% \end{alertblock} +% \uncover<2->{ +% Etudions un cas particulier : les « Itérations chaotiques »} +%} + +\section{Conclusion} + + +\bibliographystyle{plain} +\bibliography{mabase} \end{document}