From 78cd1e6fef0e2664357da1584c958f06b0820a88 Mon Sep 17 00:00:00 2001 From: couchot Date: Fri, 26 Aug 2016 15:58:51 +0200 Subject: [PATCH 1/1] fin prng --- 14Secrypt.tex | 170 ++++++++++++++++++++++++-------- demandeInscription/synthese.tex | 2 +- main.tex | 5 + 3 files changed, 134 insertions(+), 43 deletions(-) diff --git a/14Secrypt.tex b/14Secrypt.tex index 597acbb..f1fae6f 100644 --- a/14Secrypt.tex +++ b/14Secrypt.tex @@ -380,43 +380,65 @@ vérifiant $\sum_{i=1}^nNT_n(i) = 2^n$. \section{Génération de codes de Gray équilibrés par induction} \label{sec:induction} -Dans leur article de 2004~\cite{ZanSup04}, Zanten et Suparta proposent un -algorithme inductif pour générer des codes de Gray équilibrés de $n$ bits à -partir de codes de $n-2$ bits. Cependant, leur méthode n'est pas -constructive. En effet, elle effectue des manipulations sur un partitionnement du -code de Gray initial de $n-2$ bits pour obtenir un code de Gray sur $n$ bits, -mais le résultat n'est pas systématiquement équilibré. Il est donc nécessaire -d'évaluer les résultats obtenus à partir de tous les partitionnements réalisables -en suivant les contraintes spécifiées. Or, le nombre de possibilités augmente -exponentiellement (voir~\cite{Mons14} pour l'évaluation détaillée), ce qui rend -déraisonnable tout parcours exhaustif. Une amélioration proposée -dans~\cite{Mons14} permet de réduire le nombre de partitionnements considérés, -mais l'ordre de grandeur reste similaire. On constate donc clairement ici la -nécessité de trouver des algorithmes de génération de codes de Gray équilibrés -plus efficaces. Ce problème représente une des voies que nous souhaitons -explorer dans la suite de nos travaux. - -Le tableau~\ref{table:nbFunc} donne le nombre de fonctions différentes -compatibles avec les codes de Gray équilibrés générés par l'approche précédente -selon le nombre de bits. Il donne donc la taille de la classe des générateurs -pouvant être produits. Les cas 7 et 8 ne sont que des bornes minimales basées -sur des sous-ensembles des partitionnements possibles. +De nombreuses approches ont été developpées pour résoudre le problème de construire +un code de Gray dans un $\mathsf{N}$-cube~\cite{Robinson:1981:CS,DBLP:journals/combinatorics/BhatS96,ZanSup04}, +selon les propriétés que doit vérifier ce code. + +Dans les travaux~\cite{Robinson:1981:CS}, les auteurs +proposent une approche inductive de construction de code de Gray équilibrés +(on passe du $\mathsf{N}-2$ à $\mathsf{N}$) +pour peu que l'utilisateur fournisse une sous-séquence possédant certaines +propriétés à chaque pas inductif. +Ce travail a été renforcé dans ~\cite{DBLP:journals/combinatorics/BhatS96} +où les auteurs donnent une manière explicite de construire une telle sous-séquence. +Enfin, les autheurs de~\cite{ZanSup04} présentent une extension de l'algorithme de +\emph{Robinson-Cohn}. La présentation rigoureuse de cette extension leur permet +principalement de prouver que si $\mathsf{N}$ est une puissance de 2, +le code de Gray équilibré engendré par l'extension est toujours totalement équilibré et +que $S_{\mathsf{N}}$ est la séquence de transition d'un code de Gray de $\mathsf{N}$ bits +si $S_{\mathsf{N}-2}$ l'est aussi.. +Cependant les auteurs ne prouvent pas que leur approche fournit systématiquement +un code de Gray (totalement) équilibré. +Cette section montre que ceci est vrai en rappelant tout d'abord +l'extension de l'algorithme de \emph{Robinson-Cohn} pour un +code de Gray avec $\mathsf{N}-2$ bits. -\begin{table}[ht] - \begin{center} - \begin{tabular}{|l|c|c|c|c|c|} - \hline - $n$ & 4 & 5 & 6 & 7 & 8 \\ - \hline - nb. de fonctions & 1 & 2 & 1332 & $>$ 2300 & $>$ 4500 \\ - \hline - \end{tabular} - \end{center} -\caption{Nombre de codes de Gray équilibrés selon le nombre de bits.}\label{table:nbFunc} -\end{table} +\begin{enumerate} +\item \label{item:nondet}Soit $l$ un entier positif pair. Trouver des sous-sequences +$u_1, u_2, \dots , u_{l-2}, v$ (possiblement vides) de $S_{\mathsf{N}-2}$ +telles que $S_{\mathsf{N}-2}$ est la concaténation de +$$ +s_{i_1}, u_0, s_{i_2}, u_1, s_{i_3}, u_2, \dots , s_{i_l-1}, u_{l-2}, s_{i_l}, v +$$ +où $i_1 = 1$, $i_2 = 2$, et $u_0 = \emptyset$ (la séquence vide). +\item\label{item:u'} Remplacer dans $S_{\mathsf{N}-2}$ les sequences $u_0, u_1, u_2, \ldots, u_{l-2}$ + par + $\mathsf{N} - 1, u'(u_1,\mathsf{N} - 1, \mathsf{N}) , u'(u_2,\mathsf{N}, \mathsf{N} - 1), u'(u_3,\mathsf{N} - 1,\mathsf{N}), \dots, u'(u_{l-2},\mathsf{N}, \mathsf{N} - 1)$ + respectivement, où $u'(u,x,y)$ est la séquence $u,x,u^R,y,u$ telle que + $u^R$ est $u$, mais dans l'ordre inverse. La séquence obtenue est ensuite notée $U$. +\item\label{item:VW} Contruire les séquences $V=v^R,\mathsf{N},v$, $W=\mathsf{N}-1,S_{\mathsf{N}-2},\mathsf{N}$. Soit alors $W'$ définie commé étant égale à $W$ sauf pour les +deux premiers éléments qui ont été intervertis. +\item La séquence de transition $S_{\mathsf{N}}$ est la concatenation $U^R, V, W'$. +\end{enumerate} + +L'étape~(\ref{item:nondet}) n'est pas constructive: il n'est pas précisé +comment sélectionner des sous-séquences qui assurent que le code obtenu est équilibré. +La théoreme suivante montre que c'est possible et sa preuve explique comment le faire. + + +\begin{theorem}\label{prop:balanced} +Soit $\mathsf{N}$ dans $\Nats^*$, et $a_{\mathsf{N}}$ défini par +$a_{\mathsf{N}}= 2 \left\lfloor \dfrac{2^{\mathsf{N}}}{2\mathsf{N}} \right\rfloor$. +il existe une séquence $l$ dans l'étape~(\ref{item:nondet}) de l'extension +de l'algorithme de \emph{Robinson-Cohn} extension telle que +le nombres de transitions $\textit{TC}_{\mathsf{N}}(i)$ +sont tous $a_{\mathsf{N}}$ ou $a_{\mathsf{N}}+2$ +pour chaque $i$, $1 \le i \le \mathsf{N}$. +\end{theorem} +La preuve de ce théorème est donnée en annexes~\ref{anx:generateur}. -Ces fonctions étant générée, on s'intéresse à étudier à quelle vitesse +Ces fonctions étant générées, on s'intéresse à étudier à quelle vitesse un générateur les embarquant converge vers la distribution uniforme. C'est l'objectif de la section suivante. @@ -541,19 +563,22 @@ Si $\tau$ est un temps d'arrêt fort, alors $d(t)\leq \max_{X\in\Bool^{\mathsf{N \P_X(\tau > t)$. \end{theorem} + +Soit alors $\ov{h} : \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ la fonction +telle que pour $X \in \Bool^{\mathsf{N}} $, +$(X,\ov{h}(X)) \in E$ et $X\oplus\ov{h}(X)=0^{{\mathsf{N}}-h(X)}10^{h(X)-1}$. +La fonction $\ov{h}$ est dite {\it anti-involutive} si pour tout $X\in \Bool^{\mathsf{N}}$, +$\ov{h}(\ov{h}(X))\neq X$. + + \begin{theorem} \label{prop:stop} -If $\ov{h}$ is bijective et telle que if for every $X\in \Bool^{\mathsf{N}}$, +Si $\ov{h}$ is bijective et anti involutive $\ov{h}(\ov{h}(X))\neq X$, alors $E[\ts]\leq 8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1)$. \end{theorem} -Sans entrer dans les détails de la preuve, on remarque tout d'abord -que le calcul -de cette borne n'intègre pas le fait qu'on préfère enlever des -chemins hamiltoniens équilibrés. -En intégrant cette contrainte, la borne supérieure pourrait être réduite. - -On remarque ensuite que la chaîne de Markov proposée ne suit pas exactement +Les détails de la preuve sont donnés en annexes~\ref{anx:generateur}. +On remarque tout d'abord que la chaîne de Markov proposée ne suit pas exactement l'algorithme~\ref{CI Algorithm}. En effet dans la section présente, la probabilité de rester dans une configuration donnée est fixée à $frac{1}{2}+\frac{1}{2n}$. @@ -563,6 +588,67 @@ a été introduite pour simplifier le calcul de la borne sup du temps d'arrêt. +Sans entrer dans les détails de la preuve, on remarque aussi +que le calcul de cette borne impose uniquement que +pour chaque n{\oe}ud du $\mathsf{N}$-cube +un arc entrant et un arc sortant sont supprimés. +Le fait qu'on enlève un cycle hamiltonien et que ce dernier +soit équilibré n'est pas pris en compte. +En intégrant cette contrainte, la borne supérieure pourrait être réduite. + +En effet, le temps de mixage est en $\Theta(N\ln N)$ lors d'une +marche aléatoire classique paresseuse dans le $\mathsf{N}$-cube. +On peut ainsi conjecturer que cet ordre de grandeur reste le même +dans le contexte du $\mathsf{N}$-cube privé d'un chemin hamiltonien. + +On peut évaluer ceci pratiquement: pour une fonction +$f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ et une graine initiale +$x^0$, le code donné à l'algorithme algorithm~\ref{algo:stop} retourne le +nombre d'itérations suffisant tel que tous les éléments $\ell\in \llbracket 1,{\mathsf{N}} \rrbracket$ sont équitables. Il permet de déduire une approximation de $E[\ts]$ +en l'instanciant un grand nombre de fois: pour chaque nombre $\mathsf{N}$, +$ 3 \le \mathsf{N} \le 16$, 10 fonctionss ont été générées comme dans +ce chapitre. Pour chacune d'elle, le calcul d'une approximation de $E[\ts]$ +est exécuté 10000 fois avec une graine aléatoire.La Figure~\ref{fig:stopping:moy} +résume ces resultats. Dans celle-ci, un cercle représente une approximation de +$E[\ts]$ pour un $\mathsf{N}$ donné tandis que la courbe est une représentation de +la fonction $x \mapsto 2x\ln(2x+8)$. +On cosntate que l'approximation de $E[\ts]$ est largement inférieure +à la borne quadratique donnée au thérème~\ref{prop:stop} et que la conjecture +donnée au paragraphe précédent est sensée. + + +\begin{algorithm}[ht] +%\begin{scriptsize} +\KwIn{a function $f$, an initial configuration $x^0$ ($\mathsf{N}$ bits)} +\KwOut{a number of iterations $\textit{nbit}$} + +$\textit{nbit} \leftarrow 0$\; +$x\leftarrow x^0$\; +$\textit{fair}\leftarrow\emptyset$\; +\While{$\left\vert{\textit{fair}}\right\vert < \mathsf{N} $} +{ + $ s \leftarrow \textit{Random}(\mathsf{N})$ \; + $\textit{image} \leftarrow f(x) $\; + \If{$\textit{Random}(1) \neq 0$ and $x[s] \neq \textit{image}[s]$}{ + $\textit{fair} \leftarrow \textit{fair} \cup \{s\}$\; + $x[s] \leftarrow \textit{image}[s]$\; + } + $\textit{nbit} \leftarrow \textit{nbit}+1$\; +} +\Return{$\textit{nbit}$}\; +%\end{scriptsize} +\caption{Pseudo Code of stoping time calculus } +\label{algo:stop} +\end{algorithm} + + +\begin{figure} +\centering +\includegraphics[width=0.49\textwidth]{images/complexityET} +\caption{Average Stopping Time Approximation}\label{fig:stopping:moy} +\end{figure} + + \section{Et les itérations généralisées?} diff --git a/demandeInscription/synthese.tex b/demandeInscription/synthese.tex index 5553fd9..03c44f7 100755 --- a/demandeInscription/synthese.tex +++ b/demandeInscription/synthese.tex @@ -1377,7 +1377,7 @@ Jacques Bahi, Jean-Fran\c{c}ois Couchot, and Christophe Guyeux. Jean-François Couchot, Sylvain Contassot-Vivier, Christophe Guyeux, and Pierre-Cyrille H\'eam. \newblock Random walk in a n-cube without hamiltonian cycle to chaotic pseudorandom number generation: Theoretical and practical considerations. -\newblock in submission. +\newblock in submission to Elsevier Chaos, Solitons \& Fractal, August 2016. \bibitem{bgco16:onp} Mohammed Bakiri, Christophe Guyeux, Jean-Fran\c{c}cois Couchot, and diff --git a/main.tex b/main.tex index cacbb94..0a4591e 100644 --- a/main.tex +++ b/main.tex @@ -244,6 +244,10 @@ On montre qu'on a des résultats similaires. \chapter{Une démarches plus classique de dissimulation: STABYLO} \input{stabylo} +\chapter{Une démarches plus classique de dissimulation: STABYLO} + \input{stabylo} + + \part{Conclusion et Perspectives} @@ -332,6 +336,7 @@ du chapitre 8} \chapter{Preuves sur les générateurs de nombres pseudo-aléatoires}\label{anx:generateur} \input{annexePreuveDistribution} +\input{annexePreuveGrayEquilibre} \input{annexePreuveStopping} \chapter{Preuves sur le marquage de média}\label{anx:marquage} -- 2.39.5