X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/1042ddb8d08dc129da9358b73e723fc5014fb2c8..4cba8ffe29ea141685f705fba5aaeec1bb84f823:/14Secrypt.tex?ds=inline diff --git a/14Secrypt.tex b/14Secrypt.tex index 9de2b0d..a04c11e 100644 --- a/14Secrypt.tex +++ b/14Secrypt.tex @@ -13,17 +13,17 @@ graphe d'itérations, ce qui revient à supprimer en chaque n{\oe}ud de ce graph 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. +% 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 +Pour éviter d'avoir à gérer 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 @@ -37,16 +37,16 @@ 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}$: +\item pour chaque 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$, +\item pour chaque 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 +arithmétiques simples (sommes et produits). il pourrait théoriquement être +traité par des démarches de programmation 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 @@ -86,7 +86,7 @@ bistoc(X):- \caption{Code PROLOG permettant de trouver toutes les matrices DSSC pour $n=2$}\label{fig:prolog} \end{figure} -Enfin, on définit la relation $\mathcal{R}$, qui est établie pourles deux +Enfin, on définit la relation $\mathcal{R}$, qui est établie pour les deux fonctions $f$ et $g$ si leur graphes respectifs $\textsf{giu}(f)$ et $\textsf{giu}(g)$ sont isomorphes. @@ -105,10 +105,10 @@ 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. +en s'appuyant sur l'efficience 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 +comparé les fonctions non équivalentes selon leur proportion à engendrer des temps de mélange petits (cf. équation~\ref{eq:mt:ex}). @@ -395,17 +395,17 @@ sur des sous-ensembles des partitionnements possibles. Ces fonctions étant générée, on s'intéresse à étudier à quelle vitesse un générateur les embarquant converge vers la distribution uniforme. -C'est l'objeftif de la section suivante. +C'est l'objectif de la section suivante. \section{Quantifier l'écart par rapport à la distribution uniforme} On considère ici une fonction construite comme à la section précédente. On s'intéresse ici à étudier de manière théorique les -itérations définies à l'equation~(\ref{eq:asyn}) pour une +itérations définies à l'équation~(\ref{eq:asyn}) pour une stratégie donnée. -Tout d'abord, celles-ci peuvent être inerprétées comme une marche le long d'un +Tout d'abord, celles-ci peuvent être interprétées comme une marche le long d'un graphe d'itérations $\textsc{giu}(f)$ tel que le choix de tel ou tel arc est donné par la stratégie. -On remaque que ce graphe d'itération est toujours un sous graphe +On remarque que ce graphe d'itération est toujours un sous graphe du ${\mathsf{N}}$-cube augmenté des boucles sur chaque sommet, \textit{i.e.}, les arcs $(v,v)$ pour chaque $v \in \Bool^{\mathsf{N}}$. @@ -416,7 +416,7 @@ Ceci se base sur la théorie des chaînes de Markov. Pour une référence générale à ce sujet on pourra se référer au livre~\cite{LevinPeresWilmer2006}, -particulièrementau chapitre sur les temps d'arrêt. +particulièrement au chapitre sur les temps d'arrêt. @@ -433,7 +433,7 @@ p(e) \left\{ \end{array} \right. $$ -La matrice $P$ de la chaine de Markov associée à $f^*$ +La matrice $P$ de la chaîne de Markov associée à $f^*$ est \[ P=\dfrac{1}{6} \left( @@ -465,7 +465,7 @@ De plus, si $\nu$ est une distribution on $\Bool^{\mathsf{N}}$, on a $$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}.$$ -Soit $P$ une matrice d'une chaîne de Markovs sur $\Bool^{\mathsf{N}}$. +Soit $P$ une matrice d'une chaîne de Markov sur $\Bool^{\mathsf{N}}$. $P(X,\cdot)$ est la distribution induite par la $X^{\textrm{ème}}$ colonne de $P$. Si la chaîne de Markov induite par @@ -500,7 +500,7 @@ $f(X_{t-1},Z_t)$ une représentation fonctionnelle de celle-ci. Un \emph{temps d'arrêt aléatoire} pour la chaîne de Markov est un temps d'arrêt pour $(Z_t)_{t\in\mathbb{N}}$. -Si la chaîne de Markov est irreductible et a $\pi$ +Si la chaîne de Markov est irréductible et a $\pi$ comme distribution stationnaire, alors un \emph{temps stationnaire} $\tau$ est temps d'arrêt aléatoire (qui peut dépendre de la configuration initiale $X$), @@ -527,4 +527,44 @@ $E[\ts]\leq 8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1)$. Sans entrer dans les détails de la preuve, on remarque que le calcul de cette borne ne tient pas en compte le fait qu'on préfère enlever des chemins hamiltoniens équilibrés. -En intégrant cette contrainte, la borne supérieure pourraît être réduite. +En intégrant cette contrainte, la borne supérieure pourrait être réduite. + +\section{Et les itérations généralisées?} +Le chaptire précédent a présenté un algorithme de +PRNG construit à partir d'itérations unaires. +On pourrait penser que cet algorithme est peu efficace puisqu'il +dispose d'une fonction $f$ de $\Bool^n$ dans lui même mais il ne modifie à +chaque itération qu'un seul élément de $[n]$. +On pourrait penser à un algorithme basé sur les itérations généralisées, +c'est-à-dire qui modifierait une partie des éléments de $[n]$ à chaque +itération. +C'est l'algorithme~\ref{CI Algorithm:prng:g}. + +\begin{algorithm}[h] +%\begin{scriptsize} +\KwIn{une fonction $f$, un nombre d'itérations $b$, +une configuration initiale $x^0$ ($n$ bits)} +\KwOut{une configuration $x$ ($n$ bits)} +$x\leftarrow x^0$\; +$k\leftarrow b $\; +\For{$i=1,\dots,k$} +{ +$s\leftarrow{\textit{Set}(\textit{Random}(2^n))}$\; +$x\leftarrow{F_{f_g}(s,x)}$\; +} +return $x$\; +%\end{scriptsize} +\caption{PRNG basé sur les itérations généralisées.} +\label{CI Algorithm:prng:g} +\end{algorithm} + +Par rapport à l'algorithme~\ref{CI Algorithm} seule +la ligne $s\leftarrow{\textit{Set}(\textit{Random}(2^n))}$ est différente. +Dans celle-ci la fonction $\textit{Set} : \{1,\ldots,2^n\} \rightarrow +\mathcal{P}(\{1,\ldots n\})$ retourne l'ensemble dont la fonction +caractéristique serait représentée par le nombre donné en argument. +Par exemple, pour $n=3$, l'ensemble $\textit{Set}(6)$ vaudraitt $\{3,2\}$. +On remarque aussi que l'argument de la fonction $\textit{Random}$ +passe de $n$ à $2^n$. + +