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