X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/16dcc.git/blobdiff_plain/79f46c777f6ef3202c2fb25194822518cad3e32c..HEAD:/presPRNG.tex diff --git a/presPRNG.tex b/presPRNG.tex index bbb82e9..dda0268 100644 --- a/presPRNG.tex +++ b/presPRNG.tex @@ -5,17 +5,20 @@ \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} +\usepackage{stmaryrd} \graphicspath{{Figures/}} @@ -24,6 +27,7 @@ \newboolean{acroread} \setboolean{acroread}{true} +\newcommand{\Bool}[0]{\ensuremath{\mathds{B}}} \newcommand{\N}{\mathbb N} \newcommand{\R}{\mathbb R} \newcommand{\Z}{\mathbb Z} @@ -37,6 +41,7 @@ \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} @@ -70,13 +75,13 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 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} @@ -88,26 +93,154 @@ } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% 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} +$$ +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} + \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} @@ -115,24 +248,24 @@ \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} @@ -141,13 +274,13 @@ \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)$ @@ -158,13 +291,13 @@ \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)$\\ @@ -173,93 +306,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 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} @@ -272,75 +405,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} - $\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} @@ -353,27 +521,183 @@ \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} +} + + + \begin{frame} + \frametitle{Perspectives} +\begin{itemize} +\item Qu'est-ce qu'un $\mathsf{N}$-cube? +\item Justifier les trois arrêtes sortantes du n{\oe}ud $010$ de la figure~1. +\item Illustrer à l'aide d'un graphe le fait que la fonction $f^*$, définie au milieu de la~page~3 est un 3-cube privé d'un cycle hamiltonien. +\item Pourquoi l'extension de Robinson-Cohn (page 11) n'est-elle pas un algorithme? A quoi sert la démonstration de la section 5.2? +\item Quel est l'objectif de la section~6? +Ordonner les lemmes et théorèmes de cette section pour dégager le résultat +final. +\item Expliquer toutes les informations que l'on peut trouver dans la seconde +ligne du tableau de la page 18 (ligne portant le libéllé \og function \textcircled{a}\fg{}. +\end{itemize} +\end{frame} + + + \end{document} + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: t +%%% End: