presPRNG.tex

   1 \documentclass[compress]{beamer}
   2
   3 \usetheme[compress]{Ilmenau}
   4 \setbeamertemplate{items}[ball]
   5 \usenavigationsymbolstemplate{}
   6
   7 \usepackage{thumbpdf}
   8 \usepackage[LY1]{fontenc}
   9 \usepackage[utf8]{inputenc}
  10 \usepackage{pifont}
  11 \usepackage{amsmath}
  12 \usepackage{wasysym}
  13 \usepackage{amsfonts}
  14 \usepackage{dsfont}
  15 \usepackage{tabularx}
  16 \usepackage{graphicx}
  17 \usepackage{ifthen}
  18 \usepackage[francais]{babel}
  19 \usepackage{rotating}
  20 \usepackage{algorithm2e}
  21 \usepackage{stmaryrd}
  22
  23 \graphicspath{{Figures/}}
  24
  25 %\includeonlyframes{1,2,3,4,5,6,7,8,9,10,11,15,17,18,19,20,21,22,23,24,25,26,28,29,30,31,32,33,34,35,36,37,38,39,bibliocont,bibliodisc}
  26 %\includeonlyframes{6}
  27
  28 \newboolean{acroread}
  29 \setboolean{acroread}{true}
  30 \newcommand{\Bool}[0]{\ensuremath{\mathds{B}}}
  31 \newcommand{\N}{\mathbb N}
  32 \newcommand{\R}{\mathbb R}
  33 \newcommand{\Z}{\mathbb Z}
  34 \newcommand{\Q}{\mathbb Q}
  35 \newcommand{\C}{\mathbb C}
  36 \newlength{\tl}
  37 \newcommand{\attention}{%
  38   \settowidth{\tl}{$\triangle$}%
  39   \makebox[0pt][l]{$\triangle$}%
  40   \makebox[\tl][c]{\raisebox{.2ex}{\tiny\string!}}}
  41 \newcommand{\hauteur}[2]{\raisebox{0pt}[#1][-#1]{#2}}
  42 \def\oeuvre{\oe uvre }
  43 \def\oeuvrepv{\oe uvre}
  44 \newcommand{\bleu}[1]{\color{blue}{#1}}
  45
  46 %\newenvironment{myitemize}[1]{
  47 %%  \setlength{\topsep}{#1mm}
  48 %  \begin{itemize}
  49 %%    \setlength{\partopsep}{#1mm}
  50 %    \setlength{\itemsep}{#1}
  51 %  }
  52 %  {\end{itemize}
  53 %}
  54
  55 %\newcounter{selection}
  56 %\setcounter{selection}{0}
  57 %\newcounter{num}
  58 %\setcounter{num}{0}
  59
  60 \newcommand{\frameselect}[2]{
  61   % \addtocounter{num}{1}
  62   \ifthenelse{\boolean{#1}}%\value{selection}=0 \or
  63     % \value{num}=\value{selection}}
  64   {
  65     #2
  66   }{}
  67 }
  68
  69 \newenvironment{algo}[0] {
  70   \begin{quotation}
  71   \begin{tabbing}
  72   \hspace{5mm}\=\hspace{5mm}\=\hspace{5mm}\=\hspace{5mm}\= \kill} %
  73  { \end{tabbing}\end{quotation}}
  74
  75 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  76 % TITRE
  77 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  78 \author{Sylvain Contassot-Vivier$^1$ et Jean-François Couchot$^2$}
  79
  80 \title{Construction de codes de Gray équilibrés \\et forme canonique}
  81 %\subtitle{Habilitation à Diriger des Recherches}
  82
  83 \date{1 - Équipe Simbiot - LORIA - Université de Lorraine\\
  84 2 - Équipe AND - FEMTO-ST - Univ. Bourgogne Franche-Comté
  85 }
  86
  87 \begin{document}
  88
  89 \frameselect{true}{
  90   \begin{frame}[label=1]
  91     \titlepage
  92   \end{frame}
  93 }
  94
  95 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  96 % Méthode R-C
  97 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  98
  99 \section{Introduction}
 100
 101 \frameselect{true}{
 102   \begin{frame}
 103     \frametitle{Pseudo Random Number Generation}
 104 \vspace{-1.5em}
 105 \begin{itemize}
 106 \item Fields of Applications:
 107 \vspace{-0.5em}
 108 \begin{itemize}
 109 \item Security: hash function, steganography, cryptography
 110 \item Time Synchronization: GPS
 111 \item Numerical simulations: Monte-Carlo algorithms
 112 \end{itemize}
 113 \item Some requirements:
 114 \vspace{-0.5em}
 115 \begin{itemize}
 116 \item For cryptography: cryptographically secure
 117 \item Successful pass on PRNG batteries of tests:
 118 NIST\footnote{E.~Barker and A.~Roginsky.
 119   Draft {N}{I}{S}{T} special publication 800-131 recommendation for the
 120   transitioning of cryptographic algorithms and key sizes, 2010.},
 121 DieHARD\footnote{G.~Marsaglia.
 122  DieHARD: a battery of tests of randomness.
 123  {\em http://stat.fsu.edu/~geo/diehard.html}, 1996}
 124 \item Should have chaos properties
 125 \end{itemize}
 126 \end{itemize}
 127   \end{frame}
 128 }
 129
 130 \frameselect{true}{
 131   \begin{frame}
 132     \frametitle{Our PRNG}
 133 \begin{block}{PRNG $\chi_{\textit{14Secrypt}}$}
 134 \begin{algorithm}[H]
 135 %\begin{scriptsize}
 136 \KwIn{a function $f$, an iteration number $b$, a \textit{Random} PRNG, an initial configuration $x^0$ ($n$ bits)}
 137 \KwOut{a configuration $x$ ($n$ bits)}
 138 $x\leftarrow x^0$\;
 139 \For{$i=0,\dots,b-1$}
 140 {
 141 $s\leftarrow{\textit{Random}(n)}$\;
 142 $x\leftarrow{F_f(s,x)}$\;
 143 }
 144 return $x$\;
 145 %\end{scriptsize}
 146 \end{algorithm}
 147 \end{block}
 148 $$
 149 F_f:  \Bool^{{\mathsf{N}}} \times \llbracket1;{\mathsf{N}} \rrbracket \to \Bool^{\mathsf{N}},
 150 F_f(x,i)=(x_1,\dots,x_{i-1},f_i(x),x_{i+1},\dots,x_{\mathsf{N}}).
 151 $$
 152   \end{frame}
 153 }
 154
 155 \frameselect{true}{
 156   \begin{frame}
 157     \frametitle{Random Walk in a modified $\mathsf{N}$-cube}
 158
 159 \begin{block}{}
 160 \begin{itemize}
 161 \item ${\mathsf{N}}=3$, $f^*: \Bool^3 \rightarrow \Bool^3$ s.t.
 162 $$
 163 f^*(x_1,x_2,x_3) =
 164 (x_2 \oplus x_3, \overline{x_1}\overline{x_3} + x_1\overline{x_2},
 165 \overline{x_1}\overline{x_3} + x_1x_2)$$
 166 \item Iteration graph $\Gamma(f^*)$ of this function:
 167 \includegraphics[width=0.45\textwidth]{images/iter_f0c}
 168 \end{itemize}
 169 \end{block}
 170 \end{frame}
 171 }
 172
 173
 174 \frameselect{true}{
 175   \begin{frame}
 176     \frametitle{Chaotic PRNG with verified statistical properties}
 177
 178 \begin{exampleblock}{Previous work}
 179 To provide a PRNG with the properties of Devaney's chaos and of succeeding NIST test: a (non-chaotic) PRNG + iterating a Boolean maps~\footnote{J. Bahi, J.-F. Couchot, C. Guyeux, and A. Richard.
 180  On the link between strongly connected iteration graphs and chaotic
 181   Boolean discrete-time dynamical systems, {\em
 182   Fundamentals of Computation Theory}, volume 6914 of {\em LNCS}, pages 126--137. Springer, 2011.}:
 183 \begin{itemize}
 184 \item with strongly connected iteration graph $\Gamma(f)$
 185 \item with doubly stochastic Markov probability matrix
 186 \end{itemize}
 187 \end{exampleblock}
 188 \end{frame}
 189 }
 190
 191
 192 \frameselect{true}{
 193   \begin{frame}
 194     \frametitle{A solution to find ``good'' $\Gamma(f)$}
 195
 196 \begin{theorem}{}
 197 Let $\Gamma$ be the $n$-cube in which an Hamiltonian  cycle is removed:
 198 $\Gamma$ is strongly connected and the
 199 resulting Markov matrix is doubly stochastic.
 200 \end{theorem}
 201
 202
 203 \begin{block}{We are then left to }
 204   \begin{itemize}
 205   \item  Focus on the generation of Hamiltonian cycles in the
 206     $n$-cube
 207   \item Find cyclic Gray codes.
 208   \end{itemize}
 209 \end{block}
 210 \footnote{Couchot, J., Héam, P., Guyeux, C., Wang, Q.,  Bahi, J. M. [2014]
 211  Pseudorandom number generators with balanced gray codes,
 212  SECRYPT 2014 - Proceedings of the 11th International Conference on
 213 Security and Cryptography, Vienna, Austria, 28-30 August, 2014, pp. 469--475}
 214
 215 \end{frame}
 216 }
 217
 218
 219 \frame{\frametitle{Outline}\tableofcontents[hideallsubsections]}
 220
 221
 222
 223 \section{Codes de Gray équilibrés}
 224 \frame{\frametitle{Outline}\tableofcontents[currentsection,hideallsubsections]}
 225
 226 \frameselect{true}{
 227   \begin{frame}[label=2]
 228     \frametitle{Méthode R-C de construction de CG}
 229
 230     Méthode de Robinson-Cohn :
 231     \begin{itemize}
 232     \item Méthode inductive
 233     \item Produit un CG à N bits à partir d'un CG à N-2 bits
 234       \begin{itemize}
 235       \item Séquence connue de transitions $S_{N-2} = (s_1,...,s_{2^{N-2}})$
 236       \item Codées par la dimension empruntée lors de chaque déplacement du code\\
 237         $\Rightarrow$ $1\le s_i \le N-2$
 238       \end{itemize}
 239     \end{itemize}
 240
 241     Définitions :
 242     \begin{itemize}
 243     \item $u^R$ est le renversé de la séquence $u$
 244     \item $u'(u, x, y) = (u,x,u^R,y,u)$
 245     \end{itemize}
 246   \end{frame}
 247 }
 248
 249 \frameselect{true}{
 250   \begin{frame}
 251     \frametitle{Méthode R-C de construction de CG}
 252     Algorithme :
 253     \begin{enumerate}
 254     \item Pour $l$ un entier pair, décomposer $S_{N-2}$ en une séquence :\\
 255       \centerline{$(s_{i_1}, \underline{u_0}, s_{i_2}, \underline{u_1}, s_{i_3}, \underline{u_2}, \dots , s_{i_l-1}, \underline{u_{l-2}}, s_{i_l}, \underline{v})$}
 256       où les $u_i$ sont des ss-séqs éventuellement vides de $S_{N-2}$\\
 257       et $u_0 = \emptyset$, $i_1 = 1$, $i_2 = 2$ et $v$ éventuellement $\emptyset$.
 258     \item Obtenir une nouvelle séquence $U$ en remplaçant :
 259       \begin{itemize}
 260       \item $u_0$ par $N-1$
 261       \item $u_{2i+1}$ par $u'(u_{2i+1},N-1,N)$
 262       \item $u_{2i}$ par $u'(u_{2i},N,N-1)$
 263       \end{itemize}
 264     \item Construire les séquences :\\
 265       \begin{itemize}
 266       \item $V=(v^R,N,v)$
 267       \item $W=(N-1,S_{N-2},N)$
 268       \item $W'=(w_2,w_1,W_{[3:]})$ \hfill(inversion des 2 1ers élts de $W$)
 269       \end{itemize}
 270     \item $S_{N} = (U^R, V, W')$
 271     \end{enumerate}
 272   \end{frame}
 273 }
 274
 275 \frameselect{true}{
 276   \begin{frame}
 277     \frametitle{Méthode R-C de construction de CG}
 278     \textbf{Exemple 1} : $N = 5$ et $S_3 = (1,2,1,3,1,2,1,3)$
 279     \begin{enumerate}
 280     \item le choix $l=2$ implique : $S_3=(s_{1}, \underline{u_0}, s_{2},v)$\\
 281       avec $v = (s_3,...,s_{2^{N-2}}) = (1,3,1,2,1,3)$
 282     \item on obtient $U = (s_1, 4, s_2, s_3,...,s_{2^{N-2}}) = (1,4,2,1,3,1,2,1,3)$
 283     \item et les séquences :\\
 284       \begin{itemize}
 285       \item $V= (v^R,N,v) = (3,1,2,1,3,1,5,1,3,1,2,1,3)$
 286       \item $W=(N-1,S_{N-2},N)=(4,1,2,1,3,1,2,1,3,5)$
 287       \item $W'=(w_2,w_1,W_{[3:]})=(1,4,2,1,3,1,2,1,3,5)$
 288       \end{itemize}
 289     \item $S_{N} = (U^R, V, W')=(\underline{3,1,2,1,3,1,2,4,1},$\\
 290       \hspace{9em} $3,1,2,1,3,1,5,1,3,1,2,1,3,$\\
 291       \hspace{9em} $1,4,2,1,3,1,2,1,3,5)$
 292     \end{enumerate}
 293
 294     Fréquences = 14, 6, 8, 2, 2
 295   \end{frame}
 296 }
 297
 298 \frameselect{true}{
 299   \begin{frame}
 300     \frametitle{Méthode R-C de construction de CG}
 301     \textbf{Exemple 2} : $N = 5$ et $S_3 = (1,2,1,3,1,2,1,3)$
 302     \begin{enumerate}
 303     \item le choix $l=4$ implique : $S_3=(s_{1}, \underline{u_0}, s_{2}, \underline{u_1}, s_{i_3}, \underline{u_2}, s_{i_4},v)$\\
 304       on choisit $u_1=(1,3)$, donc $s_{i_3}=1$\\
 305       et $u_2=(2)$, donc $s_{i_4}=1$ et $v =(3)$
 306     \item on a $u'(u_1,4,5) = (1,3,4,3,1,5,1,3)$\\
 307       et $u'(u_2,5,4) = (2,5,2,4,2)$\\
 308       et donc $U = (1,4,2,\underline{1,3,4,3,1,5,1,3},1,\underline{2,5,2,4,2},1,3)$
 309     \item et les séquences :\\
 310       \begin{itemize}
 311       \item $V= (v^R,N,v) = (3,5,3)$
 312       \item $W$ et $W'$ comme précédemment
 313       \end{itemize}
 314     \item $S_{N} = (U^R, V, W')=(\underline{3,1,2,4,2,5,2,1,3,1,5,1,3,4,3,}$\\
 315       \hspace{9em} $\underline{1,2,4,1},3,5,3,$\\
 316       \hspace{9em} $1,4,2,1,3,1,2,1,3,5)$
 317     \end{enumerate}
 318
 319     Fréquences = 10, 6, 8, 4, 4
 320   \end{frame}
 321 }
 322
 323 \frameselect{true}{
 324   \begin{frame}
 325     \frametitle{Problématique des CG équilibrés}
 326
 327     L'algo précédent n'est pas \textbf{constructif}\\
 328     $\rightarrow$ pas d'indication sur le choix de $l$ et des $u_i$ !
 329     \vspace{1em}
 330
 331     Formalisation de l'équilibre d'un CG :
 332     \begin{itemize}
 333     \item Soit $TC_N : \{1,\dots, N\} \rightarrow \{0, \ldots, 2^N\}$\\
 334       nb d'occurrences d'une dimension dans une séquence
 335     \item un CG est \textbf{équilibré} ssi :\\
 336       \centerline{$\forall i,j\in \{1,...,N\},~|TC_N(i) - TC_N(j)|\le 2$}
 337     \item il est \textbf{totalement équilibré} ssi:\\
 338       \centerline{$\forall i\in \{1,...,N\},~TC_N(i) = \frac{2^N}{N}$}
 339     \end{itemize}
 340     \vspace{1em}
 341
 342     On a  montré qu'il existe au  moins un choix  de $(u_i)$ dans l'algo  RC qui
 343     donne un CG équilibré.
 344   \end{frame}
 345 }
 346
 347 \frameselect{true}{
 348   \begin{frame}
 349     \frametitle{Construction de CG équilibrés}
 350
 351     L'idée est de :
 352     \begin{itemize}
 353     \item Compter pour chaque dimension, les occurrences générées par l'algo RC :
 354       \begin{itemize}
 355       \item Pour les dimensions $N-1$ et $N$ on arrive à $l$
 356       \item Pour les autres, on établit une formulation dépendant :
 357         \begin{itemize}
 358         \item des occurrences dans la séquence initiale $S_{N-2}$
 359         \item des choix d'inclusion ou non dans les $s_{i_j}$, $u_i$ et $v$ :
 360           $TC_N(k)=TC(k, \cup_j(s_{i_j})) + 3\times ( TC(k, \cup_iu_i) + TC(k, v)) + TC_{N-2}(k)$\\
 361         \end{itemize}
 362       \end{itemize}
 363     \item Appliquer la contrainte d'équilibre aux formulations obtenues
 364     \end{itemize}
 365
 366     \begin{center}
 367       $\Rightarrow$ On en déduit le nombre d'occurrences de chaque dimension à
 368       insérer dans les $s_{i_j}$, $u_i$ et $v$
 369     \end{center}
 370   \end{frame}
 371 }
 372
 373 \frameselect{true}{
 374   \begin{frame}
 375     \frametitle{Construction de CG équilibrés}
 376
 377     Exemple : $S_2 = (1,2,1,2)$
 378     \begin{itemize}
 379     \item Pour avoir l'équilibre final, $l$ doit valoir 4
 380     \item On en déduit une décomposition de la forme :\\
 381       $S_2 = (s_{i_1},u_0,s_{i_2},u_1,s_{i_3},u_2,s_{i_4},v)$ et $s_{i_1}=1$, $u_0=\emptyset$, $s_{i_2}=2$
 382     \item Or, on a : $TC_2(1) = 2$ et $TC_2(2)=2$
 383     \item Et pour $k=1$ et $k=2$, il faut vérifier :
 384       $TC(k, \cup_j(s_{i_j})) + 3\times ( TC(k, \cup_iu_i) + TC(k, v)) + TC_2(k)=4$\\
 385       $TC(k, \cup_j(s_{i_j})) + 3\times ( TC(k, \cup_iu_i) + TC(k, v))=2$\\
 386       $\Rightarrow TC(k, \cup_iu_i) + TC(k, v) = 0$\\
 387       $\Rightarrow TC(k, \cup_j(s_{i_j}))=2$
 388     \item Donc $u_0,u_1,u_2$ et $v$ doivent être vides !
 389     \end{itemize}
 390   \end{frame}
 391 }
 392
 393 \frameselect{true}{
 394   \begin{frame}
 395     \frametitle{Construction de CG équilibrés}
 396
 397     Comme $u_0,u_1,u_2$ et $v$ sont vides, on a :
 398     \begin{itemize}
 399     \item $u'(u_1,3,4) = (3,4)$
 400     \item $u'(u_2,4,3) = (4,3)$
 401     \item $U = (1,3,2,3,4,1,4,3,2)$
 402     \item $V= (v^R,N,v) = (4)$
 403     \item $W=(N-1,S_{N-2},N)=(3,1,2,1,2,4)$
 404     \item $W'=(w_2,w_1,W_{[3:]})=(1,3,2,1,2,4)$
 405     \item $S_{4} = (U^R, V, W')=(2,3,4,1,4,3,2,3,1,4,1,3,2,1,2,4)$
 406     \end{itemize}
 407     \begin{center}
 408       $\Rightarrow$ Fréquences = 4, 4, 4, 4
 409     \end{center}
 410   \end{frame}
 411 }
 412
 413 \frameselect{true}{
 414   \begin{frame}
 415     \frametitle{Algo de construction de CG équilibrés}
 416
 417     Une fois  déterminés les nombres d'occurrences  à placer dans les  $u_i$, il
 418     faut construire la séquence :
 419     \begin{itemize}
 420     \item Parcours exhaustif :
 421       \begin{itemize}
 422       \item [$\frownie$] Coûteux
 423       \item [$\smiley$] Produit tous les CG équilibrés atteignables par cette méthode
 424       \end{itemize}
 425     \item Algorithme glouton :
 426       \begin{itemize}
 427       \item Construction des $u_i$ dans l'ordre
 428       \item  Choix  glouton  pour  chaque  $u_i$ :\\
 429         sous-séquence  maximale  de  $S_{N-2}$   vérifiant  les  nombres  totaux
 430         d'occurrences déterminés pour les $u_i$
 431       \end{itemize}
 432     \item [$\frownie$] Ne produit pas tous les CGE possibles !
 433     \item [$\smiley$] Produit rapidement un CG pour n'importe quelle dimension !\\
 434       (à partir des dimensions 2 et 3)
 435     \end{itemize}
 436   \end{frame}
 437 }
 438
 439 \frameselect{true}{
 440   \begin{frame}
 441     \frametitle{Algo de construction de tous les CG équilibrés}
 442
 443     Algo basé sur la méthode de M.~Wild :
 444     \begin{itemize}
 445     \item Basé sur le principe d'exclusion
 446     \item Liste des arêtes du N-cube
 447     \item Chaque arête prend un état dans l'ensemble $\{0,1,2,g,d\}$ :
 448       \begin{itemize}
 449       \item 0 pour supprimée, 1 pour incluse, 2 pour indéterminé (initial)
 450       \item $g$ pour un ensemble d'arêtes dont une seule est incluse
 451       \item $d$ pour un ensemble d'arêtes dont deux sont incluses
 452       \end{itemize}
 453     \item Ajouts successifs des noeuds en appliquant :
 454       \begin{itemize}
 455       \item Condition locale (chaque noeud) : degré 2
 456       \item Conditions globales : \\
 457         cycle max : nb arêtes à 1 = nb sommets\\
 458         cycles inf : pas de cycles < nb sommets
 459       \item [$\Rightarrow$] élagage dès qu'une contrainte n'est pas vérifiée
 460       \end{itemize}
 461     \end{itemize}
 462   \end{frame}
 463 }
 464
 465 \frameselect{true}{
 466   \begin{frame}
 467     \frametitle{Exemple sur le 3-cube}
 468
 469     \begin{center}
 470       \vspace{-.75em}
 471       \includegraphics[width=.3\textwidth]{3-cube.pdf}
 472       \vspace{-.75em}
 473     \end{center}
 474
 475     \begin{block}{}
 476       \small
 477       \vspace{-1.5em}
 478       \begin{center}
 479         \begin{equation*}
 480           \begin{array}[h]{c|cccccccccccc}
 481             \text{arêtes}  & 1         & 2         & 3   & 4   & 5   & 6 & 7   & 8 & 9 & 10 & 11  & 12 \\
 482             \hline
 483             \text{init}    & 2         & 2         & 2   & 2   & 2   & 2 & 2   & 2 & 2 & 2  & 2   & 2  \\
 484             \hline
 485             \text{ajout a} & d_1       & d_1       & 2   & 2   & d_1  & 2 & 2   & 2 & 2 & 2  & 2   & 2  \\
 486             \hline
 487             \text{ajout b} & \alert{1} & \bleu{g_1} & 2   & \bleu{g_2} & \bleu{g_1}  & 2 & 2   & 2 & 2 & 2  & \bleu{g_2} & 2  \\
 488                            & \alert{0} & \bleu{1}         & 2   & \bleu{1}   & \bleu{1}   & 2 & 2   & 2 & 2 & 2  & \bleu{1}   & 2  \\
 489             \hline
 490             \text{ajout c} & 1         & \alert{1} & \bleu{g_3} & g_2 & \bleu{0}   & 2 & \bleu{g_3} & 2 & 2 & 2  & g_2 & 2  \\
 491                            & 1         & \alert{0} & \bleu{1}   & g_2 & \bleu{1}   & 2 & \bleu{1}   & 2 & 2 & 2  & g_2 & 2  \\
 492                            & 0         & 1         & \bleu{g_3} & 1   & 1   & 2 & \bleu{g_3} & 2 & 2 & 2  & 1   & 2  \\
 493           \end{array}
 494         \end{equation*}
 495       \end{center}
 496     \end{block}
 497   \end{frame}
 498 }
 499
 500 \frameselect{true}{
 501   \begin{frame}
 502     \frametitle{Adaptation au contexte de N-cube}
 503
 504     \begin{itemize}
 505     \item Ajout de la contrainte d'équilibre dans l'élagage
 506     \item Utilisation d'une forme canonique des CG :\\
 507       \begin{itemize}
 508       \item [$\Rightarrow$] Unicité des représentants
 509       \item [$\Rightarrow$] Ordre global sur les représentants :
 510         \begin{itemize}
 511         \item Détection efficace des doublons
 512         \item Stockage minimal
 513         \end{itemize}
 514       \end{itemize}
 515     \end{itemize}
 516   \end{frame}
 517 }
 518
 519 \frameselect{true}{
 520   \begin{frame}
 521     \frametitle{Forme canonique des CG}
 522
 523     \begin{itemize}
 524     \item Alignement sur début d'une sous-séquence avec \textbf{écart max} :
 525       \begin{itemize}
 526       \item Plus grand intervalle entre 2 occurrences d'une même dimension
 527       \end{itemize}
 528     \item Écart max sur l'ensemble des dimensions = \textbf{équilibre local}
 529     \item Renumérotation des dimensions :
 530       \begin{itemize}
 531       \item Affectation dans l'ordre croissant des no \hfill$\Rightarrow$ débuts = (1,2)
 532       \item Équivalent à des isomorphismes du N-cube
 533       \item Donne un ordre global \hfill$\Rightarrow$ tri possible
 534       \end{itemize}
 535     \item Travaux en cours :
 536       \begin{itemize}
 537       \item Unicité de la forme canonique pour une classe d'isomorphismes
 538       \item Deux formes canoniques distinctes ne sont pas isomorphes
 539       \end{itemize}
 540     \end{itemize}
 541     \begin{center}
 542       $\Rightarrow$ Génération exhaustive en accord avec la théorie (dims $\le$ 5)
 543     \end{center}
 544   \end{frame}
 545 }
 546
 547
 548 \section{Temps de mélange pour une distribution uniforme}
 549 \frame{\frametitle{Outline}\tableofcontents[currentsection,hideallsubsections]}
 550
 551
 552 \frameselect{true}{
 553   \begin{frame}
 554     \frametitle{Mixing time upper bound}
 555     \begin{itemize}
 556     \item Evaluated in a (lazy) context
 557     \item $t_{\rm mix}(\varepsilon)$: the steps required to be sure to be $\varepsilon$-close
 558       to the stationary uniform distribution
 559     \item Theoretical result: $t_{\rm mix}\leq 32N^2+16N\ln (N+1)=O(N^2)$
 560     \item In practice: in $N\ln(N)$
 561     \end{itemize}
 562   \end{frame}
 563 }
 564
 565
 566 \section{Experiments}
 567 \frame{\frametitle{Outline}\tableofcontents[currentsection,hideallsubsections]}
 568
 569
 570
 571 \frameselect{true}{
 572   \begin{frame}
 573     \frametitle{Functions with DSCC Matrix and smallest MT}
 574     \begin{center}
 575 \begin{scriptsize}
 576   \begin{tabular}{|c|c|c|c|}
 577     \hline
 578 Function $f$ & $f(x)$, for $x$ in $(0,1,2,\hdots,2^n-1)$ & $\mathsf{N}$ & $b$
 579 \\
 580 \hline
 581 %%%%% n= 4
 582 $\textcircled{a}$&[13,10,9,14,3,11,1,12,15,4,7,5,2,6,0,8]&4&64\\
 583 \hline
 584 %%%%% n= 5
 585 $\textcircled{b}$&
 586 [29, 22, 25, 30, 19, 27, 24, 16, 21, 6, 5, 28, 23, 26, 1, 17, & 5 & 78 \\
 587 &
 588  31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 7, 20, 11, 18, 0, 4]
 589 &&\\
 590 %%%%% n= 6
 591 \hline
 592 &
 593 [55, 60, 45, 44, 58, 62, 61, 48, 53, 50, 52, 36, 59, 34, 33, 49,
 594 &&\\
 595 &
 596  15, 42, 47, 46, 35, 10, 57, 56, 7, 54, 39, 37, 51, 2, 1, 40, 63,
 597 &&\\
 598 $\textcircled{c}$&
 599  26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, 16, 24, 13,
 600 &6&88\\
 601 &
 602 12, 29, 8, 43, 14, 41, 0, 5, 38, 4, 6, 11, 3, 9, 32]
 603 &&\\
 604 %%%%% n= 7
 605 \hline
 606 &
 607 [111, 124, 93, 120, 122, 114, 89, 121, 87, 126, 125, 84, 123, 82,
 608 &&\\
 609 &112, 80, 79, 106, 105, 110, 75, 107, 73, 108, 119, 100, 117, 116,
 610 &&\\
 611 &103, 102, 101, 97, 31, 86, 95, 94, 83, 26, 88, 24, 71, 118, 69,
 612 &&\\
 613 &68, 115, 90, 113, 16, 15, 76, 109, 72, 74, 10, 9, 104, 7, 6, 65,
 614 &&\\
 615 $\textcircled{d}$ &70, 99, 98, 64, 96, 127, 54, 53, 62, 51, 59, 56, 60, 39, 52, 37, &7 &99\\
 616 &36, 55, 58, 57, 49, 63, 44, 47, 40, 42, 46, 45, 41, 35, 34, 33,
 617 &&\\
 618 &38, 43, 50, 32, 48, 29, 28, 61, 92, 91, 18, 17, 25, 19, 30, 85,
 619 &&\\
 620 &22, 27, 2, 81, 0, 13, 78, 77, 14, 3, 11, 8, 12, 23, 4, 21, 20,
 621 &&\\
 622 &67, 66, 5, 1]
 623 &&\\
 624
 625
 626 %%%%%n=8
 627 \hline
 628 $\textcircled{e}$& \ldots &8&109\\
 629  \hline
 630 \end{tabular}
 631 \end{scriptsize}
 632 \end{center}
 633 \end{frame}
 634 }
 635
 636 \frameselect{true}{
 637   \begin{frame}
 638     \frametitle{Nist Test Results}
 639 \begin{itemize}
 640 \item Embedded PRNG \textit{Random}: Mersenne Twister algorithm~\footnote{Mersenne twister: a 623-dimensionally
 641     equidistributed uniform pseudo-random number generator, (TOMACS) 8 , 3--30}
 642 \item Adding chaos properties for Mersenne Twister algorithm:  security  is not reduced w.r.t. NIST
 643 \end{itemize}
 644 \end{frame}
 645 }
 646
 647 \section{Conclusion}
 648
 649 \frameselect{true}{
 650   \begin{frame}
 651     \frametitle{Summary}
 652 \begin{itemize}
 653 \item Chaos properties can be added to PRNGs
 654 \item Iterated map: built by removing from a $\mathsf{N}$-cube a balanced  Hamiltonian cycle
 655 \item Efficient method to compute balanced Hamiltonian cycles
 656 \item Upper bound  (quadratic) on the number of iterations
 657 that is sufficient to obtain an uniform distribution of the output
 658 \item The first time a full automatic method to provide chaotic PRNGs is given
 659 \end{itemize}
 660 \end{frame}
 661 }
 662
 663
 664 \frameselect{true}{
 665   \begin{frame}
 666     \frametitle{Perspectives}
 667 \begin{itemize}
 668 \item Actuellement: si le cycle hamiltonien
 669 change le $l^{\textrm{ème}}$ bit entre les n{\oe}uds $X$ et $Y$, alors
 670 le $l^{\textrm{ème}}$ bit entre $Y$ et $Z$, ne peut pas être changé.
 671 \item Si le cycle hamiltonien est globalement équilibré:
 672 la probabilité de changer un bit $l'$, $ l' \neq l$, entre $Y$ et $Z$
 673 est $\frac{1}{\mathsf{N}-1}$ $\leadsto$ à intégrer.
 674 \item Actuellement: marcher dans une partie d'un $\mathsf{N}$-cube
 675 \item Futur: modifier plusieurs bits  en une seule itération (sauter dans cette partie du $\mathsf{N}$-cube)
 676 \end{itemize}
 677 \end{frame}
 678 }
 679
 680
 681   \begin{frame}
 682     \frametitle{Perspectives}
 683 \begin{itemize}
 684 \item Qu'est-ce qu'un $\mathsf{N}$-cube?
 685 \item Justifier les trois arrêtes sortantes du n{\oe}ud $010$ de la figure~1.
 686 \item Illustrer à l'aide d'un graphe le fait que la fonction $f^*$, définie au milieu de la~page~3  est un 3-cube privé d'un cycle hamiltonien.
 687 \item Pourquoi l'extension de Robinson-Cohn (page 11) n'est-elle pas un algorithme? A quoi sert la démonstration de la section 5.2?
 688 \item Quel est l'objectif de la section~6?
 689 Ordonner les lemmes et théorèmes de cette section pour dégager le résultat
 690 final.
 691 \item Expliquer toutes les informations que l'on peut trouver dans la seconde
 692 ligne du tableau de la page 18 (ligne portant le libéllé \og function \textcircled{a}\fg{}.
 693 \end{itemize}
 694 \end{frame}
 695
 696
 697
 698 \end{document}
 699
 700 %%% Local Variables:
 701 %%% mode: latex
 702 %%% TeX-master: t
 703 %%% End: