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 \newcommand{\bleu}[1]{\color{blue}{#1}}
  44
  45 %\newenvironment{myitemize}[1]{
  46 %%  \setlength{\topsep}{#1mm}
  47 %  \begin{itemize}
  48 %%    \setlength{\partopsep}{#1mm}
  49 %    \setlength{\itemsep}{#1}
  50 %  }
  51 %  {\end{itemize}
  52 %}
  53
  54 %\newcounter{selection}
  55 %\setcounter{selection}{0}
  56 %\newcounter{num}
  57 %\setcounter{num}{0}
  58
  59 \newcommand{\frameselect}[2]{
  60   % \addtocounter{num}{1}
  61   \ifthenelse{\boolean{#1}}%\value{selection}=0 \or
  62     % \value{num}=\value{selection}}
  63   {
  64     #2
  65   }{}
  66 }
  67
  68 \newenvironment{algo}[0] {
  69   \begin{quotation}
  70   \begin{tabbing}
  71   \hspace{5mm}\=\hspace{5mm}\=\hspace{5mm}\=\hspace{5mm}\= \kill} %
  72  { \end{tabbing}\end{quotation}}
  73
  74 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  75 % TITRE
  76 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  77 \author{Sylvain Contassot-Vivier$^1$ et Jean-François Couchot$^2$}
  78
  79 \title{Construction de codes de Gray équilibrés \\et forme canonique}
  80 %\subtitle{Habilitation à Diriger des Recherches}
  81
  82 \date{1 - Équipe Simbiot - LORIA - Université de Lorraine\\
  83 2 - Équipe AND - FEMTO-ST - Univ. Bourgogne Franche-Comté
  84 }
  85
  86 \begin{document}
  87
  88 \frameselect{true}{
  89   \begin{frame}[label=1]
  90     \titlepage
  91   \end{frame}
  92 }
  93
  94 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  95 % Méthode R-C
  96 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  97
  98 \section{Introduction}
  99
 100 \frameselect{true}{
 101   \begin{frame}
 102     \frametitle{Pseudo Random Number Generation}
 103 \vspace{-1.5em}
 104 \begin{itemize}
 105 \item Fields of Applications:
 106 \vspace{-0.5em}
 107 \begin{itemize}
 108 \item Security: hash function, steganography, cryptography
 109 \item Time Synchronization: GPS
 110 \item Numerical simulations: Monte-Carlo algorithms
 111 \end{itemize}
 112 \item Some requirements:
 113 \vspace{-0.5em}
 114 \begin{itemize}
 115 \item For cryptography: cryptographically secure
 116 \item Successful pass on PRNG batteries of tests:
 117 NIST\footnote{E.~Barker and A.~Roginsky.
 118   Draft {N}{I}{S}{T} special publication 800-131 recommendation for the
 119   transitioning of cryptographic algorithms and key sizes, 2010.},
 120 DieHARD\footnote{G.~Marsaglia.
 121  DieHARD: a battery of tests of randomness.
 122  {\em http://stat.fsu.edu/~geo/diehard.html}, 1996}
 123 \item Should have chaos properties
 124 \end{itemize}
 125 \end{itemize}
 126   \end{frame}
 127 }
 128
 129 \frameselect{true}{
 130   \begin{frame}
 131     \frametitle{Our PRNG}
 132 \begin{block}{PRNG $\chi_{\textit{14Secrypt}}$}
 133 \begin{algorithm}[H]
 134 %\begin{scriptsize}
 135 \KwIn{a function $f$, an iteration number $b$, a \textit{Random} PRNG, an initial configuration $x^0$ ($n$ bits)}
 136 \KwOut{a configuration $x$ ($n$ bits)}
 137 $x\leftarrow x^0$\;
 138 \For{$i=0,\dots,b-1$}
 139 {
 140 $s\leftarrow{\textit{Random}(n)}$\;
 141 $x\leftarrow{F_f(s,x)}$\;
 142 }
 143 return $x$\;
 144 %\end{scriptsize}
 145 \end{algorithm}
 146 \end{block}
 147   \end{frame}
 148 }
 149
 150 \frameselect{true}{
 151   \begin{frame}
 152     \frametitle{Random Walk in a modified $\mathsf{N}$-cube}
 153
 154 \begin{block}{}
 155 \begin{itemize}
 156 \item ${\mathsf{N}}=3$, $f^*: \Bool^3 \rightarrow \Bool^3$ s.t.
 157 $$
 158 f^*(x_1,x_2,x_3) =
 159 (x_2 \oplus x_3, \overline{x_1}\overline{x_3} + x_1\overline{x_2},
 160 \overline{x_1}\overline{x_3} + x_1x_2)$$
 161 \item Iteration graph $\Gamma(f^*)$ of this function:
 162 \includegraphics[width=0.45\textwidth]{images/iter_f0c}
 163 \end{itemize}
 164 \end{block}
 165 \end{frame}
 166 }
 167
 168
 169 \frameselect{true}{
 170   \begin{frame}
 171     \frametitle{Chaotic PRNG with verified statistical properties}
 172
 173 \begin{exampleblock}{Previous work}
 174 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.
 175  On the link between strongly connected iteration graphs and chaotic
 176   Boolean discrete-time dynamical systems, {\em
 177   Fundamentals of Computation Theory}, volume 6914 of {\em LNCS}, pages 126--137. Springer, 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 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{Exemple sur le 3-cube}
 463
 464     \begin{center}
 465       \vspace{-.75em}
 466       \includegraphics[width=.3\textwidth]{3-cube.pdf}
 467       \vspace{-.75em}
 468     \end{center}
 469
 470     \begin{block}{}
 471       \small
 472       \vspace{-1.5em}
 473       \begin{center}
 474         \begin{equation*}
 475           \begin{array}[h]{c|cccccccccccc}
 476             \text{arêtes}  & 1         & 2         & 3   & 4   & 5   & 6 & 7   & 8 & 9 & 10 & 11  & 12 \\
 477             \hline
 478             \text{init}    & 2         & 2         & 2   & 2   & 2   & 2 & 2   & 2 & 2 & 2  & 2   & 2  \\
 479             \hline
 480             \text{ajout a} & d_1       & d_1       & 2   & 2   & d_1  & 2 & 2   & 2 & 2 & 2  & 2   & 2  \\
 481             \hline
 482             \text{ajout b} & \alert{1} & \bleu{g_1} & 2   & \bleu{g_2} & \bleu{g_1}  & 2 & 2   & 2 & 2 & 2  & \bleu{g_2} & 2  \\
 483                            & \alert{0} & \bleu{1}         & 2   & \bleu{1}   & \bleu{1}   & 2 & 2   & 2 & 2 & 2  & \bleu{1}   & 2  \\
 484             \hline
 485             \text{ajout c} & 1         & \alert{1} & \bleu{g_3} & g_2 & \bleu{0}   & 2 & \bleu{g_3} & 2 & 2 & 2  & g_2 & 2  \\
 486                            & 1         & \alert{0} & \bleu{1}   & g_2 & \bleu{1}   & 2 & \bleu{1}   & 2 & 2 & 2  & g_2 & 2  \\
 487                            & 0         & 1         & \bleu{g_3} & 1   & 1   & 2 & \bleu{g_3} & 2 & 2 & 2  & 1   & 2  \\
 488           \end{array}
 489         \end{equation*}
 490       \end{center}
 491     \end{block}
 492   \end{frame}
 493 }
 494
 495 \frameselect{true}{
 496   \begin{frame}
 497     \frametitle{Adaptation au contexte de N-cube}
 498
 499     \begin{itemize}
 500     \item Ajout de la contrainte d'équilibre dans l'élagage
 501     \item Utilisation d'une forme canonique des CG :\\
 502       \begin{itemize}
 503       \item [$\Rightarrow$] Unicité des représentants
 504       \item [$\Rightarrow$] Ordre global sur les représentants :
 505         \begin{itemize}
 506         \item Détection efficace des doublons
 507         \item Stockage minimal
 508         \end{itemize}
 509       \end{itemize}
 510     \end{itemize}
 511   \end{frame}
 512 }
 513
 514 \frameselect{true}{
 515   \begin{frame}
 516     \frametitle{Forme canonique des CG}
 517
 518     \begin{itemize}
 519     \item Alignement sur début d'une sous-séquence avec \textbf{écart max} :
 520       \begin{itemize}
 521       \item Plus grand intervalle entre 2 occurrences d'une même dimension
 522       \end{itemize}
 523     \item Écart max sur l'ensemble des dimensions = \textbf{équilibre local}
 524     \item Renumérotation des dimensions :
 525       \begin{itemize}
 526       \item Affectation dans l'ordre croissant des no \hfill$\Rightarrow$ débuts = (1,2)
 527       \item Équivalent à des isomorphismes du N-cube
 528       \item Donne un ordre global \hfill$\Rightarrow$ tri possible
 529       \end{itemize}
 530     \item Travaux en cours :
 531       \begin{itemize}
 532       \item Unicité de la forme canonique pour une classe d'isomorphismes
 533       \item Deux formes canoniques distinctes ne sont pas isomorphes
 534       \end{itemize}
 535     \end{itemize}
 536     \begin{center}
 537       $\Rightarrow$ Génération exhaustive en accord avec la théorie (dims $\le$ 5)
 538     \end{center}
 539   \end{frame}
 540 }
 541
 542
 543 \section{Temps de mélange pour une distribution uniforme}
 544 \frame{\frametitle{Outline}\tableofcontents[currentsection,hideallsubsections]}
 545
 546
 547 \frameselect{true}{
 548   \begin{frame}
 549     \frametitle{Mixing time upper bound}
 550     \begin{itemize}
 551     \item Evaluated in a (lazy) context
 552     \item $t_{\rm mix}(\varepsilon)$: the steps required to be sure to be $\varepsilon$-close
 553       to the stationary uniform distribution
 554     \item Theoretical result: $t_{\rm mix}\leq 32N^2+16N\ln (N+1)=O(N^2)$
 555     \item In practice: in $N\ln(N)$
 556     \end{itemize}
 557   \end{frame}
 558 }
 559
 560
 561 \section{Experiments}
 562 \frame{\frametitle{Outline}\tableofcontents[currentsection,hideallsubsections]}
 563
 564
 565
 566 \frameselect{true}{
 567   \begin{frame}
 568     \frametitle{Functions with DSCC Matrix and smallest MT}
 569     \begin{center}
 570 \begin{scriptsize}
 571   \begin{tabular}{|c|c|c|c|}
 572     \hline
 573 Function $f$ & $f(x)$, for $x$ in $(0,1,2,\hdots,2^n-1)$ & $\mathsf{N}$ & $b$
 574 \\
 575 \hline
 576 %%%%% n= 4
 577 $\textcircled{a}$&[13,10,9,14,3,11,1,12,15,4,7,5,2,6,0,8]&4&64\\
 578 \hline
 579 %%%%% n= 5
 580 $\textcircled{b}$&
 581 [29, 22, 25, 30, 19, 27, 24, 16, 21, 6, 5, 28, 23, 26, 1, 17, & 5 & 78 \\
 582 &
 583  31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 7, 20, 11, 18, 0, 4]
 584 &&\\
 585 %%%%% n= 6
 586 \hline
 587 &
 588 [55, 60, 45, 44, 58, 62, 61, 48, 53, 50, 52, 36, 59, 34, 33, 49,
 589 &&\\
 590 &
 591  15, 42, 47, 46, 35, 10, 57, 56, 7, 54, 39, 37, 51, 2, 1, 40, 63,
 592 &&\\
 593 $\textcircled{c}$&
 594  26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, 16, 24, 13,
 595 &6&88\\
 596 &
 597 12, 29, 8, 43, 14, 41, 0, 5, 38, 4, 6, 11, 3, 9, 32]
 598 &&\\
 599 %%%%% n= 7
 600 \hline
 601 &
 602 [111, 124, 93, 120, 122, 114, 89, 121, 87, 126, 125, 84, 123, 82,
 603 &&\\
 604 &112, 80, 79, 106, 105, 110, 75, 107, 73, 108, 119, 100, 117, 116,
 605 &&\\
 606 &103, 102, 101, 97, 31, 86, 95, 94, 83, 26, 88, 24, 71, 118, 69,
 607 &&\\
 608 &68, 115, 90, 113, 16, 15, 76, 109, 72, 74, 10, 9, 104, 7, 6, 65,
 609 &&\\
 610 $\textcircled{d}$ &70, 99, 98, 64, 96, 127, 54, 53, 62, 51, 59, 56, 60, 39, 52, 37, &7 &99\\
 611 &36, 55, 58, 57, 49, 63, 44, 47, 40, 42, 46, 45, 41, 35, 34, 33,
 612 &&\\
 613 &38, 43, 50, 32, 48, 29, 28, 61, 92, 91, 18, 17, 25, 19, 30, 85,
 614 &&\\
 615 &22, 27, 2, 81, 0, 13, 78, 77, 14, 3, 11, 8, 12, 23, 4, 21, 20,
 616 &&\\
 617 &67, 66, 5, 1]
 618 &&\\
 619
 620
 621 %%%%%n=8
 622 \hline
 623 $\textcircled{e}$& \ldots &8&109\\
 624  \hline
 625 \end{tabular}
 626 \end{scriptsize}
 627 \end{center}
 628 \end{frame}
 629 }
 630
 631 \frameselect{true}{
 632   \begin{frame}
 633     \frametitle{Nist Test Results}
 634 \begin{itemize}
 635 \item Embedded PRNG \textit{Random}: Mersenne Twister algorithm~\footnote{Mersenne twister: a 623-dimensionally
 636     equidistributed uniform pseudo-random number generator, (TOMACS) 8 , 3--30}
 637 \item Adding chaos properties for Mersenne Twister algorithm:  security  is not reduced w.r.t. NIST
 638 \end{itemize}
 639 \end{frame}
 640 }
 641
 642 \section{Conclusion}
 643
 644 \frameselect{true}{
 645   \begin{frame}
 646     \frametitle{Summary}
 647 \begin{itemize}
 648 \item Chaos properties can be added to PRNGs
 649 \item Iterated map: built by removing from a $\mathsf{N}$-cube a balanced  Hamiltonian cycle
 650 \item Efficient method to compute balanced Hamiltonian cycles
 651 \item Upper bound  (quadratic) on the number of iterations
 652 that is sufficient to obtain an uniform distribution of the output
 653 \item The first time a full automatic method to provide chaotic PRNGs is given
 654 \end{itemize}
 655 \end{frame}
 656 }
 657
 658
 659 \frameselect{true}{
 660   \begin{frame}
 661     \frametitle{Perspectives}
 662 \begin{itemize}
 663 \item Actuellement: si le cycle hamiltonien
 664 change le $l^{\textrm{ème}}$ bit entre les n{\oe}uds $X$ et $Y$, alors
 665 le $l^{\textrm{ème}}$ bit entre $Y$ et $Z$, ne peut pas être changé.
 666 \item Si le cycle hamiltonien est globalement équilibré:
 667 la probabilité de changer un bit $l'$, $ l' \neq l$, entre $Y$ et $Z$
 668 est $\frac{1}{\mathsf{N}-1}$ $\leadsto$ à intégrer.
 669 \item Actuellement: marcher dans une partie d'un $\mathsf{N}$-cube
 670 \item Futur: modifier plusieurs bits  en une seule itération (sauter dans cette partie du $\mathsf{N}$-cube)
 671 \end{itemize}
 672 \end{frame}
 673 }
 674
 675
 676 \end{document}
 677
 678 %%% Local Variables:
 679 %%% mode: latex
 680 %%% TeX-master: t
 681 %%% End: