From 23f35c6593b3de7d37b266c9ef6c35da97d98998 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Jean-Fran=C3=A7ois=20Couchot?= Date: Tue, 21 Jul 2015 16:13:25 +0200 Subject: [PATCH] ajout de 14secrypt --- 14Secrypt.tex | 396 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 396 insertions(+) create mode 100644 14Secrypt.tex diff --git a/14Secrypt.tex b/14Secrypt.tex new file mode 100644 index 0000000..b7cb0d3 --- /dev/null +++ b/14Secrypt.tex @@ -0,0 +1,396 @@ +On a vu dans le chapitre précédent que pour avoir +un générateur à sortie +uniforme, il est nécessaire que la matrice d'adjacence du graphe d'itération du +système soit doublement stochastique. Nous présentons dans cette partie une +méthode permettant de générer de telles matrices. + +Les approches théoriques basées sur la programmation logique par contraintes sur +domaines finis ne sont pas envisageables en pratique dès que la taille des +matrices considérées devient suffisamment grande. + +Une approche plus pragmatique consiste à supprimer un cycle hamiltonien dans le +graphe d'itérations, ce qui revient à supprimer en chaque n{\oe}ud de ce graphe une +arête sortante et une arête entrante. + + +This aim of this section is to show +that finding DSSC matrices from a hypercube +is a typical finite domain satisfaction +problem, classically denoted as +Constraint Logic Programming on Finite Domains (CLPFD). +This part is addressed in the first section. Next, we analyse the first +results to provide a generation of DSSC matrices with small mixing times. + +\section{Programmation logique par contraintes sur des domaines finis} +Tout d'abord, soit ${\mathsf{N}}$ le nombre d'éléments. +Pour éviter d'avoir à gérér des fractions, on peut considérer que +les matrices (d'incidence) à générer ont des lignes et des colonnes dont les +sommes valent ${\mathsf{N}}$ à chaque fois. +On cherche ainsi toutes les matrices $M$ de taille $2^{\mathsf{N}}\times 2^{\mathsf{N}}$ telles que + +\begin{enumerate} +\item $M_{ij}$ vaut 0 si $j$ n'est pas un voisin de $i$, \textit{i.e.}, + il n'y a pas d'arc de $i$ à $j$ dans le graphe $\textsc{giu}(f)$; + +\item $0 \le M_{ii} \le {\mathsf{N}}$: le nombre de boucles autour de chaque +configuration $i$ est inférieur à ${\mathsf{N}}$; + +\item pour $j \neq i$, $0 \le M_{ij} \le 1$: on construit l'arc de $i$ à $j$ +si et seulement si $M_{ij}$ vaut 1 (et 0 sinon) +\item pour chque indice de ligne $i$, $1 \le i\le 2^{\mathsf{N}}$, ${\mathsf{N}} = \sum_{1 \le j\le 2^{\mathsf{N}}} M_{ij}$: +la matrice est stochastique à droite; +\item pour chque indice de colonne $j$, + $1 \le j\le 2^{\mathsf{N}}$, ${\mathsf{N}} = \sum_{1 \le i\le 2^{\mathsf{N}}} M_{ij}$: + la matrice est stochastique à gauche; +\item Toutes les éléments de la somme $\sum_{1\le k\le 2^{\mathsf{N}}}M^k$ sont strictement positif, \textit{i.e.}, le graphe $\textsc{giu}(f)$ est fortement connexe; +\end{enumerate} +Ce problème s'exprime sur des domaines finis entiers avec des opérateurs +arithmétiques simples (sommes et poduits). il pourrait théoriquement être +traité par desdémarches de programation logique par contrainte +sur des domaines finis (comme en PROLOG). +L'algorithme donné en Figure~\ref{fig:prolog} +est en effet le c{\oe}ur du programme PROLOG +qui pourrait être utilisé pour instancier toutes les solutions, +ici pour $\mathsf{N} = 2$. Dans ce code, +\verb+mmult(+$X,Y,R$\verb+)+ et +\verb+summ(+$X,Y,R$\verb+)+ +valent True si et seulement si $R$ +est le produit matriciel (ou la somme matricielle) +entre $X$ and $Y$ respectivement. +il n'est pas difficile d'adapter ce code à n'importe quelle valeur +entière naturelle $\mathsf{N}$. + +\begin{figure}[ht] +\begin{scriptsize} +\lstset{language=prolog} +\begin{lstlisting} +bistoc(X):- + M=[[M0_0, M0_1, 0, M0_3], [M1_0, M1_1, 0, M1_3], + [M2_0, 0, M2_2, M2_3], [0, M3_1, M3_2, M3_3]], + [M0_0, M1_1, M2_2, M3_3] ins 0..2, + [M0_1, M0_3, M1_0, M1_3, M2_0, M2_3, M3_1, M3_2] + ins 0..1, + M0_0+ M0_1+ M0_2 #=2, M1_0+ M1_1+ M1_3 #=2, + M2_0+ M2_2+ M2_3 #=2, M3_1+ M3_2+ M3_3 #=2, + M0_0+ M1_0+ M2_0 #=2, M0_1+ M1_1+ M3_1 #=2, + M0_2+ M2_2+ M3_2 #=2, M1_3+ M2_3+ M3_3 #=2, + mmult(M,M,M2), + mmult(M,M2,M3), + mmult(M,M3,M4), + summ(M,M2,S2), + summ(S2,M3,S3), + summ(S3,M4,S4), + allpositive(S4). +\end{lstlisting} +\end{scriptsize} +\caption{Prolog Problem to Find DSSC Matrix when $n=2$}\label{fig:prolog} +\end{figure} + +Enfin, on définit la relation $\mathcal{R}$, qui est établie pourles deux +fonctions $f$ et $g$ si leur graphes +respectifs $\textsf{giu}(f)$ et $\textsf{giu}(g)$ +sont isomorphes. +C'est évidemment une relation d'équivalence. + + + +\subsection{Analyse de l'approche} +Exécutée sur un ordinateur personnelle, PROLOG trouve +en moins d'une seconde les +49 solutions pour $n=2$, +dont 2 seulement ne sont pas équivalentes, +en moins d'une minute les 27642 solutions dont seulement 111 ne +sont pas équivalentes pour $n=3$. +Cependant, l'approche ne permet pas d'engendrer toutes les solutions +pour $n=4$. +Cette approche, basée sur une démarche de type \emph{générer, tester} ne peut +pas être retenue pour $n$ de grande taille, même +en s'appuyant sur l'éfficience de l'algorithme de backtrack natif de PROLOG. + +Cependant, pour des valeurs de $n$ petites, nous avons +comparé les fonctions non équivalantes selon leur proportion +à engendrer des temps de mélange petits (cf. équation~\ref{eq:mt:ex}). + + + + +\begin{xpl} +Le tableau~\ref{table:mixing:3} fournit les 5 fonctions booléennes +qui ont les temps de mélange les plus petits pour $\varepsilon=10^{-5}$. +\begin{table}[ht] +\begin{small} +$$ +\begin{array}{|l|l|l|} +\hline +\textrm{Name} & \textrm{Image} & \textrm{MT}\\ +\hline +f^a & (x_2 \oplus x_3, x_1 \oplus \overline{x_3},\overline{x_3}) & 16 \\ +\hline +f^* & (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) & 17 \\ +\hline +f^b & (\overline{x_1}(x_2+x_3) + x_2x_3,\overline{x_1}(\overline{x_2}+\overline{x_3}) + \overline{x_2}\overline{x_3}, & \\ +& \qquad \overline{x_3}(\overline{x_1}+x_2) + \overline{x_1}x_2) & 26 \\ +\hline +f^c & (\overline{x_1}(x_2+x_3) + x_2x_3,\overline{x_1}(\overline{x_2}+\overline{x_3}) + \overline{x_2}\overline{x_3}, & \\ +& \overline{x_3}(\overline{x_1}+x_2) + \overline{x_1}x_2) & 29 \\ +\hline +f^d & (x_1\oplus x_2,x_3(\overline{x_1}+\overline{x_2}),\overline{x_3}) & 30 \\ +\hline +% [3, 4, 7, 0, 1, 6, 5, 2], #16 +% [3, 4, 7, 0, 2, 6, 5, 1], #17 +% [3, 6, 7, 5, 2, 0, 1, 4], #26 +% [3, 4, 7, 5, 2, 6, 1, 0], #29 +% [3, 2, 5, 6, 7, 0, 1, 4]] #30 +\end{array} +$$ +\end{small} +\caption{Les 5 fonctions booléennes $n=3$ aux temps de mélange les plus faibles.}\label{table:mixing:3} +\end{table} +\end{xpl} + +Une analyse syntaxique de ces fonctions ne permet pas, à priori, +de déduire des règles permettant de construire de nouvelles +fonction dont le temps de mélange serait faible. +Cependant, le graphe $\textsc{giu}(f^*)$ +(donné à la Figure~\ref{fig:iteration:f*}) +est le $3$-cube dans lequel le cycle +$000,100,101,001,011,111,110,010,000$ +a été enlevé. +Ce cycle qui visite chaque n{\oe}ud exactement une fois est un +\emph{cycle hamiltonien}. +La matrice de Markov correspondante est donnée à +la figure~\ref{fig:markov:f*}. +On s'intéresse par la suite à la génération de ce genre de cycles. + + + + + +\begin{figure}[ht] + \begin{center} + \subfigure[Graphe $\textsc{giu}(f^*)$. + \label{fig:iteration:f*}]{ + \begin{minipage}{0.55\linewidth} + \centering + \includegraphics[width=\columnwidth]{images/iter_f0c}% + \end{minipage} + }% + \subfigure[Matrice de Markov associée à $\textsc{giu}(f^*)$ + \label{fig:markov:f*}]{% + \begin{minipage}{0.35\linewidth} + \begin{scriptsize} + \begin{center} + $ \dfrac{1}{4} \left( + \begin{array}{cccccccc} + 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ + + 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ + + 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ + + 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ + + 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ + + 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ + + 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ + + 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ + + \end{array} \right) $ + \end{center} + \end{scriptsize} + \end{minipage} + }% + \caption{Représentations de $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)$.}\label{fig1} + \end{center} +\end{figure} + + + + +\section{Graphes + $\textsc{giu}(f)$ + $\textsc{gig}(f)$ + fortement connexes et doublement stochastiques} +% Secrypt 14 + + + + +\subsection{Suppression des cycles hamiltoniens} +\label{sec:hamiltonian} + +Dans un premier temps, nous montrons en section~\ref{sub:removing:theory} que la +suppression d'un cycle hamiltonien produit bien des matrices doublement +stochastiques. Nous établissons ensuite le lien avec les codes de Gray +équilibrés. + +\subsubsection{Aspects théoriques} +\label{sub:removing:theory} + +Nous donnons deux résultats complémentaires, reliant la suppression d'un cycle +hamiltonien du $n$-cube, les matrices doublement stochastiques et la forte +connexité du graphe d'itérations. + +\begin{theorem}\label{th:supprCH} + La suppression d'un cycle hamiltonien dans une matrice de Markov $M$, issue du + $n$-cube, produit une matrice doublement stochastique. +\end{theorem} +\begin{Proof} + +Un cycle hamiltonien passe par chaque n{\oe}ud une et une seule fois. +Pour chaque n{\oe}ud $v$ dans le $n$-cube $C_1$, +une arête entrante $(o,v)$ et une arête sortante $(v,e)$ +est ainsi enlevée. +Considérons un autre $n$-cube $C_2$ auquel on ajoute les arêtes +pour le rendre complet. La matrice de Markov $M$ correspondante est +remplie de $\frac{1}{2^n}$ et est doublement stochastique. +Comme on enlève exactement une arête sortante $(v,e)$ +à chaque n{\oe}ud $v$ dans $C_1$, on enlève ainsi dans +$C_2$ les $2^{n-1}$ arêtes issues de $v$ et +relatives aux parties de $\{1,\ldots,n\}$ qui +contiennent $e$. Cela revient à annuler +dans la matrice $M$ les $2^{n-1}$ coefficients correspondants et ajouter +$1/2$ à l'élément $M_{vv}$. +La matrice $M$ reste stochastique. +On effectue un raisonnement similaire pour les arêtes entrantes: +comme on enlève exactement une arête entrante $(o,v)$ pour chaque +n{\oe}ud $v$ dans $C_1$, dans $C_2$, ce sont exactement +$2^{n-1}$ arêtes menant à $v$ qui sont enlevées. +Dans $M$ les $2^{n-1}$ coefficients correspondants sont mis à 0 et +$M_{vv}$ vaut alors $\frac{2^{n-1} +1}{2}$. +$M$ est donc doublement stochastique. +\end{Proof} + + + +\begin{theorem}\label{th:grapheFC} + Le graphe d'itérations issu du $n$-cube, auquel un cycle hamiltonien est + enlevé, est fortement connexe. +\end{theorem} + + +\begin{Proof} +On considère les deux $n$-cubes $C_1$ et $C_2$ définis +dans la preuve du théorème~\ref{th:supprCH}. +Dans $C_1$ on considère le cycle inverse $r$ du cycle +hamiltonien $c$. +Aucun arc n'appartient à la fois à $r$ et à $c$: +en effet, sinon $c$ contiendrait un n{\oe}ud deux fois. +Ainsi aucune arête de $r$ n'est enlevée dans $C_1$. +Le cycle $r$ est évidement un cycle hamiltonien et contient tous les n{\oe}uds. +Tous les n{\oe}uds de $C_1$ dans lequel $c$ a été enlevé sont accessibles +depuis n'importe quel n{\oe}ud. Le graphe des itérations $\textsf{giu}$ qui +étend le précédent graphe est ainsi fortement connexe. + +\end{Proof} + + + +Les preuves, relativement directes, sont laissées en exercices au lecteur. Par +contre, ce qui est moins aisé est la génération de cycles hamiltoniens dans le +$n$-cube, ce qui revient à trouver des \emph{codes de Gray cycliques}. On +rappelle que les codes de Gray sont des séquences de mots binaires de taille +fixe ($n$), dont les éléments successifs ne différent que par un seul bit. Un +code de Gray est \emph{cyclique} si le premier élément et le dernier ne +différent que par un seul bit. + +\subsection{Lien avec les codes de Gray cycliques (totalement) équilibrés} +\label{sub:gray} + +La borne inférieure du nombre de codes de Gray ($\left(\frac{n*\log2}{e \log + \log n}\times(1 - o(1))\right)^{2^n}$), donnée dans~\cite{Feder2009NTB}, +indique une explosion combinatoire pour notre recherche. Afin de contourner +cette difficulté, nous nous restreignons aux codes induisant un graphe +d'itérations $\textsf{giu}(f)$ \emph{uniforme}. Cette uniformité se traduit par des +nombres d'arcs équilibrés entre les \emph{dimensions} du graphe, la dimension +$i$ correspondant aux seules variations du bit $i$ (parmi les $n$ bits au +total). Cette approche revient à chercher des codes de Gray cycliques +\emph{équilibrés}. + +Un code de Gray équilibré peut être défini de la façon suivante : + +\begin{Def}[Code de Gray cyclique équilibré]\label{def:grayequ} + Soit $L = w_1, w_2, \dots, w_{2^n}$ la séquence d'un code de Gray cyclique à + $n$ bits. Soit $S = s_1, s_2, \dots, s_{2^n}$ la séquence des transitions où + $s_i$, $1 \le i \le 2^n$ est l'indice du seul bit qui varie entre les mots + $w_i$ et $w_{i+1}$. Enfin, soit $\textit{NT}_n : \{1,\dots, n\} \rightarrow + \{0, \ldots, 2^n\}$ la fonction qui au paramètre $i$ associe le \emph{nombre + de transitions} présentes dans la séquence $L$ pour le bit $i$, c'est-à-dire + le nombre d'occurrences de $i$ dans $S$. + + Le code $L$ est \textbf{équilibré} si $\forall + i,j\in\{1,...,n\},~|\textit{NT}_n(i) - \textit{NT}_n(j)| \le 2$. Il est + \textbf{totalement équilibré} si $\forall + i\in\{1,...,n\},~\textit{NT}_n(i)=\frac{2^n}{n}$. +\end{Def} + +On peut donc déjà déduire qu'il ne peut exister des codes de Gray totalement +équilibrés que pour les systèmes ayant un nombre d'éléments $n=2^k, k>0$. De +plus, comme dans tout code de Gray cyclique, $\textit{NT}_n(i)$ est pair +$\forall i\in\{1,...,n\}$, alors les systèmes ayant un nombre d'éléments +différent de $2^k$, ne peuvent avoir que des codes de Gray équilibrés avec +$\textit{NT}_n(i)=\lfloor\frac{2^n}{n}\rfloor$ ou +$\textit{NT}_n(i)=\lceil\frac{2^n}{n}\rceil, \forall i\in\{1,...,n\}$ et +vérifiant $\sum_{i=1}^nNT_n(i) = 2^n$. + +\begin{xpl} + Soit $L^*=000,100,101,001,011,111,110,010$ le code de Gray correspondant au + cycle hamiltonien enlevé de $f^*$. Sa séquence des transitions est \linebreak + $S=3,1,3,2,3,1,3,2$ et les nombres de transitions sont $\textit{TC}_3(1)= + \textit{TC}_3(2)=2$ et $\textit{TC}_3(3)=4$. Un tel code est équilibré. + + Si l'on considère maintenant $L^4=$ 0000, 0010, 0110, 1110, 1111, 0111, 0011, + 0001, 0101, 0100, 1100, 1101, 1001, 1011, 1010, 1000, un code de Gray + cyclique. En construisant la séquence $S=$ 2,3,4,1,4,3,2,3,1,4,1,3,2,1,2,4, + on constate que $\forall + i\in\{1,..,4\},~\textit{TC}_4(i)=4$ et donc que + ce code est totalement équilibré. +\end{xpl} + +\subsection{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. + +\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 générateurs selon le nombre de bits.}\label{table:nbFunc} +\end{table} + + +\section{Quantifier l'écart par rapport à la distribution uniforme} +%15 Rairo \ No newline at end of file -- 2.39.5