14Secrypt.tex

   1 On  a vu  dans  le chapitre précédent  que  pour avoir
   2 un  générateur à  sortie
   3 uniforme, il est nécessaire que  la matrice d'adjacence du graphe d'itération du
   4 système  soit doublement stochastique.   Nous présentons  dans cette  partie une
   5 méthode permettant de générer de telles matrices.
   6
   7 Les approches théoriques basées sur la programmation logique par contraintes sur
   8 domaines  finis ne  sont pas  envisageables en  pratique dès  que la  taille des
   9 matrices considérées devient suffisamment grande.
  10
  11 Une approche plus pragmatique consiste  à supprimer un cycle hamiltonien dans le
  12 graphe d'itérations, ce qui revient à supprimer en chaque n{\oe}ud de ce graphe une
  13 arête sortante et une arête entrante.
  14
  15
  16 This aim of this section is to show
  17 that finding DSSC matrices from a hypercube
  18 is a typical finite domain satisfaction
  19 problem, classically denoted as
  20 Constraint Logic Programming on Finite Domains (CLPFD).
  21 This part is addressed in the first section. Next, we analyse the first
  22 results to provide a generation of DSSC matrices with small mixing times.
  23
  24 \section{Programmation logique par contraintes sur des domaines finis}
  25 Tout d'abord, soit ${\mathsf{N}}$ le nombre d'éléments.
  26 Pour éviter d'avoir à gérér des fractions, on peut considérer que
  27 les matrices (d'incidence) à générer ont des lignes et des colonnes dont les
  28 sommes valent ${\mathsf{N}}$ à chaque fois.
  29 On cherche ainsi toutes les matrices $M$ de taille  $2^{\mathsf{N}}\times 2^{\mathsf{N}}$ telles que
  30
  31 \begin{enumerate}
  32 \item $M_{ij}$ vaut 0 si $j$ n'est pas un voisin de $i$, \textit{i.e.},
  33   il n'y a pas d'arc de $i$ à $j$ dans le graphe $\textsc{giu}(f)$;
  34
  35 \item $0 \le M_{ii} \le {\mathsf{N}}$: le nombre de boucles autour de chaque
  36 configuration $i$ est inférieur à ${\mathsf{N}}$;
  37
  38 \item pour $j \neq i$,  $0 \le M_{ij} \le 1$: on construit l'arc de $i$ à $j$
  39 si et seulement si $M_{ij}$ vaut 1 (et 0 sinon)
  40 \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}$:
  41 la matrice est stochastique à droite;
  42 \item pour chque indice de colonne $j$,
  43   $1 \le j\le 2^{\mathsf{N}}$, ${\mathsf{N}} = \sum_{1 \le i\le 2^{\mathsf{N}}} M_{ij}$:
  44   la matrice est stochastique à gauche;
  45 \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;
  46 \end{enumerate}
  47 Ce problème s'exprime sur des domaines finis entiers avec des opérateurs
  48 arithmétiques simples (sommes et poduits). il pourrait théoriquement être
  49 traité par desdémarches de programation logique par contrainte
  50 sur des domaines finis (comme en PROLOG).
  51 L'algorithme donné en Figure~\ref{fig:prolog}
  52 est en effet le c{\oe}ur du programme PROLOG
  53 qui pourrait être utilisé pour instancier toutes les solutions,
  54 ici pour  $\mathsf{N} = 2$. Dans ce code,
  55 \verb+mmult(+$X,Y,R$\verb+)+ et
  56 \verb+summ(+$X,Y,R$\verb+)+
  57 valent True si et seulement si $R$
  58 est le produit matriciel  (ou la somme matricielle)
  59 entre  $X$ and $Y$ respectivement.
  60 il n'est pas difficile d'adapter ce code à n'importe quelle valeur
  61 entière naturelle  $\mathsf{N}$.
  62
  63 \begin{figure}[ht]
  64 \begin{scriptsize}
  65 \lstset{language=prolog}
  66 \begin{lstlisting}
  67 bistoc(X):-
  68   M=[[M0_0, M0_1, 0, M0_3], [M1_0, M1_1, 0, M1_3],
  69      [M2_0, 0, M2_2, M2_3], [0, M3_1, M3_2, M3_3]],
  70   [M0_0, M1_1, M2_2, M3_3] ins 0..2,
  71   [M0_1, M0_3, M1_0, M1_3, M2_0, M2_3, M3_1, M3_2]
  72      ins 0..1,
  73   M0_0+ M0_1+ M0_2 #=2, M1_0+ M1_1+ M1_3 #=2,
  74   M2_0+ M2_2+ M2_3 #=2, M3_1+ M3_2+ M3_3 #=2,
  75   M0_0+ M1_0+ M2_0 #=2, M0_1+ M1_1+ M3_1 #=2,
  76   M0_2+ M2_2+ M3_2 #=2, M1_3+ M2_3+ M3_3 #=2,
  77   mmult(M,M,M2),
  78   mmult(M,M2,M3),
  79   mmult(M,M3,M4),
  80   summ(M,M2,S2),
  81   summ(S2,M3,S3),
  82   summ(S3,M4,S4),
  83   allpositive(S4).
  84 \end{lstlisting}
  85 \end{scriptsize}
  86 \caption{Prolog Problem to Find DSSC Matrix when $n=2$}\label{fig:prolog}
  87 \end{figure}
  88
  89 Enfin, on définit la relation $\mathcal{R}$, qui est établie pourles deux
  90 fonctions  $f$ et $g$ si leur graphes
  91 respectifs  $\textsf{giu}(f)$ et $\textsf{giu}(g)$
  92 sont isomorphes.
  93 C'est évidemment une relation d'équivalence.
  94
  95
  96
  97 \subsection{Analyse de l'approche}
  98 Exécutée sur un ordinateur personnelle, PROLOG trouve
  99 en moins d'une seconde les
 100 49 solutions pour  $n=2$,
 101 dont 2 seulement ne sont pas équivalentes,
 102 en moins d'une minute les 27642 solutions dont seulement 111 ne
 103 sont pas équivalentes pour $n=3$.
 104 Cependant, l'approche ne permet pas d'engendrer toutes les solutions
 105 pour $n=4$.
 106 Cette approche, basée sur une démarche de type \emph{générer, tester} ne peut
 107 pas être retenue pour $n$ de grande taille, même
 108 en s'appuyant sur l'éfficience de l'algorithme de backtrack natif de PROLOG.
 109
 110 Cependant, pour des valeurs de $n$ petites, nous avons
 111 comparé les fonctions non équivalantes selon leur proportion
 112 à engendrer des temps de mélange petits (cf. équation~\ref{eq:mt:ex}).
 113
 114
 115
 116
 117 \begin{xpl}
 118 Le tableau~\ref{table:mixing:3} fournit les 5 fonctions booléennes
 119 qui ont les temps de mélange les plus petits pour $\varepsilon=10^{-5}$.
 120 \begin{table}[ht]
 121 \begin{small}
 122 $$
 123 \begin{array}{|l|l|l|}
 124 \hline
 125 \textrm{Name} & \textrm{Image} & \textrm{MT}\\
 126 \hline
 127 f^a &  (x_2 \oplus x_3, x_1 \oplus \overline{x_3},\overline{x_3})  &  16   \\
 128 \hline
 129 f^*  &  (x_2 \oplus x_3, \overline{x_1}\overline{x_3} + x_1\overline{x_2},
 130 \overline{x_1}\overline{x_3} + x_1x_2)  &  17   \\
 131 \hline
 132 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}, &  \\
 133 & \qquad \overline{x_3}(\overline{x_1}+x_2) + \overline{x_1}x_2)  &  26   \\
 134 \hline
 135 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}, & \\
 136 & \overline{x_3}(\overline{x_1}+x_2) + \overline{x_1}x_2)  &  29   \\
 137 \hline
 138 f^d  &  (x_1\oplus x_2,x_3(\overline{x_1}+\overline{x_2}),\overline{x_3})  &  30   \\
 139 \hline
 140 % [3, 4, 7, 0, 1, 6, 5, 2], #16
 141 % [3, 4, 7, 0, 2, 6, 5, 1], #17
 142 % [3, 6, 7, 5, 2, 0, 1, 4], #26
 143 % [3, 4, 7, 5, 2, 6, 1, 0], #29
 144 % [3, 2, 5, 6, 7, 0, 1, 4]] #30
 145 \end{array}
 146 $$
 147 \end{small}
 148 \caption{Les 5 fonctions booléennes $n=3$ aux temps de mélange les plus faibles.}\label{table:mixing:3}
 149 \end{table}
 150 \end{xpl}
 151
 152 Une analyse syntaxique de ces fonctions ne permet pas, à priori,
 153 de déduire des règles permettant de construire de nouvelles
 154 fonction dont le temps de mélange serait faible.
 155 Cependant, le graphe $\textsc{giu}(f^*)$
 156 (donné à la Figure~\ref{fig:iteration:f*})
 157 est le $3$-cube dans lequel le cycle
 158 $000,100,101,001,011,111,110,010,000$
 159 a été enlevé.
 160 Ce cycle qui visite chaque n{\oe}ud exactement une fois est un
 161 \emph{cycle hamiltonien}.
 162 La matrice de Markov correspondante est donnée à
 163 la figure~\ref{fig:markov:f*}.
 164 On s'intéresse  par la suite à la génération de ce genre de cycles.
 165
 166
 167
 168
 169
 170 \begin{figure}[ht]
 171   \begin{center}
 172     \subfigure[Graphe $\textsc{giu}(f^*)$.
 173     \label{fig:iteration:f*}]{
 174       \begin{minipage}{0.55\linewidth}
 175         \centering
 176         \includegraphics[width=\columnwidth]{images/iter_f0c}%
 177       \end{minipage}
 178     }%
 179     \subfigure[Matrice de Markov associée à $\textsc{giu}(f^*)$
 180     \label{fig:markov:f*}]{%
 181       \begin{minipage}{0.35\linewidth}
 182         \begin{scriptsize}
 183           \begin{center}
 184             $ \dfrac{1}{4} \left(
 185               \begin{array}{cccccccc}
 186                 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
 187
 188                 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\
 189
 190                 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\
 191
 192                 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
 193
 194                 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\
 195
 196                 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
 197
 198                 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
 199
 200                 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\
 201
 202               \end{array}            \right) $
 203           \end{center}
 204         \end{scriptsize}
 205       \end{minipage}
 206     }%
 207     \caption{Représentations de $f^*(x_1,x_2,x_3)=
 208       (x_2 \oplus x_3, \overline{x_1}\overline{x_3} + x_1\overline{x_2},
 209       \overline{x_1}\overline{x_3} + x_1x_2)$.}\label{fig1}
 210   \end{center}
 211 \end{figure}
 212
 213
 214
 215
 216 \section{Graphes
 217   $\textsc{giu}(f)$
 218   $\textsc{gig}(f)$
 219   fortement connexes et doublement stochastiques}
 220 % Secrypt 14
 221
 222
 223
 224
 225 \subsection{Suppression des cycles hamiltoniens}
 226 \label{sec:hamiltonian}
 227
 228 Dans un premier temps, nous montrons en section~\ref{sub:removing:theory} que la
 229 suppression  d'un  cycle  hamiltonien   produit  bien  des  matrices  doublement
 230 stochastiques.   Nous  établissons  ensuite  le  lien avec  les  codes  de  Gray
 231 équilibrés.
 232
 233 \subsubsection{Aspects théoriques}
 234 \label{sub:removing:theory}
 235
 236 Nous donnons  deux résultats complémentaires, reliant la  suppression d'un cycle
 237 hamiltonien  du $n$-cube,  les matrices  doublement stochastiques  et  la forte
 238 connexité du graphe d'itérations.
 239
 240 \begin{theorem}\label{th:supprCH}
 241   La suppression d'un cycle hamiltonien dans une matrice de Markov $M$, issue du
 242   $n$-cube, produit une matrice doublement stochastique.
 243 \end{theorem}
 244 \begin{Proof}
 245
 246 Un cycle hamiltonien passe par chaque n{\oe}ud une et une seule fois.
 247 Pour chaque n{\oe}ud $v$ dans le $n$-cube $C_1$,
 248 une arête entrante $(o,v)$ et une arête sortante $(v,e)$
 249 est ainsi enlevée.
 250 Considérons un autre  $n$-cube $C_2$ auquel on ajoute les arêtes
 251 pour le rendre complet. La matrice de Markov $M$ correspondante est
 252 remplie de $\frac{1}{2^n}$ et est doublement stochastique.
 253 Comme on enlève exactement une arête sortante $(v,e)$
 254 à chaque n{\oe}ud $v$ dans $C_1$, on enlève ainsi dans
 255 $C_2$ les $2^{n-1}$ arêtes issues de $v$ et
 256 relatives aux parties de $\{1,\ldots,n\}$ qui
 257 contiennent $e$. Cela revient à annuler
 258 dans la matrice $M$ les $2^{n-1}$ coefficients correspondants et ajouter
 259 $1/2$ à l'élément $M_{vv}$.
 260 La matrice $M$ reste stochastique.
 261 On effectue un raisonnement similaire pour les arêtes entrantes:
 262 comme on enlève exactement une arête entrante $(o,v)$ pour chaque
 263 n{\oe}ud $v$ dans $C_1$, dans $C_2$, ce sont exactement
 264 $2^{n-1}$ arêtes menant à $v$ qui sont enlevées.
 265 Dans $M$ les $2^{n-1}$ coefficients correspondants sont mis à 0 et
 266 $M_{vv}$ vaut alors $\frac{2^{n-1} +1}{2}$.
 267 $M$ est donc doublement stochastique.
 268 \end{Proof}
 269
 270
 271
 272 \begin{theorem}\label{th:grapheFC}
 273   Le  graphe d'itérations  issu du  $n$-cube,  auquel un  cycle hamiltonien  est
 274   enlevé, est fortement connexe.
 275 \end{theorem}
 276
 277
 278 \begin{Proof}
 279 On considère les deux $n$-cubes $C_1$ et $C_2$ définis
 280 dans la preuve du théorème~\ref{th:supprCH}.
 281 Dans $C_1$ on considère le cycle inverse $r$ du cycle
 282 hamiltonien $c$.
 283 Aucun arc n'appartient à la fois  à $r$ et à $c$:
 284 en effet, sinon $c$ contiendrait un n{\oe}ud deux fois.
 285 Ainsi aucune arête de $r$ n'est enlevée dans $C_1$.
 286 Le cycle $r$ est évidement un cycle hamiltonien et contient tous les n{\oe}uds.
 287 Tous les n{\oe}uds de $C_1$ dans lequel $c$ a été enlevé sont accessibles
 288 depuis n'importe quel n{\oe}ud. Le graphe des itérations $\textsf{giu}$ qui
 289 étend le précédent graphe est ainsi fortement connexe.
 290
 291 \end{Proof}
 292
 293
 294
 295 Les preuves, relativement directes, sont  laissées en exercices au lecteur.  Par
 296 contre, ce qui  est moins aisé est la génération de  cycles hamiltoniens dans le
 297 $n$-cube,  ce qui  revient à  trouver des  \emph{codes de  Gray  cycliques}.  On
 298 rappelle que  les codes de  Gray sont des  séquences de mots binaires  de taille
 299 fixe ($n$),  dont les éléments successifs ne  différent que par un  seul bit. Un
 300 code  de  Gray est  \emph{cyclique}  si  le premier  élément  et  le dernier  ne
 301 différent que par un seul bit.
 302
 303 \subsection{Lien avec les codes de Gray cycliques (totalement) équilibrés}
 304 \label{sub:gray}
 305
 306 La borne  inférieure du  nombre de codes  de Gray  ($\left(\frac{n*\log2}{e \log
 307     \log   n}\times(1  -  o(1))\right)^{2^n}$),   donnée  dans~\cite{Feder2009NTB},
 308 indique  une explosion combinatoire  pour notre  recherche.  Afin  de contourner
 309 cette  difficulté,  nous  nous   restreignons  aux  codes  induisant  un  graphe
 310 d'itérations $\textsf{giu}(f)$  \emph{uniforme}.  Cette uniformité se  traduit par des
 311 nombres d'arcs  équilibrés entre les  \emph{dimensions} du graphe,  la dimension
 312 $i$  correspondant aux  seules variations  du  bit $i$  (parmi les  $n$ bits  au
 313 total).   Cette  approche  revient  à  chercher  des  codes  de  Gray  cycliques
 314 \emph{équilibrés}.
 315
 316 Un code de Gray équilibré peut être défini de la façon suivante :
 317
 318 \begin{Def}[Code de Gray cyclique équilibré]\label{def:grayequ}
 319   Soit $L = w_1,  w_2, \dots, w_{2^n}$ la séquence d'un code  de Gray cyclique à
 320   $n$ bits.  Soit $S = s_1,  s_2, \dots, s_{2^n}$ la séquence des transitions où
 321   $s_i$, $1  \le i \le 2^n$  est l'indice du seul  bit qui varie  entre les mots
 322   $w_i$ et  $w_{i+1}$. Enfin, soit  $\textit{NT}_n : \{1,\dots,  n\} \rightarrow
 323   \{0, \ldots, 2^n\}$  la fonction qui au paramètre  $i$ associe le \emph{nombre
 324     de transitions} présentes dans la séquence $L$ pour le bit $i$, c'est-à-dire
 325   le nombre d'occurrences de $i$ dans $S$.
 326
 327   Le      code       $L$      est      \textbf{équilibré}       si      $\forall
 328   i,j\in\{1,...,n\},~|\textit{NT}_n(i)  -  \textit{NT}_n(j)|  \le  2$.   Il  est
 329   \textbf{totalement             équilibré}             si             $\forall
 330   i\in\{1,...,n\},~\textit{NT}_n(i)=\frac{2^n}{n}$.
 331 \end{Def}
 332
 333 On peut  donc déjà déduire  qu'il ne peut  exister des codes de  Gray totalement
 334 équilibrés que  pour les  systèmes ayant un  nombre d'éléments $n=2^k,  k>0$. De
 335 plus,  comme  dans tout  code  de  Gray  cyclique, $\textit{NT}_n(i)$  est  pair
 336 $\forall  i\in\{1,...,n\}$,  alors  les  systèmes  ayant  un  nombre  d'éléments
 337 différent  de $2^k$,  ne peuvent  avoir  que des  codes de  Gray équilibrés  avec
 338 $\textit{NT}_n(i)=\lfloor\frac{2^n}{n}\rfloor$                                 ou
 339 $\textit{NT}_n(i)=\lceil\frac{2^n}{n}\rceil,    \forall    i\in\{1,...,n\}$   et
 340 vérifiant $\sum_{i=1}^nNT_n(i) = 2^n$.
 341
 342 \begin{xpl}
 343   Soit  $L^*=000,100,101,001,011,111,110,010$ le code  de Gray  correspondant au
 344   cycle hamiltonien enlevé de $f^*$.  Sa séquence des transitions est \linebreak
 345   $S=3,1,3,2,3,1,3,2$  et  les nombres  de  transitions sont  $\textit{TC}_3(1)=
 346   \textit{TC}_3(2)=2$ et $\textit{TC}_3(3)=4$. Un tel code est équilibré.
 347
 348   Si l'on  considère maintenant $L^4=$ 0000,  0010, 0110, 1110, 1111,  0111, 0011,
 349   0001,  0101, 0100,  1100, 1101,  1001,  1011, 1010,  1000,  un  code de  Gray
 350   cyclique. En construisant la séquence $S=$ 2,3,4,1,4,3,2,3,1,4,1,3,2,1,2,4,
 351   on constate que  $\forall
 352   i\in\{1,..,4\},~\textit{TC}_4(i)=4$ et donc que
 353   ce code est totalement équilibré.
 354 \end{xpl}
 355
 356 \subsection{Génération de codes de Gray équilibrés par induction}
 357 \label{sec:induction}
 358
 359 Dans  leur  article de  2004~\cite{ZanSup04},  Zanten  et  Suparta proposent  un
 360 algorithme inductif  pour générer  des codes  de Gray équilibrés  de $n$  bits à
 361 partir   de  codes   de  $n-2$   bits.   Cependant,   leur  méthode   n'est  pas
 362 constructive. En effet, elle effectue  des manipulations sur un partitionnement du
 363 code de Gray  initial de $n-2$ bits pour  obtenir un code de Gray  sur $n$ bits,
 364 mais le  résultat n'est pas  systématiquement équilibré. Il est  donc nécessaire
 365 d'évaluer les résultats obtenus à  partir de tous les partitionnements réalisables
 366 en suivant les  contraintes spécifiées.  Or, le nombre  de possibilités augmente
 367 exponentiellement (voir~\cite{Mons14} pour  l'évaluation détaillée), ce qui rend
 368 déraisonnable    tout   parcours    exhaustif.    Une    amélioration   proposée
 369 dans~\cite{Mons14} permet  de réduire le nombre  de partitionnements considérés,
 370 mais l'ordre  de grandeur  reste similaire. On  constate donc clairement  ici la
 371 nécessité de trouver  des algorithmes de génération de  codes de Gray équilibrés
 372 plus  efficaces.  Ce  problème  représente  une des  voies  que nous  souhaitons
 373 explorer dans la suite de nos travaux.
 374
 375 Le   tableau~\ref{table:nbFunc}  donne  le   nombre  de   fonctions  différentes
 376 compatibles avec les codes de  Gray équilibrés générés par l'approche précédente
 377 selon le nombre  de bits. Il donne  donc la taille de la  classe des générateurs
 378 pouvant être produits.  Les  cas 7 et 8 ne sont que  des bornes minimales basées
 379 sur des sous-ensembles des partitionnements possibles.
 380
 381 \begin{table}[ht]
 382   %\begin{center}
 383     \begin{tabular}{|l|c|c|c|c|c|}
 384       \hline
 385       $n$              & 4 & 5 & 6    & 7      & 8      \\
 386       \hline
 387       nb. de fonctions & 1 & 2 & 1332 & > 2300 & > 4500 \\
 388       \hline
 389     \end{tabular}
 390   %\end{center}
 391 \caption{Nombre de générateurs selon le nombre de bits.}\label{table:nbFunc}
 392 \end{table}
 393
 394
 395 \section{Quantifier l'écart par rapport à la distribution uniforme}
 396 %15 Rairo