\usenavigationsymbolstemplate{}
\usepackage{thumbpdf}
-\usepackage[T1]{fontenc}
-\usepackage[latin1]{inputenc}
+\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}
\graphicspath{{Figures/}}
\newboolean{acroread}
\setboolean{acroread}{true}
+\newcommand{\Bool}[0]{\ensuremath{\mathds{B}}}
\newcommand{\N}{\mathbb N}
\newcommand{\R}{\mathbb R}
\newcommand{\Z}{\mathbb Z}
\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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 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}
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-% 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]
- \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}
- \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}
- \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}
- Définitions :
+ Définitions :
\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}
\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}
- \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})$}
- 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}
- \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)$
- \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}
\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)$
- \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)$
\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}
- \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)$\\
\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)$
- \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}
- Fréquences = 10, 6, 8, 4, 4
+ Fréquences = 10, 6, 8, 4, 4
\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}
- 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\}$\\
- 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$}
- \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}
- 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}
- \frametitle{Construction de CG équilibrés}
+ \frametitle{Construction de CG équilibrés}
- L'idée est de :
+ L'idée est de :
\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}
- \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}
- \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 Appliquer la contrainte d'équilibre aux formulations obtenues
+ \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$
+ $\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}
+ \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 :\\
+ \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 :
+ \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 !
+ \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}
+ \frametitle{Construction de CG équilibrés}
Comme $u_0,u_1,u_2$ et $v$ sont vides, on a :
\begin{itemize}
\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}
- \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}
- \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$ :\\
- 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 !\\
- (à partir des dimensions 2 et 3)
+ (à partir des dimensions 2 et 3)
\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}
- \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}
- \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}
- \item Condition locale (chaque noeud) : degré 2
+ \item Condition locale (chaque noeud) : degré 2
\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
- \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}
}
+\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 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 :
+ \item [$\Rightarrow$] Unicité des représentants
+ \item [$\Rightarrow$] Ordre global sur les représentants :
\begin{itemize}
- \item Détection efficace des doublons
+ \item Détection efficace des doublons
\item Stockage minimal
\end{itemize}
\end{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}
- \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}
- \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}
- \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 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}
- $\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}
}
+
+\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:
