Ajout exemple 3-cube pour algo Wild

[16dcc.git] / presPRNG.tex

diff --git a/presPRNG.tex b/presPRNG.tex
index bbb82e917956965c27cdd21121798d04bc616a12..fd0ce179a86378644551d7ecf6b7676c13fdd675 100644 (file)
--- a/presPRNG.tex
+++ b/presPRNG.tex
@@ -5,17 +5,19 @@
 \usenavigationsymbolstemplate{}
 
 \usepackage{thumbpdf}
 \usenavigationsymbolstemplate{}
 
 \usepackage{thumbpdf}

-\usepackage[T1]{fontenc}
-\usepackage[latin1]{inputenc}
+\usepackage[LY1]{fontenc}
+\usepackage[utf8]{inputenc}

 \usepackage{pifont}
 \usepackage{amsmath}
 \usepackage{wasysym}
 \usepackage{amsfonts}
 \usepackage{pifont}
 \usepackage{amsmath}
 \usepackage{wasysym}
 \usepackage{amsfonts}

+\usepackage{dsfont}

 \usepackage{tabularx}
 \usepackage{graphicx}
 \usepackage{ifthen}
 \usepackage[francais]{babel}
 \usepackage{rotating}
 \usepackage{tabularx}
 \usepackage{graphicx}
 \usepackage{ifthen}
 \usepackage[francais]{babel}
 \usepackage{rotating}

+\usepackage{algorithm2e}

 
 \graphicspath{{Figures/}}
 
 
 \graphicspath{{Figures/}}
 


@@ -24,6 +26,7 @@
 
 \newboolean{acroread}
 \setboolean{acroread}{true}
 
 \newboolean{acroread}
 \setboolean{acroread}{true}

+\newcommand{\Bool}[0]{\ensuremath{\mathds{B}}}

 \newcommand{\N}{\mathbb N}
 \newcommand{\R}{\mathbb R}
 \newcommand{\Z}{\mathbb Z}
 \newcommand{\N}{\mathbb N}
 \newcommand{\R}{\mathbb R}
 \newcommand{\Z}{\mathbb Z}


@@ -37,6 +40,7 @@
 \newcommand{\hauteur}[2]{\raisebox{0pt}[#1][-#1]{#2}}
 \def\oeuvre{\oe uvre }
 \def\oeuvrepv{\oe uvre}
 \newcommand{\hauteur}[2]{\raisebox{0pt}[#1][-#1]{#2}}
 \def\oeuvre{\oe uvre }
 \def\oeuvrepv{\oe uvre}

+\newcommand{\bleu}[1]{\color{blue}{#1}}

 
 %\newenvironment{myitemize}[1]{
 %%  \setlength{\topsep}{#1mm}
 
 %\newenvironment{myitemize}[1]{
 %%  \setlength{\topsep}{#1mm}


@@ -70,13 +74,13 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 % TITRE
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 % TITRE
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

-\author{Jean-François Couchot$^1$ et Sylvain Contassot-Vivier$^2$} 
+\author{Sylvain Contassot-Vivier$^1$ et Jean-François Couchot$^2$} 

 
 

-\title{Construction de codes de Gray équilibrés \\et forme canonique}
-%\subtitle{Habilitation à Diriger des Recherches}
+\title{Construction de codes de Gray équilibrés \\et forme canonique}
+%\subtitle{Habilitation à Diriger des Recherches}

 
 

-\date{1 - Équipe AND - FEMTO-ST - Univ. Bourgogne Franche-Comté\\
-  2 - Équipe Simbiot - LORIA - Université de Lorraine
+\date{1 - Équipe Simbiot - LORIA - Université de Lorraine\\
+2 - Équipe AND - FEMTO-ST - Univ. Bourgogne Franche-Comté

 }
 
 \begin{document}
 }
 
 \begin{document}


@@ -88,26 +92,150 @@
 }
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 }
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

-% Méthode R-C
+% Méthode R-C

 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

+
+\section{Introduction}
+
+\frameselect{true}{
+  \begin{frame}
+    \frametitle{Pseudo Random Number Generation}
+\vspace{-1.5em}
+\begin{itemize}
+\item Fields of Applications:
+\vspace{-0.5em}
+\begin{itemize}
+\item Security: hash function, steganography, cryptography
+\item Time Synchronization: GPS
+\item Numerical simulations: Monte-Carlo algorithms
+\end{itemize}
+\item Some requirements:
+\vspace{-0.5em}
+\begin{itemize}
+\item For cryptography: cryptographically secure
+\item Successful pass on PRNG batteries of tests:
+NIST\footnote{E.~Barker and A.~Roginsky.
+  Draft {N}{I}{S}{T} special publication 800-131 recommendation for the
+  transitioning of cryptographic algorithms and key sizes, 2010.}, 
+DieHARD\footnote{G.~Marsaglia.
+ DieHARD: a battery of tests of randomness.
+ {\em http://stat.fsu.edu/~geo/diehard.html}, 1996}
+\item Should have chaos properties
+\end{itemize} 
+\end{itemize}
+  \end{frame}
+}
+
+\frameselect{true}{
+  \begin{frame}
+    \frametitle{Our PRNG}
+\begin{block}{PRNG $\chi_{\textit{14Secrypt}}$}
+\begin{algorithm}[H]
+%\begin{scriptsize}
+\KwIn{a function $f$, an iteration number $b$, a \textit{Random} PRNG, an initial configuration $x^0$ ($n$ bits)}
+\KwOut{a configuration $x$ ($n$ bits)}
+$x\leftarrow x^0$\;
+\For{$i=0,\dots,b-1$}
+{
+$s\leftarrow{\textit{Random}(n)}$\;
+$x\leftarrow{F_f(s,x)}$\;
+}
+return $x$\;
+%\end{scriptsize}
+\end{algorithm}
+\end{block}
+  \end{frame}
+}
+
+\frameselect{true}{
+  \begin{frame}
+    \frametitle{Random Walk in a modified $\mathsf{N}$-cube}
+    
+\begin{block}{}
+\begin{itemize}
+\item ${\mathsf{N}}=3$, $f^*: \Bool^3 \rightarrow \Bool^3$ s.t.
+$$
+f^*(x_1,x_2,x_3) = 
+(x_2 \oplus x_3, \overline{x_1}\overline{x_3} + x_1\overline{x_2},
+\overline{x_1}\overline{x_3} + x_1x_2)$$
+\item Iteration graph $\Gamma(f^*)$ of this function:
+\includegraphics[width=0.45\textwidth]{images/iter_f0c}
+\end{itemize}
+\end{block}
+\end{frame}
+}
+
+
+\frameselect{true}{
+  \begin{frame}
+    \frametitle{Chaotic PRNG with verified statistical properties}
+
+\begin{exampleblock}{Previous work}
+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.
+ On the link between strongly connected iteration graphs and chaotic
+  Boolean discrete-time dynamical systems, {\em
+  Fundamentals of Computation Theory}, volume 6914 of {\em LNCS}, pages 126--137. Springer, 2011.}:
+\begin{itemize}
+\item with strongly connected iteration graph $\Gamma(f)$
+\item with doubly stochastic Markov probability matrix 
+\end{itemize}
+\end{exampleblock}
+\end{frame}
+}
+
+
+\frameselect{true}{
+  \begin{frame}
+    \frametitle{A solution to find ``good'' $\Gamma(f)$}
+
+\begin{theorem}{}
+Let $\Gamma$ be the $n$-cube in which an Hamiltonian  cycle is removed:
+$\Gamma$ is strongly connected and the
+resulting Markov matrix is doubly stochastic.
+\end{theorem}
+
+
+\begin{block}{We are then left to }
+  \begin{itemize}
+  \item  Focus on the generation of Hamiltonian cycles in the 
+    $n$-cube
+  \item Find cyclic Gray codes.
+  \end{itemize}
+\end{block}
+\footnote{Couchot, J., Héam, P., Guyeux, C., Wang, Q.,  Bahi, J. M. [2014] 
+ Pseudorandom number generators with balanced gray codes,
+ SECRYPT 2014 - Proceedings of the 11th International Conference on
+Security and Cryptography, Vienna, Austria, 28-30 August, 2014, pp. 469--475}
+
+\end{frame}
+}
+
+
+\frame{\frametitle{Outline}\tableofcontents[hideallsubsections]}
+
+
+
+\section{Codes de Gray équilibrés}
+\frame{\frametitle{Outline}\tableofcontents[currentsection,hideallsubsections]}
+

 \frameselect{true}{
   \begin{frame}[label=2]  
 \frameselect{true}{
   \begin{frame}[label=2]  

-    \frametitle{Méthode R-C de construction de CG}
+    \frametitle{Méthode R-C de construction de CG}

     
     

-    Méthode de Robinson-Cohn :
+    Méthode de Robinson-Cohn :

     \begin{itemize}
     \begin{itemize}

-    \item Méthode inductive
-    \item Produit un CG à N bits à partir d'un CG à N-2 bits
+    \item Méthode inductive
+    \item Produit un CG à N bits à partir d'un CG à N-2 bits

       \begin{itemize}
       \begin{itemize}

-      \item Séquence connue de transitions $S_{N-2} = (s_1,...,s_{2^{N-2}})$
-      \item Codées par la dimension empruntée lors de chaque déplacement du code\\
+      \item Séquence connue de transitions $S_{N-2} = (s_1,...,s_{2^{N-2}})$
+      \item Codées par la dimension empruntée lors de chaque déplacement du code\\

         $\Rightarrow$ $1\le s_i \le N-2$
       \end{itemize}
     \end{itemize}
 
         $\Rightarrow$ $1\le s_i \le N-2$
       \end{itemize}
     \end{itemize}
 

-    Définitions :
+    Définitions :

     \begin{itemize}
     \begin{itemize}

-    \item $u^R$ est le renversé de la séquence $u$
+    \item $u^R$ est le renversé de la séquence $u$

     \item $u'(u, x, y) = (u,x,u^R,y,u)$ 
     \end{itemize}
   \end{frame}
     \item $u'(u, x, y) = (u,x,u^R,y,u)$ 
     \end{itemize}
   \end{frame}


@@ -115,24 +243,24 @@
 
 \frameselect{true}{
   \begin{frame}
 
 \frameselect{true}{
   \begin{frame}

-    \frametitle{Méthode R-C de construction de CG}
+    \frametitle{Méthode R-C de construction de CG}

     Algorithme :
     \begin{enumerate}
     Algorithme :
     \begin{enumerate}

-    \item Pour $l$ un entier pair, décomposer $S_{N-2}$ en une séquence :\\
+    \item Pour $l$ un entier pair, décomposer $S_{N-2}$ en une séquence :\\

       \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})$}
       \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})$}

-      où les $u_i$ sont des ss-séqs éventuellement vides de $S_{N-2}$\\
-      et $u_0 = \emptyset$, $i_1 = 1$, $i_2 = 2$ et $v$ éventuellement $\emptyset$.
-    \item Obtenir une nouvelle séquence $U$ en remplaçant :
+      où les $u_i$ sont des ss-séqs éventuellement vides de $S_{N-2}$\\
+      et $u_0 = \emptyset$, $i_1 = 1$, $i_2 = 2$ et $v$ éventuellement $\emptyset$.
+    \item Obtenir une nouvelle séquence $U$ en remplaçant :

       \begin{itemize}
       \item $u_0$ par $N-1$
       \item $u_{2i+1}$ par $u'(u_{2i+1},N-1,N)$
       \item $u_{2i}$ par $u'(u_{2i},N,N-1)$
       \end{itemize}
       \begin{itemize}
       \item $u_0$ par $N-1$
       \item $u_{2i+1}$ par $u'(u_{2i+1},N-1,N)$
       \item $u_{2i}$ par $u'(u_{2i},N,N-1)$
       \end{itemize}

-    \item Construire les séquences :\\
+    \item Construire les séquences :\\

       \begin{itemize}
       \item $V=(v^R,N,v)$
       \item $W=(N-1,S_{N-2},N)$
       \begin{itemize}
       \item $V=(v^R,N,v)$
       \item $W=(N-1,S_{N-2},N)$

-      \item $W'=(w_2,w_1,W_{[3:]})$ \hfill(inversion des 2 1ers élts de $W$)
+      \item $W'=(w_2,w_1,W_{[3:]})$ \hfill(inversion des 2 1ers élts de $W$)

       \end{itemize}
     \item $S_{N} = (U^R, V, W')$
     \end{enumerate}
       \end{itemize}
     \item $S_{N} = (U^R, V, W')$
     \end{enumerate}


@@ -141,13 +269,13 @@
 
 \frameselect{true}{
   \begin{frame}
 
 \frameselect{true}{
   \begin{frame}

-    \frametitle{Méthode R-C de construction de CG}
+    \frametitle{Méthode R-C de construction de CG}

     \textbf{Exemple 1} : $N = 5$ et $S_3 = (1,2,1,3,1,2,1,3)$
     \begin{enumerate}
     \item le choix $l=2$ implique : $S_3=(s_{1}, \underline{u_0}, s_{2},v)$\\
       avec $v = (s_3,...,s_{2^{N-2}}) = (1,3,1,2,1,3)$
     \item on obtient $U = (s_1, 4, s_2, s_3,...,s_{2^{N-2}}) = (1,4,2,1,3,1,2,1,3)$
     \textbf{Exemple 1} : $N = 5$ et $S_3 = (1,2,1,3,1,2,1,3)$
     \begin{enumerate}
     \item le choix $l=2$ implique : $S_3=(s_{1}, \underline{u_0}, s_{2},v)$\\
       avec $v = (s_3,...,s_{2^{N-2}}) = (1,3,1,2,1,3)$
     \item on obtient $U = (s_1, 4, s_2, s_3,...,s_{2^{N-2}}) = (1,4,2,1,3,1,2,1,3)$

-    \item et les séquences :\\
+    \item et les séquences :\\

       \begin{itemize}
       \item $V= (v^R,N,v) = (3,1,2,1,3,1,5,1,3,1,2,1,3)$
       \item $W=(N-1,S_{N-2},N)=(4,1,2,1,3,1,2,1,3,5)$
       \begin{itemize}
       \item $V= (v^R,N,v) = (3,1,2,1,3,1,5,1,3,1,2,1,3)$
       \item $W=(N-1,S_{N-2},N)=(4,1,2,1,3,1,2,1,3,5)$


@@ -158,13 +286,13 @@
       \hspace{9em} $1,4,2,1,3,1,2,1,3,5)$
     \end{enumerate}
 
       \hspace{9em} $1,4,2,1,3,1,2,1,3,5)$
     \end{enumerate}
 

-    Fréquences = 14, 6, 8, 2, 2
+    Fréquences = 14, 6, 8, 2, 2

   \end{frame}
 }
 
 \frameselect{true}{
   \begin{frame}
   \end{frame}
 }
 
 \frameselect{true}{
   \begin{frame}

-    \frametitle{Méthode R-C de construction de CG}
+    \frametitle{Méthode R-C de construction de CG}

     \textbf{Exemple 2} : $N = 5$ et $S_3 = (1,2,1,3,1,2,1,3)$
     \begin{enumerate}
     \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)$\\
     \textbf{Exemple 2} : $N = 5$ et $S_3 = (1,2,1,3,1,2,1,3)$
     \begin{enumerate}
     \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)$\\


@@ -173,93 +301,93 @@
     \item on a $u'(u_1,4,5) = (1,3,4,3,1,5,1,3)$\\
       et $u'(u_2,5,4) = (2,5,2,4,2)$\\
       et donc $U = (1,4,2,\underline{1,3,4,3,1,5,1,3},1,\underline{2,5,2,4,2},1,3)$
     \item on a $u'(u_1,4,5) = (1,3,4,3,1,5,1,3)$\\
       et $u'(u_2,5,4) = (2,5,2,4,2)$\\
       et donc $U = (1,4,2,\underline{1,3,4,3,1,5,1,3},1,\underline{2,5,2,4,2},1,3)$

-    \item et les séquences :\\
+    \item et les séquences :\\

       \begin{itemize}
       \item $V= (v^R,N,v) = (3,5,3)$
       \begin{itemize}
       \item $V= (v^R,N,v) = (3,5,3)$

-      \item $W$ et $W'$ comme précédemment
+      \item $W$ et $W'$ comme précédemment

       \end{itemize}
     \item $S_{N} = (U^R, V, W')=(\underline{3,1,2,4,2,5,2,1,3,1,5,1,3,4,3,}$\\
       \hspace{9em} $\underline{1,2,4,1},3,5,3,$\\
       \hspace{9em} $1,4,2,1,3,1,2,1,3,5)$
     \end{enumerate}
 
       \end{itemize}
     \item $S_{N} = (U^R, V, W')=(\underline{3,1,2,4,2,5,2,1,3,1,5,1,3,4,3,}$\\
       \hspace{9em} $\underline{1,2,4,1},3,5,3,$\\
       \hspace{9em} $1,4,2,1,3,1,2,1,3,5)$
     \end{enumerate}
 

-    Fréquences = 10, 6, 8, 4, 4
+    Fréquences = 10, 6, 8, 4, 4

   \end{frame}
 }
 
 \frameselect{true}{
   \begin{frame}
   \end{frame}
 }
 
 \frameselect{true}{
   \begin{frame}

-    \frametitle{Problématique des CG équilibrés}
+    \frametitle{Problématique des CG équilibrés}

     
     

-    L'algo précédent n'est pas \textbf{constructif}\\
+    L'algo précédent n'est pas \textbf{constructif}\\

     $\rightarrow$ pas d'indication sur le choix de $l$ et des $u_i$ !
     \vspace{1em}
 
     $\rightarrow$ pas d'indication sur le choix de $l$ et des $u_i$ !
     \vspace{1em}
 

-    Formalisation de l'équilibre d'un CG :
+    Formalisation de l'équilibre d'un CG :

     \begin{itemize}
     \item Soit $TC_N : \{1,\dots, N\} \rightarrow \{0, \ldots, 2^N\}$\\
     \begin{itemize}
     \item Soit $TC_N : \{1,\dots, N\} \rightarrow \{0, \ldots, 2^N\}$\\

-      nb d'occurrences d'une dimension dans une séquence
-    \item un CG est \textbf{équilibré} ssi :\\
+      nb d'occurrences d'une dimension dans une séquence
+    \item un CG est \textbf{équilibré} ssi :\\

       \centerline{$\forall i,j\in \{1,...,N\},~|TC_N(i) - TC_N(j)|\le 2$}
       \centerline{$\forall i,j\in \{1,...,N\},~|TC_N(i) - TC_N(j)|\le 2$}

-    \item il est \textbf{totalement équilibré} ssi:\\
+    \item il est \textbf{totalement équilibré} ssi:\\

       \centerline{$\forall i\in \{1,...,N\},~TC_N(i) = \frac{2^N}{N}$}
     \end{itemize}
     \vspace{1em}
 
       \centerline{$\forall i\in \{1,...,N\},~TC_N(i) = \frac{2^N}{N}$}
     \end{itemize}
     \vspace{1em}
 

-    On a  montré qu'il existe au  moins un choix  de $(u_i)$ dans l'algo  RC qui
-    donne un CG équilibré.
+    On a  montré qu'il existe au  moins un choix  de $(u_i)$ dans l'algo  RC qui
+    donne un CG équilibré.

   \end{frame}
 }
 
 \frameselect{true}{
   \begin{frame}
   \end{frame}
 }
 
 \frameselect{true}{
   \begin{frame}

-    \frametitle{Construction de CG équilibrés}
+    \frametitle{Construction de CG équilibrés}

     
     

-    L'idée est de : 
+    L'idée est de : 

     \begin{itemize}
     \begin{itemize}

-    \item Compter pour chaque dimension, les occurrences générées par l'algo RC :
+    \item Compter pour chaque dimension, les occurrences générées par l'algo RC :

       \begin{itemize}
       \begin{itemize}

-      \item Pour les dimensions $N-1$ et $N$ on arrive à $l$
-      \item Pour les autres, on établit une formulation dépendant :
+      \item Pour les dimensions $N-1$ et $N$ on arrive à $l$
+      \item Pour les autres, on établit une formulation dépendant :

         \begin{itemize}
         \begin{itemize}

-        \item des occurrences dans la séquence initiale $S_{N-2}$
+        \item des occurrences dans la séquence initiale $S_{N-2}$

         \item des choix d'inclusion ou non dans les $s_{i_j}$, $u_i$ et $v$ :
           $TC_N(k)=TC(k, \cup_j(s_{i_j})) + 3\times ( TC(k, \cup_iu_i) + TC(k, v)) + TC_{N-2}(k)$\\
         \end{itemize}
       \end{itemize}
         \item des choix d'inclusion ou non dans les $s_{i_j}$, $u_i$ et $v$ :
           $TC_N(k)=TC(k, \cup_j(s_{i_j})) + 3\times ( TC(k, \cup_iu_i) + TC(k, v)) + TC_{N-2}(k)$\\
         \end{itemize}
       \end{itemize}

-    \item Appliquer la contrainte d'équilibre aux formulations obtenues
+    \item Appliquer la contrainte d'équilibre aux formulations obtenues

     \end{itemize}
 
     \begin{center}
     \end{itemize}
 
     \begin{center}

-      $\Rightarrow$ On en déduit le nombre d'occurrences de chaque dimension à
-      insérer dans les $s_{i_j}$, $u_i$ et $v$
+      $\Rightarrow$ On en déduit le nombre d'occurrences de chaque dimension à
+      insérer dans les $s_{i_j}$, $u_i$ et $v$

     \end{center}
   \end{frame}
 }
 
 \frameselect{true}{
   \begin{frame}
     \end{center}
   \end{frame}
 }
 
 \frameselect{true}{
   \begin{frame}

-    \frametitle{Construction de CG équilibrés}
+    \frametitle{Construction de CG équilibrés}

     
     Exemple : $S_2 = (1,2,1,2)$
     \begin{itemize}
     
     Exemple : $S_2 = (1,2,1,2)$
     \begin{itemize}

-    \item Pour avoir l'équilibre final, $l$ doit valoir 4
-    \item On en déduit une décomposition de la forme :\\
+    \item Pour avoir l'équilibre final, $l$ doit valoir 4
+    \item On en déduit une décomposition de la forme :\\

       $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$
     \item Or, on a : $TC_2(1) = 2$ et $TC_2(2)=2$
       $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$
     \item Or, on a : $TC_2(1) = 2$ et $TC_2(2)=2$

-    \item Et pour $k=1$ et $k=2$, il faut vérifier :
+    \item Et pour $k=1$ et $k=2$, il faut vérifier :

       $TC(k, \cup_j(s_{i_j})) + 3\times ( TC(k, \cup_iu_i) + TC(k, v)) + TC_2(k)=4$\\
       $TC(k, \cup_j(s_{i_j})) + 3\times ( TC(k, \cup_iu_i) + TC(k, v))=2$\\
       $\Rightarrow TC(k, \cup_iu_i) + TC(k, v) = 0$\\
       $\Rightarrow TC(k, \cup_j(s_{i_j}))=2$
       $TC(k, \cup_j(s_{i_j})) + 3\times ( TC(k, \cup_iu_i) + TC(k, v)) + TC_2(k)=4$\\
       $TC(k, \cup_j(s_{i_j})) + 3\times ( TC(k, \cup_iu_i) + TC(k, v))=2$\\
       $\Rightarrow TC(k, \cup_iu_i) + TC(k, v) = 0$\\
       $\Rightarrow TC(k, \cup_j(s_{i_j}))=2$

-    \item Donc $u_0,u_1,u_2$ et $v$ doivent être vides !
+    \item Donc $u_0,u_1,u_2$ et $v$ doivent être vides !

     \end{itemize}
   \end{frame}
 }
 
 \frameselect{true}{
   \begin{frame}
     \end{itemize}
   \end{frame}
 }
 
 \frameselect{true}{
   \begin{frame}

-    \frametitle{Construction de CG équilibrés}
+    \frametitle{Construction de CG équilibrés}

     
     Comme $u_0,u_1,u_2$ et $v$ sont vides, on a :
     \begin{itemize}
     
     Comme $u_0,u_1,u_2$ et $v$ sont vides, on a :
     \begin{itemize}


@@ -272,75 +400,110 @@
     \item $S_{4} = (U^R, V, W')=(2,3,4,1,4,3,2,3,1,4,1,3,2,1,2,4)$
     \end{itemize}
     \begin{center}
     \item $S_{4} = (U^R, V, W')=(2,3,4,1,4,3,2,3,1,4,1,3,2,1,2,4)$
     \end{itemize}
     \begin{center}

-      $\Rightarrow$ Fréquences = 4, 4, 4, 4
+      $\Rightarrow$ Fréquences = 4, 4, 4, 4

     \end{center}
   \end{frame}
 }
 
 \frameselect{true}{
   \begin{frame}
     \end{center}
   \end{frame}
 }
 
 \frameselect{true}{
   \begin{frame}

-    \frametitle{Algo de construction de CG équilibrés}
+    \frametitle{Algo de construction de CG équilibrés}

     
     

-    Une fois  déterminés les nombres d'occurrences  à placer dans les  $u_i$, il
-    faut construire la séquence :
+    Une fois  déterminés les nombres d'occurrences  à placer dans les  $u_i$, il
+    faut construire la séquence :

     \begin{itemize}
     \item Parcours exhaustif :
       \begin{itemize}
     \begin{itemize}
     \item Parcours exhaustif :
       \begin{itemize}

-      \item [$\frownie$] Coûteux
-      \item [$\smiley$] Produit tous les CG équilibrés atteignables par cette méthode
+      \item [$\frownie$] Coûteux
+      \item [$\smiley$] Produit tous les CG équilibrés atteignables par cette méthode

       \end{itemize}
     \item Algorithme glouton :
       \begin{itemize}
       \item Construction des $u_i$ dans l'ordre
       \item  Choix  glouton  pour  chaque  $u_i$ :\\
       \end{itemize}
     \item Algorithme glouton :
       \begin{itemize}
       \item Construction des $u_i$ dans l'ordre
       \item  Choix  glouton  pour  chaque  $u_i$ :\\

-        sous-séquence  maximale  de  $S_{N-2}$   vérifiant  les  nombres  totaux
-        d'occurrences déterminés pour les $u_i$
+        sous-séquence  maximale  de  $S_{N-2}$   vérifiant  les  nombres  totaux
+        d'occurrences déterminés pour les $u_i$

       \end{itemize}
     \item [$\frownie$] Ne produit pas tous les CGE possibles !
     \item [$\smiley$] Produit rapidement un CG pour n'importe quelle dimension !\\
       \end{itemize}
     \item [$\frownie$] Ne produit pas tous les CGE possibles !
     \item [$\smiley$] Produit rapidement un CG pour n'importe quelle dimension !\\

-      (à partir des dimensions 2 et 3)
+      (à partir des dimensions 2 et 3)

     \end{itemize}
   \end{frame}
 }
 
 \frameselect{true}{
   \begin{frame}
     \end{itemize}
   \end{frame}
 }
 
 \frameselect{true}{
   \begin{frame}

-    \frametitle{Algo de construction de tous les CG équilibrés}
+    \frametitle{Algo de construction de tous les CG équilibrés}

     
     

-    Algo basé sur la méthode de M.~Wild : 
+    Algo basé sur la méthode de M.~Wild : 

     \begin{itemize}
     \begin{itemize}

-    \item Basé sur le principe d'exclusion
-    \item Liste des arêtes du N-cube 
-    \item Chaque arête prend un état dans l'ensemble $\{0,1,2,g,d\}$ :
+    \item Basé sur le principe d'exclusion
+    \item Liste des arêtes du N-cube 
+    \item Chaque arête prend un état dans l'ensemble $\{0,1,2,g,d\}$ :

       \begin{itemize}
       \begin{itemize}

-      \item 0 pour supprimée, 1 pour incluse, 2 pour indéterminé (initial)
-      \item $g$ pour un ensemble d'arêtes dont une seule est incluse
-      \item $d$ pour un ensemble d'arêtes dont deux sont incluses
+      \item 0 pour supprimée, 1 pour incluse, 2 pour indéterminé (initial)
+      \item $g$ pour un ensemble d'arêtes dont une seule est incluse
+      \item $d$ pour un ensemble d'arêtes dont deux sont incluses

       \end{itemize}
     \item Ajouts successifs des noeuds en appliquant :
       \begin{itemize}
       \end{itemize}
     \item Ajouts successifs des noeuds en appliquant :
       \begin{itemize}

-      \item Condition locale (chaque noeud) : degré 2
+      \item Condition locale (chaque noeud) : degré 2

       \item Conditions globales : \\
       \item Conditions globales : \\

-        cycle max : nb arêtes à 1 = nb sommets\\
+        cycle max : nb arêtes à 1 = nb sommets\\

         cycles inf : pas de cycles < nb sommets
         cycles inf : pas de cycles < nb sommets

-      \item [$\Rightarrow$] élagage dès qu'une contrainte n'est pas vérifiée 
+      \item [$\Rightarrow$] élagage dès qu'une contrainte n'est pas vérifiée 

       \end{itemize}
     \end{itemize}
   \end{frame}
 }
 
       \end{itemize}
     \end{itemize}
   \end{frame}
 }
 

+\frameselect{true}{
+  \begin{frame}
+    \frametitle{Exemple sur le 3-cube}
+    
+    \begin{center}
+      \vspace{-.75em}
+      \includegraphics[width=.3\textwidth]{3-cube.pdf}
+      \vspace{-.75em}
+    \end{center}
+
+    \begin{block}{}
+      \small
+      \vspace{-1.5em}
+      \begin{center}
+        \begin{equation*}
+          \begin{array}[h]{c|cccccccccccc}
+            \text{arêtes}  & 1         & 2         & 3   & 4   & 5   & 6 & 7   & 8 & 9 & 10 & 11  & 12 \\
+            \hline
+            \text{init}    & 2         & 2         & 2   & 2   & 2   & 2 & 2   & 2 & 2 & 2  & 2   & 2  \\
+            \hline
+            \text{ajout a} & d_1       & d_1       & 2   & 2   & d_1  & 2 & 2   & 2 & 2 & 2  & 2   & 2  \\
+            \hline
+            \text{ajout b} & \alert{1} & \bleu{g_1} & 2   & \bleu{g_2} & \bleu{g_1}  & 2 & 2   & 2 & 2 & 2  & \bleu{g_2} & 2  \\
+                           & \alert{0} & \bleu{1}         & 2   & \bleu{1}   & \bleu{1}   & 2 & 2   & 2 & 2 & 2  & \bleu{1}   & 2  \\
+            \hline
+            \text{ajout c} & 1         & \alert{1} & \bleu{g_3} & g_2 & \bleu{0}   & 2 & \bleu{g_3} & 2 & 2 & 2  & g_2 & 2  \\
+                           & 1         & \alert{0} & \bleu{1}   & g_2 & \bleu{1}   & 2 & \bleu{1}   & 2 & 2 & 2  & g_2 & 2  \\
+                           & 0         & 1         & \bleu{g_3} & 1   & 1   & 2 & \bleu{g_3} & 2 & 2 & 2  & 1   & 2  \\
+          \end{array}
+        \end{equation*}
+      \end{center}
+    \end{block}
+  \end{frame}
+}
+

 \frameselect{true}{
   \begin{frame}
     \frametitle{Adaptation au contexte de N-cube}
     
     \begin{itemize}
 \frameselect{true}{
   \begin{frame}
     \frametitle{Adaptation au contexte de N-cube}
     
     \begin{itemize}

-    \item Ajout de la contrainte d'équilibre dans l'élagage
+    \item Ajout de la contrainte d'équilibre dans l'élagage

     \item Utilisation d'une forme canonique des CG :\\
       \begin{itemize}
     \item Utilisation d'une forme canonique des CG :\\
       \begin{itemize}

-      \item [$\Rightarrow$] Unicité des représentants
-      \item [$\Rightarrow$] Ordre global sur les représentants :
+      \item [$\Rightarrow$] Unicité des représentants
+      \item [$\Rightarrow$] Ordre global sur les représentants :

         \begin{itemize}
         \begin{itemize}

-        \item Détection efficace des doublons
+        \item Détection efficace des doublons

         \item Stockage minimal
         \end{itemize}
       \end{itemize}
         \item Stockage minimal
         \end{itemize}
       \end{itemize}


@@ -353,27 +516,166 @@
     \frametitle{Forme canonique des CG}
     
     \begin{itemize}
     \frametitle{Forme canonique des CG}
     
     \begin{itemize}

-    \item Alignement sur début d'une sous-séquence avec \textbf{écart max} :
+    \item Alignement sur début d'une sous-séquence avec \textbf{écart max} :

       \begin{itemize}
       \begin{itemize}

-      \item Plus grand intervalle entre 2 occurrences d'une même dimension
+      \item Plus grand intervalle entre 2 occurrences d'une même dimension

       \end{itemize}
       \end{itemize}

-    \item Écart max sur l'ensemble des dimensions = \textbf{équilibre local}
-    \item Renumérotation des dimensions :
+    \item Écart max sur l'ensemble des dimensions = \textbf{équilibre local}
+    \item Renumérotation des dimensions :

       \begin{itemize}
       \begin{itemize}

-      \item Affectation dans l'ordre croissant des n° \hfill$\Rightarrow$ débuts = (1,2)
-      \item Équivalent à des isomorphismes du N-cube
+      \item Affectation dans l'ordre croissant des no \hfill$\Rightarrow$ débuts = (1,2)
+      \item Équivalent à des isomorphismes du N-cube

       \item Donne un ordre global \hfill$\Rightarrow$ tri possible
       \end{itemize}
     \item Travaux en cours :
       \begin{itemize}
       \item Donne un ordre global \hfill$\Rightarrow$ tri possible
       \end{itemize}
     \item Travaux en cours :
       \begin{itemize}

-      \item Unicité de la forme canonique pour une classe d'isomorphismes
+      \item Unicité de la forme canonique pour une classe d'isomorphismes

       \item Deux formes canoniques distinctes ne sont pas isomorphes
       \end{itemize}
     \end{itemize}
     \begin{center}
       \item Deux formes canoniques distinctes ne sont pas isomorphes
       \end{itemize}
     \end{itemize}
     \begin{center}

-      $\Rightarrow$ Génération exhaustive en accord avec la théorie (dims $\le$ 5)
+      $\Rightarrow$ Génération exhaustive en accord avec la théorie (dims $\le$ 5)

     \end{center}
   \end{frame}
 }
 
     \end{center}
   \end{frame}
 }
 

+
+\section{Temps de mélange pour une distribution uniforme}
+\frame{\frametitle{Outline}\tableofcontents[currentsection,hideallsubsections]}
+
+
+\frameselect{true}{
+  \begin{frame}
+    \frametitle{Mixing time upper bound}
+    \begin{itemize}
+    \item Evaluated in a (lazy) context
+    \item $t_{\rm mix}(\varepsilon)$: the steps required to be sure to be $\varepsilon$-close
+      to the stationary uniform distribution
+    \item Theoretical result: $t_{\rm mix}\leq 32N^2+16N\ln (N+1)=O(N^2)$
+    \item In practice: in $N\ln(N)$
+    \end{itemize}
+  \end{frame}
+}
+
+
+\section{Experiments}
+\frame{\frametitle{Outline}\tableofcontents[currentsection,hideallsubsections]}
+
+
+
+\frameselect{true}{
+  \begin{frame}
+    \frametitle{Functions with DSCC Matrix and smallest MT}
+    \begin{center}
+\begin{scriptsize}
+  \begin{tabular}{|c|c|c|c|}
+    \hline
+Function $f$ & $f(x)$, for $x$ in $(0,1,2,\hdots,2^n-1)$ & $\mathsf{N}$ & $b$ 
+\\ 
+\hline
+%%%%% n= 4
+$\textcircled{a}$&[13,10,9,14,3,11,1,12,15,4,7,5,2,6,0,8]&4&64\\
+\hline
+%%%%% n= 5
+$\textcircled{b}$& 
+[29, 22, 25, 30, 19, 27, 24, 16, 21, 6, 5, 28, 23, 26, 1, 17, & 5 & 78 \\
+&
+ 31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 7, 20, 11, 18, 0, 4]
+&&\\
+%%%%% n= 6
+\hline
+&
+[55, 60, 45, 44, 58, 62, 61, 48, 53, 50, 52, 36, 59, 34, 33, 49,
+&&\\
+&
+ 15, 42, 47, 46, 35, 10, 57, 56, 7, 54, 39, 37, 51, 2, 1, 40, 63,
+&&\\
+$\textcircled{c}$&
+ 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, 16, 24, 13, 
+&6&88\\
+&
+12, 29, 8, 43, 14, 41, 0, 5, 38, 4, 6, 11, 3, 9, 32]
+&&\\
+%%%%% n= 7
+\hline
+&
+[111, 124, 93, 120, 122, 114, 89, 121, 87, 126, 125, 84, 123, 82, 
+&&\\
+&112, 80, 79, 106, 105, 110, 75, 107, 73, 108, 119, 100, 117, 116, 
+&&\\
+&103, 102, 101, 97, 31, 86, 95, 94, 83, 26, 88, 24, 71, 118, 69, 
+&&\\
+&68, 115, 90, 113, 16, 15, 76, 109, 72, 74, 10, 9, 104, 7, 6, 65, 
+&&\\
+$\textcircled{d}$ &70, 99, 98, 64, 96, 127, 54, 53, 62, 51, 59, 56, 60, 39, 52, 37, &7 &99\\
+&36, 55, 58, 57, 49, 63, 44, 47, 40, 42, 46, 45, 41, 35, 34, 33, 
+&&\\
+&38, 43, 50, 32, 48, 29, 28, 61, 92, 91, 18, 17, 25, 19, 30, 85, 
+&&\\
+&22, 27, 2, 81, 0, 13, 78, 77, 14, 3, 11, 8, 12, 23, 4, 21, 20, 
+&&\\
+&67, 66, 5, 1]
+&&\\
+
+
+%%%%%n=8
+\hline
+$\textcircled{e}$& \ldots &8&109\\
+ \hline
+\end{tabular}
+\end{scriptsize}
+\end{center}
+\end{frame}
+}
+
+\frameselect{true}{
+  \begin{frame}
+    \frametitle{Nist Test Results}
+\begin{itemize}
+\item Embedded PRNG \textit{Random}: Mersenne Twister algorithm~\footnote{Mersenne twister: a 623-dimensionally 
+    equidistributed uniform pseudo-random number generator, (TOMACS) 8 , 3--30}
+\item Adding chaos properties for Mersenne Twister algorithm:  security  is not reduced w.r.t. NIST
+\end{itemize}
+\end{frame}
+}
+
+\section{Conclusion}
+
+\frameselect{true}{
+  \begin{frame}
+    \frametitle{Summary}
+\begin{itemize}
+\item Chaos properties can be added to PRNGs
+\item Iterated map: built by removing from a $\mathsf{N}$-cube a balanced  Hamiltonian cycle
+\item Efficient method to compute balanced Hamiltonian cycles
+\item Upper bound  (quadratic) on the number of iterations 
+that is sufficient to obtain an uniform distribution of the output
+\item The first time a full automatic method to provide chaotic PRNGs is given
+\end{itemize}
+\end{frame}
+}
+
+
+\frameselect{true}{
+  \begin{frame}
+    \frametitle{Perspectives}
+\begin{itemize}
+\item Actuellement: si le cycle hamiltonien 
+change le $l^{\textrm{ème}}$ bit entre les n{\oe}uds $X$ et $Y$, alors 
+le $l^{\textrm{ème}}$ bit entre $Y$ et $Z$, ne peut pas être changé.
+\item Si le cycle hamiltonien est globalement équilibré:
+la probabilité de changer un bit $l'$, $ l' \neq l$, entre $Y$ et $Z$
+est $\frac{1}{\mathsf{N}-1}$ $\leadsto$ à intégrer.
+\item Actuellement: marcher dans une partie d'un $\mathsf{N}$-cube 
+\item Futur: modifier plusieurs bits  en une seule itération (sauter dans cette partie du $\mathsf{N}$-cube) 
+\end{itemize}
+\end{frame}
+}
+
+

 \end{document}
 \end{document}

+
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: t
+%%% End: