\documentclass[compress]{beamer}

\usetheme[compress]{Ilmenau}
\setbeamertemplate{items}[ball]
\usenavigationsymbolstemplate{}

\usepackage{thumbpdf}
\usepackage[LY1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{pifont}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{dsfont}
\usepackage{tabularx}
\usepackage{graphicx}
\usepackage{ifthen}
\usepackage[francais]{babel}
\usepackage{rotating}
\usepackage{algorithm2e}
\usepackage{stmaryrd}

\graphicspath{{Figures/}}

%\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}
%\includeonlyframes{6}

\newboolean{acroread}
\setboolean{acroread}{true}
\newcommand{\Bool}[0]{\ensuremath{\mathds{B}}}
\newcommand{\N}{\mathbb N}
\newcommand{\R}{\mathbb R}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Q}{\mathbb Q}
\newcommand{\C}{\mathbb C}
\newlength{\tl}
\newcommand{\attention}{%
  \settowidth{\tl}{$\triangle$}%
  \makebox[0pt][l]{$\triangle$}%
  \makebox[\tl][c]{\raisebox{.2ex}{\tiny\string!}}}
\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}
%  \begin{itemize}
%%    \setlength{\partopsep}{#1mm}
%    \setlength{\itemsep}{#1}
%  }
%  {\end{itemize}
%}

%\newcounter{selection}
%\setcounter{selection}{0}
%\newcounter{num}
%\setcounter{num}{0}

\newcommand{\frameselect}[2]{
  % \addtocounter{num}{1}
  \ifthenelse{\boolean{#1}}%\value{selection}=0 \or
    % \value{num}=\value{selection}}
  {
    #2
  }{}
}

\newenvironment{algo}[0] {
  \begin{quotation}
  \begin{tabbing}
  \hspace{5mm}\=\hspace{5mm}\=\hspace{5mm}\=\hspace{5mm}\= \kill} %
 { \end{tabbing}\end{quotation}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TITRE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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}

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

\begin{document}

\frameselect{true}{
  \begin{frame}[label=1]
    \titlepage
  \end{frame}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 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}
$$
F_f:  \Bool^{{\mathsf{N}}} \times \llbracket1;{\mathsf{N}} \rrbracket \to \Bool^{\mathsf{N}}, 
F_f(x,i)=(x_1,\dots,x_{i-1},f_i(x),x_{i+1},\dots,x_{\mathsf{N}}).
$$
  \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]  
    \frametitle{Méthode R-C de construction de CG}
    
    Méthode de Robinson-Cohn :
    \begin{itemize}
    \item Méthode inductive
    \item Produit un CG à N bits à partir d'un CG à N-2 bits
      \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\\
        $\Rightarrow$ $1\le s_i \le N-2$
      \end{itemize}
    \end{itemize}

    Définitions :
    \begin{itemize}
    \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}
}

\frameselect{true}{
  \begin{frame}
    \frametitle{Méthode R-C de construction de CG}
    Algorithme :
    \begin{enumerate}
    \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})$}
      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}
    \item Construire les séquences :\\
      \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$)
      \end{itemize}
    \item $S_{N} = (U^R, V, W')$
    \end{enumerate}
  \end{frame}
}

\frameselect{true}{
  \begin{frame}
    \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)$
    \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)$
      \item $W'=(w_2,w_1,W_{[3:]})=(1,4,2,1,3,1,2,1,3,5)$
      \end{itemize}
    \item $S_{N} = (U^R, V, W')=(\underline{3,1,2,1,3,1,2,4,1},$\\
      \hspace{9em} $3,1,2,1,3,1,5,1,3,1,2,1,3,$\\
      \hspace{9em} $1,4,2,1,3,1,2,1,3,5)$
    \end{enumerate}

    Fréquences = 14, 6, 8, 2, 2
  \end{frame}
}

\frameselect{true}{
  \begin{frame}
    \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)$\\
      on choisit $u_1=(1,3)$, donc $s_{i_3}=1$\\
      et $u_2=(2)$, donc $s_{i_4}=1$ et $v =(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 :\\
      \begin{itemize}
      \item $V= (v^R,N,v) = (3,5,3)$
      \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}

    Fréquences = 10, 6, 8, 4, 4
  \end{frame}
}

\frameselect{true}{
  \begin{frame}
    \frametitle{Problématique des CG équilibrés}
    
    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}

    Formalisation de l'équilibre d'un CG :
    \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 :\\
      \centerline{$\forall i,j\in \{1,...,N\},~|TC_N(i) - TC_N(j)|\le 2$}
    \item il est \textbf{totalement équilibré} ssi:\\
      \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é.
  \end{frame}
}

\frameselect{true}{
  \begin{frame}
    \frametitle{Construction de CG équilibrés}
    
    L'idée est de : 
    \begin{itemize}
    \item Compter pour chaque dimension, les occurrences générées par l'algo RC :
      \begin{itemize}
      \item Pour les dimensions $N-1$ et $N$ on arrive à $l$
      \item Pour les autres, on établit une formulation dépendant :
        \begin{itemize}
        \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 Appliquer la contrainte d'équilibre aux formulations obtenues
    \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$
    \end{center}
  \end{frame}
}

\frameselect{true}{
  \begin{frame}
    \frametitle{Construction de CG équilibrés}
    
    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 :\\
      $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 :
      $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 !
    \end{itemize}
  \end{frame}
}

\frameselect{true}{
  \begin{frame}
    \frametitle{Construction de CG équilibrés}
    
    Comme $u_0,u_1,u_2$ et $v$ sont vides, on a :
    \begin{itemize}
    \item $u'(u_1,3,4) = (3,4)$
    \item $u'(u_2,4,3) = (4,3)$
    \item $U = (1,3,2,3,4,1,4,3,2)$
    \item $V= (v^R,N,v) = (4)$
    \item $W=(N-1,S_{N-2},N)=(3,1,2,1,2,4)$
    \item $W'=(w_2,w_1,W_{[3:]})=(1,3,2,1,2,4)$
    \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
    \end{center}
  \end{frame}
}

\frameselect{true}{
  \begin{frame}
    \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 :
    \begin{itemize}
    \item Parcours exhaustif :
      \begin{itemize}
      \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$ :\\
        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 !\\
      (à partir des dimensions 2 et 3)
    \end{itemize}
  \end{frame}
}

\frameselect{true}{
  \begin{frame}
    \frametitle{Algo de construction de tous les CG équilibrés}
    
    Algo basé sur la méthode de M.~Wild : 
    \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\}$ :
      \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
      \end{itemize}
    \item Ajouts successifs des noeuds en appliquant :
      \begin{itemize}
      \item Condition locale (chaque noeud) : degré 2
      \item Conditions globales : \\
        cycle max : nb arêtes à 1 = nb sommets\\
        cycles inf : pas de cycles < nb sommets
      \item [$\Rightarrow$] élagage dès qu'une contrainte n'est pas vérifiée 
      \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}
    \item Ajout de la contrainte d'équilibre dans l'élagage
    \item Utilisation d'une forme canonique des CG :\\
      \begin{itemize}
      \item [$\Rightarrow$] Unicité des représentants
      \item [$\Rightarrow$] Ordre global sur les représentants :
        \begin{itemize}
        \item Détection efficace des doublons
        \item Stockage minimal
        \end{itemize}
      \end{itemize}
    \end{itemize}
  \end{frame}
}

\frameselect{true}{
  \begin{frame}
    \frametitle{Forme canonique des CG}
    
    \begin{itemize}
    \item Alignement sur début d'une sous-séquence avec \textbf{écart max} :
      \begin{itemize}
      \item Plus grand intervalle entre 2 occurrences d'une même dimension
      \end{itemize}
    \item Écart max sur l'ensemble des dimensions = \textbf{équilibre local}
    \item Renumérotation des dimensions :
      \begin{itemize}
      \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 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}
      $\Rightarrow$ Génération exhaustive en accord avec la théorie (dims $\le$ 5)
    \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}

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