review_prng.tex

   1 \documentclass{article}
   2 \usepackage[utf8x]{inputenc}
   3 \usepackage[standard]{ntheorem}
   4 \usepackage[english]{babel}
   5
   6 \usepackage{stmaryrd}
   7 \usepackage{amsmath}
   8 \usepackage{color}
   9 \usepackage{dsfont}
  10
  11
  12
  13 \title{A Review of Chaotic Iteration Based Pseudorandom Number Generators}
  14 \author{Jacques M. Bahi, Jean-Fran\c cois Couchot, Raphaël Couturier, and Christophe Guyeux~\thanks{Authors in alphabetic order}}
  15
  16
  17
  18 \begin{document}
  19
  20 \maketitle
  21
  22 \begin{abstract}
  23
  24 \end{abstract}
  25
  26
  27 \section{Introduction}
  28
  29
  30 \section{Topologycal Study of Disorder}
  31
  32 \subsection{Historical Context}
  33
  34 Pseudorandom number generators are recurrent sequences having a disordered behavior.
  35
  36 Recurrent sequences, also called discrete dynamical systems, of the form
  37 \begin{equation}
  38 \label{sdd}
  39 u^0 \in \mathds{R}, u^{n+1} = f(u^n),
  40 \end{equation}
  41 with
  42 $f$ continuous, have been well studied since the early years of mathematical
  43 analysis. They are widely used, for instance to resolve equations using a
  44 Newton method, or when approximating the solutions to differential equations
  45 using finite difference equations to approximate derivatives.
  46 The context study was the seek for convergence, which is for instance guarantee
  47 when using monotonic functions or contractions.
  48 In the middle of the last century, Coppel has
  49 established a link between this desire of convergence
  50 and the existence of a cycle in iterations~\cite{Coppel55}.
  51 More precisely, his theorem states that, considering Eq.~\eqref{sdd} with a function
  52 $f:I \longrightarrow I$ continuous on the line segment $I$, the absence of
  53 any 2-cycle implies the convergence of the discrete dynamical system.
  54
  55 This theorem establish a clear link between the existence of a cycle of
  56 a given length and the convergence of the system. In other words, between
  57 cycles and order. Conversely, Li and Yorke have established in 1975~\cite{Li75} that
  58 the presence of a point of period three implies chaos in the same situation
  59 than previously. By chaos, they mean the existence of points of any
  60 period: this kind of disorder, which is the first occurrence of the
  61 term ``chaos'' in the mathematical litterature, is thus related to the
  62 multiplicity of periods. Since that time, the mathematical theory of
  63 chaos has known several developments to qualify or quantify the richness
  64 of chaos presented by a given discrete dynamical system, one of the most
  65 famous work, although old, being the one of Devaney~\cite{devaney}.
  66
  67 \subsection{Iterative Systems}
  68
  69 In the distributed computing community, dynamical systems have been
  70 generatized to take into account delay transmission or heterogeneous
  71 computational powers. Mathematically, the intended result is often one
  72 fixed point resulting from the iterations of a given function over a
  73 Boolean vector, considering that:
  74 \begin{itemize}
  75 \item at time $t$, $x^{t}$ is computed using not only $x^{t-1}$, but
  76 potentially any $x^{k}, k<t$, due to delay transmission,
  77 \item not all the components of $x^{t}$ are supposed to be updated at
  78 each iteration: each component represents a unit of computation, and
  79 these units have not the same processing frequency.
  80 \end{itemize}
  81
  82 These considerations lead to the following definition of an iterative
  83 system~\cite{GuyeuxThese10}.
  84
  85 \begin{definition}
  86 Iterative systems on a set $\mathcal{X}$ are defined by
  87 $$\left\{
  88   \begin{array}{l}
  89     x^0 \in \mathcal{X}\\
  90     x^{n+1} = f^n(x^0, \hdots, x^n)
  91   \end{array}
  92  \right.$$
  93 where $f^n:\mathcal{X}^{n+1}\rightarrow \mathcal{X}$.
  94 \end{definition}
  95
  96 Some particular cases of these iterative systems are well documented,
  97 namely the serial, parallel, or chaotic modes.
  98 In the serial mode, each component is updated one by one, whereas the
  99 parallel mode consists in updating all the components at each iteration,
 100 leading to an usual discrete dynamical system.
 101 These modes are compliant with the definition above,
 102 as the parallel mode consists in considering that the sequence
 103 $f^n$ defined above is constant equal to a given $f: \mathcal{X}
 104 \longrightarrow \mathcal{X}$,
 105 whereas the serial mode can be rewritten as parallel iterations of
 106 $$ G=F_\mathsf{N} \circ \ldots \circ F_2 \circ F_1 $$
 107 where, $\forall i \in \llbracket 1, \mathsf{N} \rrbracket $:
 108 $$\begin{array}{rccc}
 109 F_i: & \mathcal{X} & \longrightarrow & \mathcal{X}\\
 110         & (x_1, \hdots, x_\mathsf{N}) & \longmapsto & \left(x_1, \hdots, x_{i-1},f_i\left(x_1, \hdots, x_\mathsf{N}\right), x_{i+1}, \hdots, x_\mathsf{N}\right).
 111 \end{array}$$
 112
 113
 114
 115 Finally, iterative systems in chaotic mode, simply called chaotic iterations,
 116 are defined as follows~\cite{Robert}.
 117
 118
 119 \begin{definition}
 120 Let $f: \mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N}$ and
 121 $S \subset \mathcal{P} \left(\llbracket1,\mathsf{N}\rrbracket\right)^\mathds{N}$.
 122 \emph{Chaotic iterations} $(f, (x^0, S))$ are defined by:
 123 $$\left\{
 124 \begin{array}{l}
 125 x^0 \in \mathds{B}^\mathsf{N} \\
 126 \forall n \in \mathds{N}^*, \forall i \in \llbracket 1; \mathsf{N} \rrbracket,  x^{n}_i = \left\{
 127 \begin{array}{ll}
 128 x^{n-1}_{i} & \textrm{ if } i \notin S^n\\
 129 f(x^{n-1})_{i} & \textrm{ if } i \in S^n
 130 \end{array}
 131 \right.
 132 \end{array}
 133 \right.$$
 134 \end{definition}
 135
 136 \emph{A priori}, there is no relation between these chaotic iterations
 137 and the mathematical theory of chaos recalled in the previous section.
 138 On our side, we have regarded whether these chaotic iterations can
 139 behave chaotically, as it is defined for instance by Devaney, and if so,
 140 in which applicative context this behavior can be profitable.
 141 This questioning has led to a first necessary condition of non convergence~\cite{GuyeuxThese10}.
 142
 143 \begin{proposition}
 144 Let $f : \mathds{B}^\mathsf{N} \to \mathds{B}^\mathsf{N}$ and
 145 $S \in \llbracket 1, \mathsf{N} \rrbracket^{\mathds{N}}$.
 146 If the chaotic iterations $\left(f,(x^0,S)\right)$ are not convergent, then:
 147 \begin{itemize}
 148 \item either $f$ is not a contraction, meaning that there is no Boolean matrix
 149     $M$ of size $\mathsf{N}$ satisfying $\forall x,y\in \mathds{B}^\mathsf{N}$,
 150     $d(f(x),f(y)) \leqslant M d(x,y)$, where $d$ is here the ``vectorial distance''
 151     defined by $d(x,y) = \left(\begin{array}{c} \delta(x_1,y_1)\\ \vdots \\ \delta(x_\mathsf{N},
 152     y_\mathsf{N}) \end{array}\right)$, with $\delta$ the discrete metric defined by $\delta(x,y) = \left\{\begin{matrix} 1 &\mbox{if}\ x\neq y , \\ 0 &\mbox{if}\ x = y \end{matrix}\right.$, and $\leqslant$ is the inequality term by term~\cite{Robert}.
 153 \item or $S$ is not pseudo-periodic: it is not constituted by an infinite succession of finite sequences, each having any element of $\llbracket
 154     1, \mathsf{N} \rrbracket$ at least once.
 155 \end{itemize}
 156 \end{proposition}
 157
 158 The second alternative of the proposition above concerns the strategy,
 159 which should be provided by the outside world. Indeed, in our opinion,
 160 chaotic iterations can receive a PRNG $S$ as input, and due to
 161 properties of disorder of $f$, generate a new pseudorandom sequence
 162 that presents better statistical properties than $S$. Having this
 163 approach in mind, we thus have searched vectorial Boolean iteration
 164 functions that are not contractions. The vectorial negation function
 165 $f_0:\mathds{B}^\mathsf{N} \longrightarrow \mathds{N}^\mathsf{N},$
 166 $(x_1, \hdots, x_\mathsf{N}) \longmapsto (\overline{x_1}, \hdots,
 167 \overline{x_\mathsf{N}}) $ is such a function, which served has a
 168 model in our further studies ($\overline{x}$ stands for the negation
 169 of the Boolean $x$).
 170
 171 The quantity of disorder generated by such chaotic iterations, when
 172 satisfying the proposition above, has then been measured. To do so,
 173 chaotic iterations have first been rewritten as simple discrete
 174 dynamical systems, as follows.
 175
 176
 177 \subsection{Chaotic Iterations as Dynamical Systems}
 178
 179 The problems raised by such a formalization can be summarized as
 180 follows.
 181 Chaotic iterations are defined in the discrete mathematics framework,
 182 considering $x^0 \in \mathds{B}^\mathds{N}$ and $S \in \mathcal{S} = \llbracket 1,\mathsf{N}\rrbracket^\mathds{N}$, and iterations having the
 183 form
 184 $$x_i^{n+1} = \left\{ \begin{array}{ll} x^{n}_{i} & \textrm{ si } i \neq S^n\\ f(x^{n})_{i} & \textrm{ si } i = S^n \end{array} \right.$$
 185 where $f: \mathds{B}^\mathsf{N} \to \mathds{B}^\mathsf{N}$.
 186 However, the mathematical theory of chaos takes place into a
 187 topological space $(\mathcal{X},\tau)$. It studies the iterations
 188 $x^0 \in \mathcal{X}$, $\forall n \in \mathds{N}, x^{n+1} = f(x^n)$,
 189 where $f : \mathcal{X} \to \mathcal{X}$ is continuous for the
 190 topology $\tau$.
 191
 192 To realize the junction between these two frameworks, the following
 193 material has been introduced~\cite{GuyeuxThese10,bgw09:ip}:
 194 \begin{itemize}
 195 \item the shift function: $\sigma : \mathcal{S} \longrightarrow \mathcal{S}, (S^n)_{n \in \mathds{N}} \mapsto (S^{n+1})_{n \in \mathds{N}}$.
 196 \item the initial function, defined by $i : \mathcal{S} \longrightarrow \llbracket 1 ; \mathsf{N} \rrbracket, (S^n)_{n \in \mathds{N}} \mapsto S^0$
 197 \item and $F_f : \llbracket 1 ; \mathsf{N} \rrbracket \times \mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N},$ $$(k,E) \longmapsto  \left( E_j.\delta(k,j) + f(E)_k.\overline{\delta (k,j)} \right)_{j \in \llbracket 1 ; \mathsf{N} \rrbracket}$$
 198 \end{itemize}
 199 where $\delta$ is the discrete metric.
 200
 201
 202
 203
 204 Let $\mathcal{X} = \llbracket 1 ; \mathsf{N} \rrbracket^\mathds{N} \times \mathds{B}^\mathsf{N},$ and $G_f\left(S,E\right) = \left(\sigma(S), F_f(i(S),E)\right).$
 205 Chaotic iterations $\left(f, (S,x^0)\right)$ can be modeled by the
 206 discrete dynamical system:
 207 $$\left\{
 208 \begin{array}{l}
 209 X^0 = (S,x^0) \in \mathcal{X}, \\
 210 \forall k \in \mathds{N}, X^{k+1} = G_f(X^k).
 211 \end{array}
 212 \right.$$
 213 Their topological disorder can then be studied.
 214 To do so, a relevant distance must be defined of $\mathcal{X}$, as
 215 follows~\cite{GuyeuxThese10,bgw09:ip}:
 216 $$d((S,E);(\check{S};\check{E})) = d_e(E,\check{E}) +  d_s(S,\check{S})$$
 217 \noindent where $\displaystyle{d_e(E,\check{E}) = \sum_{k=1}^\mathsf{N} \delta (E_k, \check{E}_k)}$, ~~and~ $\displaystyle{d_s(S,\check{S}) = \dfrac{9}{\textsf{N}} \sum_{k = 1}^\infty \dfrac{|S^k-\check{S}^k|}{10^k}}$.
 218
 219 This new distance has been introduced in \cite{bgw09:ip} to satisfy the following requirements.
 220 \begin{itemize}
 221 \item When the number of different cells between two systems is increasing, then their distance should increase too.
 222 \item In addition, if two systems present the same cells and their respective strategies start with the same terms, then the distance between these two points must be small because the evolution of the two systems will be the same for a while. Indeed, the two dynamical systems start with the same initial condition, use the same update function, and as strategies are the same for a while, then components that are updated are the same too.
 223 \end{itemize}
 224 The distance presented above follows these recommendations. Indeed, if the floor value $\lfloor d(X,Y)\rfloor $ is equal to $n$, then the systems $E, \check{E}$ differ in $n$ cells. In addition, $d(X,Y) - \lfloor d(X,Y) \rfloor $ is a measure of the differences between strategies $S$ and $\check{S}$. More precisely, this floating part is less than $10^{-k}$ if and only if the first $k$ terms of the two strategies are equal. Moreover, if the $k^{th}$ digit is nonzero, then the $k^{th}$ terms of the two strategies are different.
 225
 226 It has then be stated that
 227 \begin{proposition}
 228 $G_f : (\mathcal{X},d) \to  (\mathcal{X},d)$ is a continuous function
 229 \end{proposition}
 230
 231 With all this material, the study of chaotic iterations as a discrete
 232 dynamical system has then be realized.
 233 This study is summarized in the next section.
 234
 235 \subsection{Topological Properties of Chaotic Iterations}
 236
 237 The topological space on which chaotic iterations are defined has
 238 firstly been investigated, leading to the following result~\cite{gb11:bc,GuyeuxThese10}:
 239 \begin{proposition}
 240 $\mathcal{X}$ is an infinitely countable metric space, being both
 241 compact, complete, and perfect (each point is an accumulation point).
 242 \end{proposition}
 243 These properties are required in some topological specific
 244 formalization of a chaotic dynamical system, justifying their
 245 proofs.
 246
 247 Concerning $G_{f_0}$, it has been stated that~\cite{GuyeuxThese10}.
 248 \begin{proposition}
 249 $G_{f_0}$ is surjective, but not injective, and so the dynamical system $(\mathcal{X},G_{f_0})$ is not reversible.
 250
 251 Furthermore, if we denote by $Per_k(f)$ the set of periodic points
 252 of period $k$ for $f$, we have
 253  $\forall k \in \mathds{N}, Per_{2k+1}(G_{f_0}) = \varnothing, card\left(Per_{2k+2}(G_{f_0})\right)>0$.
 254 \end{proposition}
 255
 256 So $\Rightarrow G_{f_0}$ does not present the existence of points of any period referred as chaos in the article of Li and Yorke~\cite{Li75}.
 257 However~\cite{GuyeuxThese10}:
 258      \begin{itemize}
 259        \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}$.
 260        \item $G_{f_0}$ possesses more than $n^2$ points of period $2n$.
 261      \end{itemize}
 262 Additionally, this existence of points of any period has been rejected
 263 by the community to the benefit of more recent notions of chaos, as
 264 they are detailed in the following paragraphs.
 265
 266
 267
 268 %\subsection*{Approche type Devaney/Knudsen}
 269
 270 %\frame{
 271 %  \frametitle{Les approches Devaney et Knudsen}
 272 %  \begin{block}{3 propriétés pour de l'imprévisibilité}
 273 %    \begin{enumerate}
 274 %      \item \emph{Indécomposabilité.} On ne doit pas pouvoir simplifier le système
 275 %      \begin{itemize}
 276 %        \item Impossible de diviser pour régner
 277 %        \item Des orbites doivent visiter tout l'espace
 278 %      \end{itemize}
 279 %      \item \emph{Élément de régularité.}
 280 %      \begin{itemize}
 281 %        \item Contrecarre l'effet précédent
 282 %        \item Des points proches \textit{peuvent} se comporter complètement différemment
 283 %      \end{itemize}
 284 %      \item \emph{Sensibilité.} Des points proches \textit{peuvent} finir éloignés
 285 %    \end{enumerate}
 286 %  \end{block}
 287 %}
 288
 289
 290 %\frame{
 291 % \frametitle{Exemple : définition de Devaney}
 292 %\begin{enumerate}
 293 %\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$
 294 %\item \emph{Régularité:} Les points périodiques sont denses
 295 %\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$$
 296 %\end{enumerate}
 297 %}
 298
 299 %\frame{
 300 %   \frametitle{Systèmes intrinsèquement compliqués}
 301 %   \begin{block}{Définitions de l'indécomposabilité}
 302 %   \begin{itemize}
 303 %     \item \emph{Indécomposable}: pas la réunion de deux parties non vides, fermées et t.q. $f(A) \subset A$
 304 %     \item \emph{Totalement transitive}: $\forall n \geqslant 1$, l'application composée $f^{(n)}$ est transitive.
 305 %     \item \emph{Fortement transitif}:
 306 %$\forall x,y \in \mathcal{X},$ $\forall r>0,$ $\exists z \in B(x,r),$ $\exists n \in \mathbb{N},$ $f^{(n)}(z)=y.$
 307 %     \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$.
 308 %   \end{itemize}
 309 %   \end{block}
 310 %}
 311
 312
 313
 314
 315 %\frame{
 316 %\frametitle{Stabilité et expansivité}
 317 %   \begin{block}{Définitions de la sensibilité}
 318 %     \begin{itemize}
 319 %       \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$
 320 %       \item $(\mathcal{X},f)$ est \emph{expansif} si
 321 %$\exists \varepsilon >0,$ $\forall x \neq y,$ $\exists n \in \mathbb{N},$ $d(f^{(n)}(x),f^{(n)}(y)) \geqslant \varepsilon$
 322 %     \end{itemize}
 323 %   \end{block}
 324 %}
 325
 326 %%\frame{
 327 %%  \frametitle{Des systèmes imprévisibles}
 328 %%    \begin{block}{Définitions des systèmes dynamiques désordonnés}
 329 %%    \begin{itemize}
 330 %%      \item \emph{Devaney:} $(\mathcal{X},f)$ est sensible aux conditions initiales, régulier et transitif
 331 %%       \item \emph{Wiggins:} $(\mathcal{X},f)$ est transitif et sensible aux conditions initiales
 332 %%       \item \emph{Knudsen:} $(\mathcal{X},f)$ a une orbite dense et s'il est sensible aux conditions initiales
 333 %%       \item \emph{expansif:} $(\mathcal{X},f)$ est transitif, régulier et expansif
 334 %%    \end{itemize}
 335 %%    \end{block}
 336 %%}
 337
 338
 339
 340 %\subsection*{Autres approches}
 341
 342
 343 %\frame{
 344 %  \frametitle{Selon Li et Yorke}
 345 %    \begin{block}{Définitions}
 346 %    \begin{description}
 347 %\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.$
 348
 349 %\item[Ensemble brouillé.] $B \subset \mathcal{X}$ en est un si tout couple de points distincts de $B$ est de Li-Yorke.
 350
 351 %\item[Systèmes de Li-Yorke.] $\mathcal{X}$ est compact et contient un ensemble brouillé indénombrable.
 352 %\end{description}
 353 %\end{block}
 354 %}
 355
 356
 357
 358
 359
 360
 361 %\frame{
 362 % \frametitle{Approche entropie topologique}
 363 %   \begin{block}{Entropie topologique}
 364 %   \begin{itemize}
 365 %   \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$.
 366 %   \item Les ensembles $(n,\varepsilon)-$séparé sont des ensembles de points qui seront tous $\varepsilon-$séparés en temps $n$
 367 %   \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]}$$
 368 %   \end{itemize}
 369 %   \end{block}
 370 %}
 371
 372
 373
 374
 375 %\frame{
 376 % \frametitle{Exposant de Lyapunov}
 377 %\begin{block}{L'exposant de Lyapunov}
 378 %$$\lambda(x^0) = \displaystyle{\lim_{n \to +\infty} \dfrac{1}{n} \sum_{i=1}^n \ln \left| ~f'\left(x^{i-1}\right)\right|}$$
 379 %Il doit être positif pour multiplier les erreurs
 380 %\end{block}
 381 %}
 382
 383
 384
 385
 386
 387 %\subsection*{Etude des systèmes itératifs}
 388
 389 %%\frame{
 390 %%  \frametitle{IC et propriété de Devaney}
 391 %%\begin{alertblock}{Théorème}
 392 %%$G_{f_0}$ est régulier et transitif (Devaney).
 393
 394 %%Sa sensibilité est $\geqslant \mathsf{N}-1$.
 395 %%\end{alertblock}
 396
 397 %%\uncover<2->{
 398 %% \begin{exampleblock}{Question}
 399 %% $f_0$ est-elle la seule fonction dont le système itératif vérifie la condition de Devaney ?
 400 %% \end{exampleblock}
 401 %%
 402 %% \vspace{0.5cm}
 403
 404 %%Pour y répondre, nous avons utilisé le graphe de tous les possibles par itérations chaotiques : le GTPIC.}
 405 %%}
 406
 407
 408
 409
 410 %%\frame{
 411 %%  \frametitle{Nombre de fonctions imprévisibles}
 412 %%  \begin{alertblock}{Caractérisation des IC imprévisibles selon Devaney}
 413 %%$G_f$ vérifie l'hypothèse de Devaney $\Leftrightarrow$ Son graphe des possibles est fortement connexe.
 414
 415 %%$\Rightarrow$ Il y a $\left(2^\mathsf{N}\right)^{2^\mathsf{N}}$ IC chaotiques.
 416 %%\end{alertblock}
 417 %%}
 418
 419
 420
 421
 422
 423
 424
 425 %\frame{
 426 %  \frametitle{Etude topologique}
 427 %    \begin{exampleblock}{Etude topologique des ICs}
 428 %      \begin{itemize}
 429 %        \item $\forall f \in \mathcal{C}$, $Per\left(G_f\right)$ est infini dénombrable, $G_f$ est fortement transitive,  est chaotique selon Knudsen,
 430 %        \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})$
 431 %        \item Indécomposabilité, instabilité, chaos de Wiggins, de la multiplicité des périodes...
 432 %      \end{itemize}
 433 %    \end{exampleblock}
 434 %}
 435
 436
 437
 438
 439
 440
 441
 442 %\frame{
 443 % \frametitle{Graphe de tous les possibles par IC}
 444 %  \begin{center}
 445 %   \includegraphics[scale=0.55]{14.Caracterisation_des_IC_chaotiques_selon_Devaney/grapheTPICver2.pdf}
 446 %  \end{center}
 447 %}
 448
 449
 450
 451
 452
 453
 454
 455
 456
 457
 458
 459
 460
 461
 462
 463
 464
 465
 466
 467 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 468 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 469 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 470 %\section*{Topologie des programmes}
 471 %\frame{
 472 %% 'transition': Crossfade,
 473 % \begin{center}
 474 %   \Huge{Topologie des programmes}
 475 %
 476 %  \end{center}
 477 %}
 478 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 479 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 480 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 481
 482
 483
 484 %%\frame{
 485 %%  \frametitle{Premières questions}
 486 %%  \begin{exampleblock}{Le chaos dans mon PC ?}
 487 %%  Le désordre, l'imprévisibilité (vrai, sans perte) sont-ils possibles sur un ordinateur ?
 488 %%\begin{itemize}
 489 %%      \item Il n'y a pas de réels sur mon PC
 490 %%      \item Toute machine ayant un nombre fini d'états finit par entrer dans un cycle.
 491 %%\end{itemize}
 492 %%  \end{exampleblock}
 493 %%}
 494
 495
 496
 497
 498
 499
 500
 501
 502
 503 %%\frame{
 504 %%  \frametitle{Mode d'emploi}
 505 %%  \begin{alertblock}{Chaos sur machine: quelques règles}
 506 %%    \begin{enumerate}
 507 %%      \item Ne pas laisser la machine travailler en vase clos %\newline
 508 %%      %$\Rightarrow$ Une nouvelle entrée à chaque itérée
 509 %%      \item Utiliser les médias sur lesquels on travaille %\newline
 510 %%      %$\Rightarrow$ Ensemble infini dénombrable
 511 %%      \item Ne manipuler que des entiers
 512 %%      \item \'Eviter les tailles fixes %(graine, nombre d'itérations, etc.)
 513 %%    \end{enumerate}
 514 %%  \end{alertblock}
 515 %%}
 516
 517
 518
 519
 520
 521 %\frame{
 522 %  \frametitle{Introduction}
 523 %  \begin{block}{Deux cas de figure}
 524 %    \begin{itemize}
 525 %      \item En vase clos :
 526 %      \begin{itemize}
 527 %        \item 4 Go de mémoire $\Rightarrow 2^{4000000000}$ états possibles...
 528 %        \item Lemme de filature/lemme fantôme
 529 %      \end{itemize}
 530 %      \item $\mathcal{X}=\mathds{B}^\mathsf{N}\times \mathcal{P}\left(\llbracket 1;\mathsf{N}\rrbracket\right)^\mathds{N}$:
 531 %      \begin{itemize}
 532 %        \item Pas de réels, que des entiers bornés par $\mathsf{N}$
 533 %        \item On peut utiliser le média à chaque itérée
 534 %      \end{itemize}
 535 %    \end{itemize}
 536 %  \end{block}
 537 %}
 538
 539
 540
 541
 542
 543
 544 %\frame{
 545 %  \frametitle{Introduction}
 546 %  \begin{exampleblock}{Deux questions}
 547 %%  Vos ICs sont chaotiques, mais pour moi c'est pas ça une machine, un programme.
 548 %\begin{itemize}
 549 %      \item Peut-on construire des automates chaotiques ?
 550 %      \item Peut-on évaluer si un programme est chaotique ?
 551 %\end{itemize}
 552 %  \end{exampleblock}
 553 %}
 554
 555
 556
 557
 558
 559 %\frame{
 560 % \frametitle{Une machine de Moore chaotique}
 561 %  \begin{center}
 562 %   \includegraphics[scale=0.55]{14.Caracterisation_des_IC_chaotiques_selon_Devaney/grapheTPICver2.pdf}
 563 %  \end{center}
 564 %}
 565
 566
 567
 568
 569
 570 %\frame{
 571 %\frametitle{Le chaos d'un programme}
 572 %\begin{block}{Machines de Turing et systèmes itératifs}
 573 %Soit $(w,i,q)$ la configuration actuelle de la machine de Turing\\
 574 %\begin{center}
 575 %\includegraphics[scale=0.3]{Steganalyse/Medias/Turing.pdf}
 576 %\end{center}
 577 %\begin{itemize}
 578 %\item $w=\sharp^{-\omega} w(0) \hdots w(k)\sharp^{\omega}$ est la bande de lecture,
 579 %\item $i$ est la position de la tête de lecture,
 580 %\item $q$ décrit l'état de la machine,
 581 %\item  et $\delta$ est sa fonction de transition.
 582 %\end{itemize}
 583 %\end{block}
 584 %}
 585
 586
 587
 588 %\frame{
 589 %\frametitle{Le chaos d'un programme}
 590 %\begin{block}{Machines de Turing et systèmes itératifs}
 591 %On définit $f$ par:
 592
 593 %\begin{itemize}
 594 %\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')$
 595 %\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')$
 596 %\end{itemize}
 597
 598 %La machine peut être écrite sous la forme $x^{n+1}=f(x^n)$
 599 %\end{block}
 600 %}
 601
 602
 603
 604
 605
 606
 607
 608 %\frame{
 609 %  \frametitle{A quoi ça sert ?}
 610 %  \begin{exampleblock}{Un programme chaotique, pour quoi faire ?}
 611 %\begin{itemize}
 612 %      \item Se placer dans de bonnes conditions lors de conception de nouveaux algorithmes
 613 %      \item Renforcer les attaques (virus chaotique)
 614 %      \item Simuler numériquement des processus chaotiques
 615 %      \item Renforcer la sécurité
 616 %      \item Battre l'intelligence artificielle
 617 %\end{itemize}
 618 %  \end{exampleblock}
 619 %
 620 %%  \uncover<3->{
 621 %%  Tentons une première illustration
 622 %%  }
 623 %}
 624
 625
 626
 627
 628
 629 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 630 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 631 %\section{Applications aux PRNGs}
 632 %\subsection*{PRNGs}
 633 %\begin{frame}{Applications}
 634 %% 'transition': Crossfade,
 635 %  \begin{center}
 636 %   \Huge{Applications}
 637
 638 %\medskip
 639 %   \huge{Générateurs pseudo-aléatoires}
 640 %  \end{center}
 641 %\end{frame}
 642 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 643 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 644
 645
 646 %\frame{
 647 %  \frametitle{Chaos et aléas}
 648 %    \begin{block}{Motivations: La batterie du NIST}
 649 %      \begin{itemize}
 650 %\item \textbf{Transitivités}
 651 %    \begin{itemize}
 652 %        \item \textbf{Random Excursions Variant Test.} To detect deviations from the expected number of visits to various states in the random walk.
 653 %        \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.
 654 %    \end{itemize}
 655 %\item \textbf{Chaos selon Li-Yorke}
 656 %    \begin{itemize}
 657 %        \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.
 658 %    \end{itemize}
 659 %\end{itemize}
 660 %\end{block}
 661 %}
 662
 663 %\frame{
 664 %  \frametitle{Chaos et aléas}
 665 %    \begin{block}{Motivations: La batterie du NIST}
 666 %      \begin{itemize}
 667 %    \item \textbf{Régularité}
 668 %    \begin{itemize}
 669 %        \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).
 670 %        \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.
 671 %    \end{itemize}
 672 %    \item \textbf{Entropie}
 673 %    \begin{itemize}
 674 %\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).
 675 %    \end{itemize}
 676 %    \end{itemize}
 677 %\end{block}
 678 %}
 679
 680 %\frame{
 681 %  \frametitle{Chaos et aléas}
 682 %    \begin{block}{Motivations: La batterie du NIST}
 683 %      \begin{itemize}
 684 %    \item \textbf{Non-linéarité, complexité}
 685 %    \begin{itemize}
 686 %\item \textbf{Binary Matrix Rank Test} To check for linear dependence among fixed length substrings of the original sequence.
 687 %\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).
 688 %      \end{itemize}
 689 %\end{itemize}
 690 %    \end{block}
 691 %}
 692
 693
 694 %\subsection*{Le Old CI PRNG}
 695 %\frame{
 696 %  \frametitle{Notre PRNG}
 697 % \begin{alertblock}{Le PRNG $CI_f(PRNG_1,PRNG_2)$}
 698 % \begin{description}
 699 %\item[\underline{Paramètres:}] Une fonction $f: \mathds{B}^\mathsf{N} \rightarrow  \mathds{B}^\mathsf{N}$, et deux PRNGs:\\
 700 %\begin{itemize}
 701 %\item $S\in\llbracket 1,\mathsf{N}\rrbracket^\mathds{N}$
 702 %\item et $m\in S^\mathds{N}, S \subset \mathds{N}$
 703 %\end{itemize}
 704 %\item[\underline{Graine:}] Les graines de $S$ et $m$, et $E\in \mathds{B}^\mathsf{N}$\\
 705 %\item[\underline{PRNG:}] $\left(G_f(E,S)^{m^i}\right)_{i\in\mathds{N}}$
 706 %\end{description}
 707 % \end{alertblock}
 708 %
 709 %% \uncover<2->{
 710 %% \begin{exampleblock}{Exemple: $X^{n+1} = X^n \oplus Y^n$}
 711 %%  où $Y \in \llbracket 0, 2^{\mathsf{N}}-1 \rrbracket^\mathds{N}$
 712 %% \end{exampleblock}
 713 %% }
 714 %}
 715
 716
 717
 718 %%\frame{
 719 %%  \frametitle{Old CI PRNG: Illustration}
 720 %%  \begin{block}{}
 721 %%\begin{figure}
 722 %%\centering
 723 %%  \includegraphics[scale=0.4]{OldCI1.png}
 724 %%  \caption{Le Old CI PRNG}
 725 %%  \end{figure}
 726 %%  \end{block}
 727 %%}
 728
 729
 730
 731 %%\frame{
 732 %%  \frametitle{Old CI PRNG: Illustration}
 733 %%  \begin{block}{}
 734 %%\begin{figure}
 735 %%\centering
 736 %%  \includegraphics[scale=0.41]{OldCI2.png}
 737 %%  \caption{Le Old CI PRNG}
 738 %%  \end{figure}
 739 %%  \end{block}
 740 %%}
 741
 742
 743 %%\frame{
 744 %%  \frametitle{Old CI PRNG: Illustration}
 745 %%  \begin{block}{}
 746 %%\begin{figure}
 747 %%\centering
 748 %%  \includegraphics[scale=0.4]{OldCI3.png}
 749 %%  \caption{Le Old CI PRNG}
 750 %%  \end{figure}
 751 %%  \end{block}
 752 %%}
 753
 754
 755
 756
 757 %%\frame{
 758 %%  \frametitle{Old CI PRNG: Illustration}
 759 %%  \begin{block}{}
 760 %%\begin{figure}
 761 %%\centering
 762 %%  \includegraphics[scale=0.4]{OldCI4.png}
 763 %%  \caption{Le Old CI PRNG}
 764 %%  \end{figure}
 765 %%  \end{block}
 766 %%}
 767
 768
 769
 770 %%\frame{
 771 %%  \frametitle{Old CI PRNG: Illustration}
 772 %%  \begin{block}{}
 773 %%\begin{figure}
 774 %%\centering
 775 %%  \includegraphics[scale=0.4]{OldCI5.png}
 776 %%  \caption{Le Old CI PRNG}
 777 %%  \end{figure}
 778 %%  \end{block}
 779 %%}
 780
 781
 782
 783
 784 %%\frame{
 785 %% \frametitle{Graphe de tous les possibles par IC}
 786 %%  \begin{center}
 787 %%   \includegraphics[scale=0.55]{14.Caracterisation_des_IC_chaotiques_selon_Devaney/grapheTPICver2.pdf}
 788 %%  \end{center}
 789 %%}
 790
 791
 792
 793
 794
 795 %\begin{frame}{Le Old $CI_{f_0}$(logistic,logistic)}
 796 %\begin{block}{}
 797 %\begin{tabular}{llllllllll}
 798 %m (logistic map):&\uncover<1->{2}      &\uncover<3->{~}                &\uncover<4->{~}        &\uncover<5->{~1}&\uncover<8->{~4}&\uncover<9->{~}&\uncover<10->{~}&\uncover<11->{~}& \uncover<13->{...}\\
 799 %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->{...}\\
 800 %\end{tabular}
 801 %\end{block}
 802 %
 803 %\begin{block}{\'Etat interne du système x:}
 804 %\begin{equation}
 805 %\label{Basic equations}
 806 %\begin{array}{r@{\;}l}
 807 %\ \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->{...}\\
 808 %\ \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->{...}\\
 809 %\ \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->{...}\\
 810 %\ \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->{...}\\
 811 %\end{array}
 812 %\end{equation}
 813 %\end{block}
 814
 815 %\begin{block}{}
 816
 817 %\alert{Sortie:} \uncover<4->{1 0 1 0 }\uncover<7->{1 1 1 0 }\uncover<13->{0 0 1 0 }\uncover<14->{...}
 818
 819 %\end{block}
 820 %\end{frame}
 821
 822
 823
 824
 825 %\begin{frame}{Choix de l'ensemble $\mathcal{M}$}
 826 % \begin{figure}[!t]
 827 % \centering
 828 % \includegraphics[width=3.5in,height=2in]{lesM.png}
 829 % \DeclareGraphicsExtensions.
 830 % \caption{Nombre d'itérations entre deux sorties}
 831 % \label{Premiers tests élémentaires}
 832 % \end{figure}
 833 %\end{frame}
 834
 835
 836
 837
 838 %\begin{frame}{Choix de l'ensemble $\mathcal{M}$}
 839 % \begin{figure}[!t]
 840 % \centering
 841 % \includegraphics[width=3.5in,height=2in]{leM.png}
 842 % \DeclareGraphicsExtensions.
 843 % \caption{Choix de $\mathcal{M}$}
 844 % \end{figure}
 845 %\end{frame}
 846
 847
 848
 849
 850
 851 %\frame{
 852 %\frametitle{Résultats}
 853 %\begin{alertblock}{Premiers résultats}
 854 %\begin{enumerate}
 855 %  \item Générateur chaotique dès que le GTPIC de $G_f$ est fortement connexe
 856 %  \item Toutes les autres propriétés de chaos
 857 %  \item Sortie uniforme si la matrice d'adjacence réduite du GTPIC est doublement stochastique
 858 %  \item Les résultats aux tests statistiques sont meilleurs (DieHARD, NIST, TestU01)
 859 %\end{enumerate}
 860 %\end{alertblock}
 861 %}
 862
 863
 864
 865
 866 %\begin{frame}{Premiers tests comparatifs}
 867 % \begin{figure}[!t]
 868 % \centering
 869 % \includegraphics[width=3.5in,height=2in]{1.pdf}
 870 % \DeclareGraphicsExtensions.
 871 % \caption{Premiers tests élémentaires}
 872 % \label{Premiers tests élémentaires}
 873 % \end{figure}
 874 %\end{frame}
 875
 876
 877 %\begin{frame}{NIST pour les PRNG en entrée}
 878 % \begin{figure}[!t]
 879 % \centering
 880 % \includegraphics[scale=0.27]{NistSeul.png}
 881 % \DeclareGraphicsExtensions.
 882 % \caption{Le NIST pour 3 PRNG}
 883 % \end{figure}
 884 %\end{frame}
 885
 886
 887
 888 %\begin{frame}{NIST pour le Old CI}
 889 % \begin{figure}[!t]
 890 % \centering
 891 % \includegraphics[scale=0.27]{NistAvec.png}
 892 % \DeclareGraphicsExtensions.
 893 % \caption{Résultats du Old CI PRNG}
 894 % \end{figure}
 895 %\end{frame}
 896
 897
 898
 899 %\begin{frame}{DieHard pour les PRNG en entrée}
 900 % \begin{figure}[!t]
 901 % \centering
 902 % \includegraphics[scale=0.27]{DieHardSeul.png}
 903 % \DeclareGraphicsExtensions.
 904 % \caption{DieHard pour 3 PRNG}
 905 % \end{figure}
 906 %\end{frame}
 907
 908
 909
 910
 911 %\begin{frame}{DieHard pour le Old CI}
 912 % \begin{figure}[!t]
 913 % \centering
 914 % \includegraphics[scale=0.24]{DieHarda.png}
 915 % \DeclareGraphicsExtensions.
 916 % \caption{Résultats du Old CI PRNG}
 917 % \end{figure}
 918 %\end{frame}
 919
 920
 921
 922
 923 %\begin{frame}{TestU01 pour les PRNG en entrée}
 924 % \begin{figure}[!t]
 925 % \centering
 926 % \includegraphics[scale=0.3]{TestUSeul.png}
 927 % \DeclareGraphicsExtensions.
 928 % \caption{TestU01 pour 3 PRNG}
 929 % \end{figure}
 930 %\end{frame}
 931
 932
 933
 934
 935
 936
 937
 938
 939 %\begin{frame}{TestU01 pour le Old CI}
 940 % \begin{figure}[!t]
 941 % \centering
 942 % \includegraphics[scale=0.25]{TestUAvec.png}
 943 % \DeclareGraphicsExtensions.
 944 % \caption{Résultats du Old CI PRNG}
 945 % \end{figure}
 946 %\end{frame}
 947
 948
 949
 950 %\subsection*{Le New CI PRNG}
 951 %\frame{
 952 %  \frametitle{Variantes}
 953 %    \begin{block}{Quelques variantes du CI PRNG}
 954 %      \begin{itemize}
 955 %        \item $New ~CI_f(PRNG_1,PRNG_2)$: éviter de changer deux fois de suite un même bit entre deux outputs
 956 %          \begin{itemize}
 957 %            \item Ne plus compter le nombre d'itérées entre deux outputs
 958 %            \item Mais le nombre de bits à changer
 959 %          \end{itemize}
 960 %        \item $Xor CI PRNG$: $S^{n+1}=S^n \oplus PRNG^n$
 961 %        \item etc.
 962 %      \end{itemize}
 963 %    \end{block}
 964 %}
 965
 966
 967
 968
 969
 970
 971 %\begin{frame}{La suite $m$ du New CI}
 972 %Supposons que $x_0 = (0, 0, 0)$. Alors $m_0 \in \llbracket 0, 3 \rrbracket$: on
 973 %peut changer de 0 à 3 bits dans cet état pour produire $x_1$.
 974 %\begin{itemize}
 975 %  \item Si $m_0 = 0$, alors aucun bit ne changera entre la première et la
 976 %  seconde sortie de notre générateur. Et donc $x_1 = (0, 0, 0)$.
 977 %  \item Si $m_0 = 1$, alors exactement 1 bit changera, ce qui conduit à trois
 978 %  valeurs possibles pour $x_1$, à savoir (1, 0, 0), (0, 1, 0) et (0, 0, 1).
 979 %  \item etc.
 980 %\end{itemize}
 981 %\end{frame}
 982
 983
 984
 985 %\begin{frame}{La suite $m$ du New CI}
 986 %\begin{equation}
 987 %\label{Formula}
 988 %m^n = f(y^n)=
 989 %\left\{
 990 %\begin{array}{l}
 991 %0 \text{   si   }0                             \leqslant\frac{y^n}{2^{32}}<\frac{C^0_N}{2^N},\\
 992 %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},\\
 993 %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},\\
 994 %\vdots~~~~~                                    ~~\vdots~~~                 ~~~~\\
 995 %N \text{   si   }\sum_{i=0}^{N-1}\frac{C^i_N}{2^N}     \leqslant\frac{y^n}{2^{32}}<1.\\
 996 %\end{array}
 997 %\right.
 998 %\end{equation}
 999 %\end{frame}
1000
1001
1002
1003
1004
1005 %\begin{frame}{Stratégie chaotique}
1006 %Une suite de marquage controlera la suite du XORshift $b$ ainsi:
1007 %\begin{itemize}
1008 %\item si $d^{b^j} \neq 1$, alors $S^k=b^j$, $d^{b^j} = 1$ et $k = k+1$
1009 %\item si $d^{b^j}=1$, alors $b^j$ est écarté.
1010 %\end{itemize}
1011 %Par exemple, si $b = 142\underline{2}334
1012 %142\underline{1} \underline{1}\underline{2}\underline{2}34...$ et $m =
1013 %4241...$, alors $S=1423~34~1423~4...$
1014 %\end{frame}
1015
1016
1017
1018
1019
1020
1021 %%\subsection*{Chaotic iterations as pseudo-random generator}
1022 %% \begin{frame}{CI(XORshift, XORshift) algorithm}
1023 %% \begin{tiny}
1024 %% \begin{table}
1025 %% \centering
1026 %% \begin{tabular}{|l|}
1027 %% \hline
1028 %% ~\textbf{Input}: the internal state $x$ (an array of $\mathsf{N}$ bits)\\
1029 %% \hline
1030 %% ~\textbf{Output}: a state $r$ of $\mathsf{N}$ bits \\
1031 %% \hline
1032 %% ~\textbf{for} $i=0,\dots,N$ \textbf{do}\\
1033 %% ~~~~~~ $d_i\leftarrow{0}$;\\
1034 %% ~\textbf{end for}\\
1035 %% ~$a\leftarrow{XORshift1(~)}$;\\
1036 %% ~$m\leftarrow{f(a)}$\;\\
1037 %% ~$k\leftarrow{m}$\;\\
1038 %% ~\textbf{for} $i=0,\dots,k$ \textbf{do}\\
1039 %% ~~~~~~ $b\leftarrow{XORshift2() mod ~ N}$;\\
1040 %% ~~~~~~ $S\leftarrow{b}$;\\
1041 %% ~~~~~~~\textbf{if} $d_S=0$ \textbf{then}\\
1042 %% ~~~~~~~~~~~~ $x_S\leftarrow{ \overline{x_S}}$;\\
1043 %% ~~~~~~~~~~~~ $d_S\leftarrow{1}$;\\
1044 %% ~~~~~~~\textbf{end}\\
1045 %% ~~~~~~~\textbf{else if} $d_S=1$ \textbf{then}\\
1046 %% ~~~~~~~~~~~~ $k\leftarrow{k+1}$;\\
1047 %% ~~~~~~~\textbf{end}\\
1048 %% ~\textbf{end for}\\
1049 %% ~$r\leftarrow{x}$\;\\
1050 %% ~\textbf{return} $r$;\\
1051 %% \hline
1052 %%
1053 %% \end{tabular}
1054 %% \caption{An arbitrary round of the proposed generator}
1055 %% \label{Chaotic iteration}
1056 %% \end{table}
1057 %% \end{tiny}
1058 %%
1059 %% \end{frame}
1060 %%
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077 %%\begin{frame}{Exemple du New CI}
1078 %%\begin{block}{}
1079 %%\begin{tabular}{llllll}
1080 %%m:&\uncover<2->{0~}   &\uncover<4->{4~~}                      &\uncover<6->{2 }       &\uncover<8->{2}&\uncover<10->{...}\\
1081 %%k:&\uncover<2->{0~}   &\uncover<4->{4~~~~~~+1~}               &\uncover<6->{2 }       &\uncover<8->{2~+1}&\uncover<10->{...}\\
1082 %%b:&\uncover<2->{~~}   &\uncover<4->{1~4~2~\underline{2}~3}    &\uncover<6->{3~4}      &\uncover<8->{1~\underline{1}~~~4}&\uncover<10->{...}\\
1083 %%S:&\uncover<2->{~~}   &\uncover<4->{1~4~2~~~~3}               &\uncover<6->{3~4}      &\uncover<8->{1~~~~~~4}&\uncover<10->{...}
1084 %%\end{tabular}
1085 %%\end{block}
1086 %%
1087 %%\begin{block}{x:}
1088 %%\begin{equation}
1089 %%\label{Basic equations}
1090 %%% \left\{
1091 %%\begin{array}{r@{\;}l}
1092 %%\ \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->{...}\\
1093 %%\ \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->{...}\\
1094 %%\ \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->{...}\\
1095 %%\ \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->{...}
1096 %%\end{array}
1097 %%% \right.
1098 %%\end{equation}
1099 %%\end{block}
1100
1101 %%\begin{block}{}
1102
1103 %%\alert{Sortie:} 0 1 0 0 \uncover<3->{0 1 0 0 }\uncover<5->{1 0 1 1
1104 %%}\uncover<7->{1 0 0 0 }\uncover<9->{0 0 0 1 }\uncover<10->{...}
1105
1106 %%\end{block}
1107
1108 %%\end{frame}
1109
1110
1111
1112
1113
1114 %\begin{frame}{Nouvelle version de $CI_f(PRNG_1,PRNG_2)$}
1115 % \begin{figure}[!t]
1116 % \centering
1117 % \includegraphics[scale=0.25]{newCI.png}
1118 % \DeclareGraphicsExtensions.
1119 % \caption{Le NEW CI PRNG}
1120 % \end{figure}
1121 %\end{frame}
1122
1123
1124
1125 %\begin{frame}{NIST pour le New CI}
1126 % \begin{figure}[!t]
1127 % \centering
1128 % \includegraphics[scale=0.27]{NistNew.png}
1129 % \DeclareGraphicsExtensions.
1130 % \caption{Résultats du New CI PRNG (Nist)}
1131 % \end{figure}
1132 %\end{frame}
1133
1134
1135
1136
1137 %\begin{frame}{DieHard pour le New CI}
1138 % \begin{figure}[!t]
1139 % \centering
1140 % \includegraphics[scale=0.24]{DieHardNew.png}
1141 % \DeclareGraphicsExtensions.
1142 % \caption{Résultats du New CI PRNG (DieHard)}
1143 % \end{figure}
1144 %\end{frame}
1145
1146
1147
1148
1149
1150
1151
1152 %\begin{frame}{TestU01 pour le New CI}
1153 % \begin{figure}[!t]
1154 % \centering
1155 % \includegraphics[scale=0.37]{TestUNew.png}
1156 % \DeclareGraphicsExtensions.
1157 % \caption{Résultats du New CI PRNG (TestU01)}
1158 % \end{figure}
1159 %\end{frame}
1160
1161
1162
1163
1164
1165
1166
1167 %%\begin{frame}{Premiers tests comparatifs}
1168 %%\begin{tiny}
1169 %%\begin{table}[!t]
1170 %%\renewcommand{\arraystretch}{1.3}
1171 %%\caption{Comparaison avec $2 \times 10^5$ bits}
1172 %%\label{Comparison2}
1173 %%\centering
1174 %%  \begin{tabular}{ccccccc}
1175 %%    \hline
1176 %%Method & Monobit & Serial & Poker & Runs & Autocorrelation & Time  \\ \hline
1177 %%Logistic map &0.1280&0.1302&240.2893&26.5667&0.0373&0.965s \\
1178 %%XORshift &1.7053&2.1466&248.9318&18.0087&-0.5009&0.096s \\
1179 %%Old CI(Logistic, Logistic) &1.0765&1.0796&258.1069&20.9272&-1.6994&0.389s \\
1180 %%New CI(XORshift,XORshift) &0.3328&0.7441&262.8173&16.7877&-0.0805&0.197s\\
1181 %%    \hline
1182 %%  \end{tabular}
1183 %%\end{table}
1184 %%\end{tiny}
1185 %%\end{frame}
1186
1187
1188
1189
1190
1191
1192
1193
1194 %%\frame{
1195 %%  \frametitle{Résultats au TestU01}
1196 %%  \begin{center}
1197 %%  \begin{tabular}{|c|c|}
1198 %%  \hline
1199 %%  PRNG & Échecs (sur 516 tests) \\
1200 %%  \hline
1201 %%  Suite logistique & 261 \\
1202 %%  XORshift & 146 \\
1203 %%  ISAAC & 0 \\
1204 %%  \hline
1205 %%  Old CI(Logistic,Logistic) & 138 \\
1206 %%  Old CI(XORshift,XORshift) & 9 \\
1207 %%  Old CI(ISAAC,XORshift) & 0 \\
1208 %%  Old CI(ISAAC,ISAAC) & 0 \\
1209 %%  \hline
1210 %%  New CI(Logistic,Logistic) & 0 \\
1211 %%  New CI(ISAAC,XORshift) & 0 \\
1212 %%  New CI(ISAAC,ISAAC) & 0 \\
1213 %%  \hline
1214 %%  \end{tabular}
1215 %%  \end{center}
1216 %%%  \begin{figure}
1217 %%%  \centering
1218 %%%  \includegraphics[scale=0.35]{testU010.png}
1219 %%%  \caption{Score de quelques PRNGs au TestU01}
1220 %%%  \end{figure}
1221 %%}
1222
1223
1224
1225 %%\frame{
1226 %%  \frametitle{Résultats}
1227 %%  \begin{figure}
1228 %%  \centering
1229 %%  \includegraphics[scale=0.35]{testU011.png}
1230 %%  \caption{Améliorations via le $Old CI(PRNG_1,PRNG_2)$}
1231 %%  \end{figure}
1232 %%}
1233
1234
1235
1236 %%\frame{
1237 %%  \frametitle{Résultats}
1238 %%  \begin{figure}
1239 %%  \centering
1240 %%  \includegraphics[scale=0.35]{testU012.png}
1241 %%  \caption{Améliorations via le $New CI(PRNG_1,PRNG_2)$}
1242 %%  \end{figure}
1243 %%}
1244
1245
1246
1247 %\frame{
1248 %  \frametitle{Résultats}
1249 %  \begin{figure}
1250 %  \centering
1251 %  \includegraphics[scale=0.27]{prngs.png}
1252 %  \caption{Autres résultats}
1253 %  \end{figure}
1254 %  }
1255
1256
1257
1258 %\frame{
1259 %  \frametitle{Résultats}
1260 %  \begin{figure}
1261 %  \centering
1262 %  \includegraphics[scale=0.27]{vitesse.png}
1263 %  \caption{Perte de vitesse}
1264 %  \end{figure}
1265 %  }
1266
1267
1268 %%\frame{
1269 %%  \frametitle{A quel prix ?}
1270 %%  \begin{figure}
1271 %%  \centering
1272 %%  \includegraphics[scale=0.35]{rapide.png}
1273 %%  \caption{Dégradation de la vitesse}
1274 %%  \end{figure}
1275 %%}
1276
1277
1278
1279
1280
1281
1282 %\subsection*{Une famille pour le Old CI}
1283
1284
1285
1286 %\frame{
1287 %  \frametitle{Définition d'une famille de Old CI}
1288 %\begin{block}{La matrice associée à $f$}
1289 %Matrice de taille $N\times 2^N$ dont l'élément $(p,q)$ est
1290 %l'entier ayant la décompistion binaire:
1291 %$$q_N, \hdots, q_{N-p}, f(q)_{N-p+1}, q_{N-p+2}, \hdots, q_1$$
1292 %avec $q_i$: $i-$ième chiffre en base 2 de $q$.
1293 %\end{block}
1294 %
1295
1296 %\begin{block}{Vecteur des images}
1297 %Le vecteur des images de $f$ est:
1298 %$$\mathcal{F}(f)=(f(0), f(1), \hdots, f(2^N-1)) \in \llbracket 0, 2^N-1 \rrbracket^{2^N}$$
1299 %\end{block}
1300 %}
1301
1302
1303
1304
1305 %\frame{
1306 %  \frametitle{Exemple de matrice associée}
1307 %  \begin{figure}
1308 %  \centering
1309 %  \includegraphics[scale=0.27]{mappingMatrix.png}
1310 %  \caption{Matrice associée et vecteur des images pour $f_0$}
1311 %  \end{figure}
1312 %
1313 %}
1314
1315
1316
1317 %\frame{
1318 %  \frametitle{Une règle pour le Old CI PRNG}
1319 %  \begin{itemize}
1320 %    \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é
1321 %    \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$
1322 %  \end{itemize}
1323 %
1324 %}
1325
1326
1327
1328
1329 %\frame{
1330 %  \frametitle{Exemple de fonctions pour le Old CI}
1331 %  \begin{figure}
1332 %  \centering
1333 %  \includegraphics[scale=0.27]{mappingF0.png}
1334 %  \caption{Création de nouvelles fonctions équilibrées}
1335 %  \end{figure}
1336 %  }
1337
1338
1339 %\frame{
1340 %  \frametitle{Un théorème pour l'équilibrage}
1341 %\begin{alertblock}{Théorème}
1342 %Soit $f: \mathds{B}^{n} \rightarrow \mathds{B}^{n}$, $\Gamma(f)$ son graphe d'itération,
1343 %$\check{M}$ sa matrice d'adjacence.
1344
1345 %Si $\Gamma(f)$ est fortement connexe, alors la sortie produite par le Old CI PRNG
1346 %suit une loi qui tend vers l'uniforme répartition si et seulement si $M$ est
1347 %doublement stochastique.
1348 %\end{alertblock}
1349 %}
1350
1351
1352
1353
1354 %\frame{
1355 %  \frametitle{D'autres Old CI chaotiques}
1356 %  \begin{block}{Pour obtenir d'autres Old CI chaotiques}
1357 %  \begin{enumerate}
1358 %    \item Partir du graphe de tous les possibles de $f_0$
1359 %    \item Tant que le taux ne suppression n'est pas atteint:
1360 %    \begin{itemize}
1361 %      \item tirer une arête au sort
1362 %      \item la supprimer si le graphe reste fortement connexe (algorithme de Tarjan)
1363 %    \end{itemize}
1364 %  \end{enumerate}
1365 %  (Problème avec les graphes isomorphes)
1366 %  \end{block}
1367 %}
1368
1369
1370 %\frame{
1371 %  \frametitle{Exemple de fonctions pour le Old CI}
1372 %  \begin{figure}
1373 %  \centering
1374 %  \includegraphics[scale=0.27]{SCC.png}
1375 %  \caption{Création de nouvelles fonctions au générateur chaotique}
1376 %  \end{figure}
1377 %
1378 %}
1379
1380
1381
1382 %\frame{
1383 %  \frametitle{Condition suffisante de chaoticité}
1384 %\begin{alertblock}{Théorème}
1385 %Soit $f$ une fonction de $\mathds{B}^n$ dans lui-même telle que:
1386 %\begin{enumerate}
1387 %\item
1388 %Le graphe de connexion $G(f)$ n'a pas de cycle de longueur au moins 2;
1389 %\item
1390 %Chaque arête de $G(f)$ ayant une boucle positive a aussi une boucle négative;
1391 %\item
1392 %Chaque arête de $G(f)$ est joignable à partir d'un noeud ayant une boucle négative.
1393 %\end{enumerate}
1394 %Alors $\Gamma(f)$ est fortement connexe.
1395 %\end{alertblock}
1396 %}
1397
1398
1399
1400 %%\begin{theorem}
1401 %%  Let $f: \mathds{B}^{n} \rightarrow \mathds{B}^{n}$, $\Gamma(f)$ its
1402 %%  iteration graph, $\check{M}$ its adjacency
1403 %%  matrix and $M$ a $n\times n$ matrix defined as in the previous lemma.
1404 %%  If $\Gamma(f)$ is SCC then
1405 %%  the output of the PRNG detailed in Algorithm~\ref{CI Algorithm} follows
1406 %%  a law that tends to the uniform distribution
1407 %%  if and only if $M$ is a double stochastic matrix.
1408 %%\end{theorem}
1409
1410
1411 %\subsection*{PRNG cryptographiquement sûr}
1412 %
1413
1414 %\frame{
1415 %\frametitle{Les PRNG cryptographiquement sûrs}
1416 %\begin{block}{Définition: Générateur $G$ \emph{cryptographiquement sûr}}
1417 %%Pour tout
1418 %%algorithme probabiliste polynomial en temps $\mathcal{D}$, pour tout
1419 %%polynome $\mathfrak{p}>0$, et pour tout $n$ suffisamment large,
1420 %$$\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)},$$
1421 %%où $\mathfrak{U}_r$ est la loi de probabilité uniforme sur $\{0,1\}^r$ et les
1422 %%probabilités sont prises sur $\mathfrak{U}_n$, $\mathfrak{U}_{\ell_G(n)}$ de la même manière
1423 %%que pour le lancer d'une pièce de monnaie dans $\mathcal{D}$.
1424 %\end{block}
1425 %}
1426
1427
1428
1429 %\subsection*{Version GPU}
1430
1431 %\frame{
1432 %\frametitle{Derniers Résultats}
1433 %\begin{alertblock}{Nos derniers résultats}
1434 %\begin{enumerate}
1435 %  \item Si le premier PRNG en entrée est polynomialement indistinguable d'une suite aléatoire, alors notre PRNG l'est aussi
1436 %  \item Implantation sur GPU $\Rightarrow$ 20 milliards de nombres (32 bits) par seconde sur un PC
1437 %  \item Utilisation de BBS $\Rightarrow$ 1 milliards de nombres sûrs par seconde
1438 %  \item Version chaotique du cryptosystème asymétrique probabiliste de Blum-Goldwasser
1439 %  \item Mixage avec dispositif optique (Larger, OPTO)
1440 %\end{enumerate}
1441 %\end{alertblock}
1442 %}
1443
1444
1445
1446
1447
1448 %%\frame{
1449 %%  \frametitle{Notre générateur GPU}
1450 %%  \begin{figure}
1451 %%  \centering
1452 %%  \includegraphics[scale=0.3]{gpu.png}
1453 %%%  \caption{Version GPU de notre générateur}
1454 %%  \end{figure}
1455 %%}
1456
1457
1458
1459
1460 %%\frame{
1461 %%  \frametitle{Notre générateur GPU}
1462 %%  \begin{figure}
1463 %%  \centering
1464 %%  \includegraphics[scale=0.25]{bbs.png}
1465 %% % \caption{Version GPU de notre générateur, avec bbs}
1466 %%  \end{figure}
1467 %%}
1468
1469
1470
1471 %\frame{
1472 %  \frametitle{Notre générateur GPU}
1473 %  \begin{tabular}{cc}
1474 %  \includegraphics[scale=0.3]{gpu.png} & \includegraphics[scale=0.275]{bbs.png}
1475 %  \end{tabular}
1476 %}
1477
1478 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1479 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1480 %\section{Nouvelles pistes}
1481 %%\subsection*{PRNGs}
1482 %\begin{frame}{}
1483 %% 'transition': Crossfade,
1484 %  \begin{center}
1485 %   \Huge{Nouvelles pistes}
1486
1487 %\medskip
1488 %   %\huge{soulevés par l'approche}
1489 %  \end{center}
1490 %\end{frame}
1491 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1492 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1493
1494
1495
1496
1497
1498
1499
1500 %\frame{
1501 % \frametitle{Le générateur optique}
1502 % \begin{block}{Côté OPTO}
1503 %  \begin{figure}
1504 %  \centering
1505 %  \includegraphics[scale=0.5]{setup_opto_RNG.eps}
1506 %   \caption{Générateur optique (laser chaotique)}
1507 %  \end{figure}
1508 %  \end{block}
1509 %}
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521 %\frame{
1522 % \frametitle{Le générateur mixé}
1523 % \begin{block}{Côté DISC}
1524 %  \begin{figure}
1525 %  \centering
1526 %  \includegraphics[scale=0.5]{improve.eps}
1527 %   \caption{Mixage analogique-numérique}
1528 %  \end{figure}
1529 %  \end{block}
1530 %}
1531
1532
1533
1534
1535
1536 %\frame{
1537 % \frametitle{Le générateur mixé}
1538 % \begin{block}{Améliorations (NIST)}
1539 %  \begin{figure}
1540 %  \centering
1541 %  \includegraphics[scale=0.35]{NistLaurent.png}
1542 %   \caption{Résultat au NIST}
1543 %  \end{figure}
1544 %  \end{block}
1545 %}
1546
1547
1548
1549
1550
1551 %\frame{
1552 % \frametitle{Le générateur mixé}
1553 % \begin{block}{Améliorations (DieHARD)}
1554 %  \begin{figure}
1555 %  \centering
1556 %  \includegraphics[scale=0.25]{DieHardLaurent.png}
1557 %   \caption{Résultat au DieHARD}
1558 %  \end{figure}
1559 %  \end{block}
1560 %}
1561
1562
1563
1564 %\frame{
1565 % \frametitle{Le générateur mixé}
1566 % \begin{block}{Côté DISC}
1567 %  \begin{figure}
1568 %  \centering
1569 %  \includegraphics[scale=0.35]{method.eps}
1570 %   \caption{Premier PRNG mixé réalisé}
1571
1572 %  \end{figure}
1573 %  \end{block}
1574 %}
1575
1576
1577 %\frame{
1578 % \frametitle{Premiers résultats}
1579 %  \begin{tabular}{|l||c|c|c|c|c|}
1580 %    \hline
1581 %\textbf{Tests} {\textbf{$n$}}&1 &10&20&30&40 \\ \hline\hline
1582 %NIST suite & 0/15 &14/15 & 15/15 & 15/15 & 15/15\\ \hline
1583 %DieHARD suite &1/18 &11/18 & 14/18 &18/18&18/18\\ \hline
1584 %  \end{tabular}
1585 %}
1586
1587
1588 %\frame{
1589 % \frametitle{Le générateur mixé}
1590 % \begin{block}{Côté DISC}
1591 %  \begin{figure}
1592 %  \centering
1593 %  \includegraphics[scale=0.25]{paralel.png}
1594 %   \caption{Deuxième PRNG mixé réalisé}
1595 %  \end{figure}
1596 %  \end{block}
1597 %}
1598
1599
1600 %\frame{
1601 %  \frametitle{Une piste ?}
1602 %  $$X^{mn+1} = X^{mn} \oplus O^{mn} \oplus C^m$$
1603 %}
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613 %\begin{frame}{}
1614 % \begin{center}
1615 % \huge{Merci pour votre attention}
1616 % \end{center}
1617 %\end{frame}
1618
1619
1620
1621
1622
1623
1624
1625
1626 %%\frame{
1627 %%% 'transition': Crossfade,
1628 %% \frametitle{Une menace en guise d'illustration}
1629 %% \begin{block}{Les attaques par canal auxiliaire}
1630 %% \begin{enumerate}
1631 %%\item Certains processeurs peuvent laisser fuire de l'information. \newline $\Rightarrow$ En 2006 [Acimez07], 508 bits d'une clé d'authentification sur 512.
1632 %%\item Variation de tension appliquée au processeur [Pellegrini10]\newline $\Rightarrow$ \'Emission d'une signature (RSA 1024) corrompue.
1633 %%\item Mesure du temps de déchiffrement [Kocher95] \newline $\Rightarrow$ Obtention de la clé de déchiffrement.
1634 %%\item Optimisations appliquées au théorème des restes chinois [Brumley03] \newline $\Rightarrow$ Factorisation RSA trouvée.
1635 %%\end{enumerate}
1636 %%\end{block}
1637 %%}
1638
1639
1640
1641
1642 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1643
1644
1645
1646 %%\frame{
1647 %%% 'transition': Crossfade,
1648 %%  \frametitle{Une menace en guise d'illustration}
1649 %%  \begin{block}{Les attaques par canal auxiliaire}
1650 %%  \begin{itemize}
1651 %%    \item Failles matérielles ou logicielles
1652 %%    \item Une partie du secret
1653 %%    \item Algorithmes prouvés sûrs
1654 %%  \end{itemize}
1655 %%  \end{block}
1656 %%
1657 %%  \vspace{0.25cm}
1658 %%  \uncover<2->{
1659 %%  \begin{exampleblock}{Tentatives de solution}
1660 %%  \begin{itemize}
1661 %%    \item Ne plus répondre au cas par cas
1662 %%    \item Une sécurité complémentaire ?
1663 %%    \item Pourquoi ne pas utiliser des programmes imprédictibles ?
1664 %%  \end{itemize}
1665 %%  \end{exampleblock}
1666 %%}
1667 %%}
1668
1669
1670
1671
1672
1673
1674
1675
1676 %%\frame{
1677 %% \frametitle{Nos contributions}
1678 %%\begin{block}{Nos contributions}
1679 %%\begin{itemize}
1680 %%\item Construire des machines, des programmes imprévisibles
1681 %%\item Etudier des algorithmes existants sous d'autres aspects (comparaison, autres menaces ?)
1682 %%\item Rajouter des propriétés (topologiques) à des outils préexistants, \emph{sans perte de sécurité}
1683 %% \end{itemize}
1684 %%\end{block}
1685 %%}
1686
1687
1688
1689
1690
1691
1692
1693
1694 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1695 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1696 %\section*{Problèmes}
1697 %\begin{frame}{}
1698 %% 'transition': Crossfade,
1699 %  \begin{center}
1700 %   \Huge{Problèmes}
1701
1702 %\medskip
1703 %   \huge{soulevés par l'approche}
1704 %  \end{center}
1705 %\end{frame}
1706 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1707 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1708
1709
1710
1711
1712
1713
1714
1715 %% %%%%%%%%%%%%% 16. De la relativité du chaos %%%%%%%%%%%%%%%
1716 %\subsection*{Tout est relatif (est-ce encore vrai ?)}
1717
1718 %% \frame{
1719 %%   \frametitle{Problème soulevé par l'approche}
1720 %%   \begin{block}{Quels problèmes pose cette approche ?}
1721 %%   \begin{itemize}
1722 %%   \item Rôle prépondérant de la topologie
1723 %%   \item De sa finesse dépendent les propriétés de désordre
1724 %%   \item Comment bien la choisir ?
1725 %%   \end{itemize}
1726 %%   $\Rightarrow$ Se ramener à la topologie de l'ordre sur $\mathds{R}$
1727 %%   \end{block}
1728 %% }
1729
1730
1731 %\frame{
1732 % \frametitle{De l'importance de la topologie}
1733 %%\begin{block}{Les questions qui se posent}
1734 %%\begin{enumerate}
1735 %%\item Si un système $(\mathcal{X},f)$ est chaotique, et pour quelle topologie.
1736 %%\item Si un système $(\mathcal{X},f)$ est plus chaotique qu'un système $(\mathcal{Y},g)$.
1737 %%\end{enumerate}
1738 %%\end{block}
1739
1740 %%\vspace{0.5cm}
1741 %%\uncover<2>{
1742 %\begin{exampleblock}{Problèmes soulevés}
1743 %\begin{enumerate}
1744 %\item Le désordre dépend de la topologie (?)
1745 %\item Comparaison de deux systèmes:
1746 %\begin{itemize}
1747 %\item Les ensembles $\mathcal{X}$ et $\mathcal{Y}$ ne sont pas forcément les mêmes.
1748 %\item Les topologies ne sont pas forcément les mêmes.
1749 %\item Sont-elles comparables ? Et quelles conséquences ?
1750 %\end{itemize}
1751 %\end{enumerate}
1752 %\end{exampleblock}
1753 %%}
1754 %}
1755
1756
1757
1758 %\frame{
1759 % \frametitle{Mon désordre n'est pas le tien}
1760 %   \begin{exampleblock}{Théorème: Impact de la finesse de la topologie}
1761 %   Soient $\tau, \tau'$ deux topologies sur $\mathcal{X}$ telles que $\tau \subset \tau'$.
1762
1763 %Si $(\mathcal{X}_{\tau'},f)$ satisfait Devaney, alors $(\mathcal{X}_\tau,f)$ aussi.
1764 %   \end{exampleblock}
1765 %}
1766
1767 %\frame{
1768 % \frametitle{Mon désordre n'est pas le tien}
1769 %   \begin{exampleblock}{Un système peut toujours être chaotique}
1770 %   Soit $\mathcal{X}$ un ensemble non vide, et $f: \mathcal{X} \to \mathcal{X}$ une application possédant au moins un point fixe.
1771 %Alors $f$ est $\tau_0-$chaotique, où $\tau_0$ est la topologie grossière sur $\mathcal{X}$.
1772 %   \end{exampleblock}
1773 %
1774 %   \vspace{0.5cm}
1775 %
1776 %     \begin{exampleblock}{Un système peut toujours ne jamais être chaotique}
1777 %Soit $\mathcal{X}$ un ensemble, et $f: \mathcal{X} \to \mathcal{X}$ une application.
1778 %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.
1779 %   \end{exampleblock}
1780 %}
1781
1782
1783
1784
1785
1786 %\frame{
1787 % \frametitle{Réflexions autour d'un désordre absolu}
1788 %  \begin{block}{Reformulation des problèmes}
1789 %    \begin{itemize}
1790 %      \item $(\mathcal{X},f)$ peut ou non être chaotique, suivant la richesse de la topologie.
1791 %      \item L'ensemble des topologies sur $\mathcal{X}$, muni de la relation « être plus fine que » est un espace réticulé.
1792 %    \end{itemize}
1793 %  \end{block}
1794 %
1795 %  \vspace{0.4cm}
1796 %
1797 % \begin{block}{Quelques pistes}
1798 %   \begin{enumerate}
1799 %     \item La plus fine topologie rendant une fonction imprédictible
1800 %     \item \^Etre imprédictible, c'est l'être pour la topologie de l'ordre.
1801 %       \begin{itemize}
1802 %         \item Approche légitime (mais, pour quel ordre ?)
1803 %         \item Peut conduire à se ramener à $\mathds{R}$
1804 %       \end{itemize}
1805 %   \end{enumerate}
1806 % \end{block}
1807 %}
1808
1809
1810 %%%%%%%%%%%%%%% 17. Une semi-conjugaison topologique %%%%%%%%
1811 %%%%%%%%%% ou comment passer de X à un intervalle réel %%%%%%
1812 %\subsection*{Une semi-conjugaison topologique}
1813
1814
1815
1816 %\frame{
1817 %  \frametitle{Une semi-conjugaison topologique}
1818 %
1819 %
1820 %\begin{exampleblock}{Une semi-conjugaison topologique}
1821 %IC $G_{f_0}$ sur $\mathcal{X}$ = IC $g$ sur $\mathds{R}$:
1822 %\begin{equation*}
1823 %\begin{CD}
1824 %\left(~\mathcal{S}_{10} \times\mathds{B}^{10}, d~\right) @>G_{f_0}>> \left(~\mathcal{S}_{10} \times\mathds{B}^{10}, d~\right)\\
1825 %    @V{\varphi}VV                    @VV{\varphi}V\\
1826 %\left( ~\big[ 0, 2^{10} \big[, D~\right)  @>>g> \left(~\big[ 0, 2^{10} \big[, D~\right)
1827 %\end{CD}
1828 %\end{equation*}
1829 %\begin{enumerate}
1830 %\item Prendre la première décimale $d$ de $x \in \big[ 0, 2^{10} \big[$
1831 %\item Nier le bit numéro $d$ de $E(x)$
1832 %\item Supprimer $d$
1833 %\end{enumerate}
1834 %\end{exampleblock}
1835 %}
1836
1837
1838
1839
1840 %\frame{
1841 %  \frametitle{Comparaison des distances}
1842
1843 %\begin{exampleblock}{Comparaison de distances}
1844 %$D$ est plus fine que la distance euclidienne.
1845 %\end{exampleblock}
1846
1847 %\begin{figure}[t]
1848 %\begin{center}
1849 %  \subfigure[Application $x \to dist(x;1,234)$.]{\includegraphics[scale=.25]{17.Semi_conjugaison_topologique/distances/DvsEuclidien.pdf}}\quad
1850 %  \subfigure[Application $x \to dist(x;3) $.]{\includegraphics[scale=.25]{17.Semi_conjugaison_topologique/distances/DvsEuclidien2.pdf}}
1851 %\end{center}
1852 %\caption{Comparaison des distances $D$ et euclidienne.}
1853 %\label{fig:comparaison de distances}
1854 %\end{figure}
1855 %}
1856
1857
1858
1859
1860
1861
1862
1863
1864 %\frame{
1865 % \frametitle{\'Etude des ICs sur $\mathds{R}$}
1866 % \begin{exampleblock}{Analyse des itérations chaotiques réelles}
1867 %Les itérations chaotiques $g$ définies sur $\mathds{R}$ sont:
1868 %\begin{itemize}
1869 %\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\}$.
1870 %\item Affine, de pente 10, sur chaque sous-intervalle.
1871 %\end{itemize}
1872 %\end{exampleblock}
1873 %}
1874
1875
1876
1877 %%\frame{
1878 %%  \frametitle{Exemples de fonctions chaotiques}
1879 %%\begin{figure}[t]
1880 %%\begin{center}
1881 %%  \subfigure[Doublement de l'angle.]{\includegraphics[scale=.16]{17.Semi_conjugaison_topologique/fonctions/doublement.pdf}}\quad
1882 %%  \subfigure[Fonction logistique.]{\includegraphics[scale=.16]{17.Semi_conjugaison_topologique/fonctions/logistique.pdf}}\quad
1883 %%  \subfigure[Fonction tente.]{\includegraphics[scale=.16]{17.Semi_conjugaison_topologique/fonctions/tente.pdf}}
1884 %%\end{center}
1885 %%\caption{Exemples de fonctions chaotiques.}
1886 %%\end{figure}
1887 %%}
1888
1889
1890
1891
1892
1893 %\frame{
1894 %  \frametitle{Les itérations chaotiques $G_{f_0}$ sur $\mathds{R}$}
1895 %\begin{figure}[t]
1896 %\begin{center}
1897 %%  \subfigure[Sur (0,9 ; 1).]{\includegraphics[scale=.16]{17.Semi_conjugaison_topologique/fonctions/ICs09a1.pdf}}\quad
1898 %  \subfigure[Sur (0,7 ; 1).]{\includegraphics[scale=.16]{17.Semi_conjugaison_topologique/fonctions/ICs07a95.pdf}}\quad
1899 %  \subfigure[Sur (0 ; 1).]{\includegraphics[scale=.19]{17.Semi_conjugaison_topologique/fonctions/ICs0a1.pdf}}\quad
1900 %    \subfigure[Sur (510 ; 514).]{\includegraphics[scale=.19]{17.Semi_conjugaison_topologique/fonctions/ICs510a514.pdf}}\quad
1901 %  \subfigure[Sur (1000 ; 1008).]{\includegraphics[scale=.19]{17.Semi_conjugaison_topologique/fonctions/ICs1000a1008.pdf}}
1902 %\end{center}
1903 %\caption{Les itérations chaotiques.}
1904 %\end{figure}
1905 %}
1906
1907
1908
1909
1910 %\frame{
1911 %  \frametitle{Les itérations chaotiques sur $\mathds{R}$}
1912 %\begin{figure}[t]
1913 %\begin{center}
1914 %  \subfigure[Sur (510 ; 514).]{\includegraphics[scale=.16]{17.Semi_conjugaison_topologique/fonctions/ICs510a514.pdf}}\quad
1915 %  \subfigure[Sur (1000 ; 1008).]{\includegraphics[scale=.16]{17.Semi_conjugaison_topologique/fonctions/ICs1000a1008.pdf}}\quad
1916 %  \subfigure[Sur (40 ; 70).]{\includegraphics[scale=.16]{17.Semi_conjugaison_topologique/fonctions/ICs40a70.pdf}}
1917 %\end{center}
1918 %\caption{Les itérations chaotiques.}
1919 %\end{figure}
1920 %}
1921
1922
1923
1924
1925
1926
1927 % \frame{
1928 %   \frametitle{Chaos des IC $G_{f_0}$ sur $\mathds{R}$}
1929 %   \begin{exampleblock}{Chaos de Devaney sur $\mathds{R}$}
1930 % Les IC sur $\mathds{R}$ sont chaotiques selon Devaney, quand $\mathds{R}$ a sa topologie usuelle.
1931 % \end{exampleblock}
1932
1933 % \vspace{0.5cm}
1934
1935 %   \begin{exampleblock}{Exposant de Lyapunov}
1936 % %$\forall x^0 \in \mathcal{L}$, l'exposant de Lyapunov des itérations chaotiques ayant $x^0$ pour condition initiale vaut
1937 % $$\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).$$
1938 % \end{exampleblock}
1939 % }
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952 %\frame{
1953 %  \frametitle{Systèmes itératifs et suites récurrentes}
1954 %  \begin{alertblock}{Les systèmes itératifs sont des suites récurrentes}
1955 %  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
1956 %    $$\left\{
1957 %  \begin{array}{l}
1958 %    X^0 = (x^0,0,0, \hdots) \in \mathcal{X}^\mathds{N}\\
1959 %    X^{n+1} = F(X^n)
1960 %  \end{array}
1961 %  \right.$$
1962 %  tend vers la suite $(x^0,x^1,x^2,\hdots)$.
1963 %  \end{alertblock}
1964 %  \uncover<2->{
1965 %  Etudions un cas particulier : les « Itérations chaotiques »}
1966 %}
1967
1968 \section{Conclusion}
1969
1970
1971 \bibliographystyle{plain}
1972 \bibliography{mabase}
1973
1974 \end{document}