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