From 6c27bb49e2e78479b953e969b4e6b4a84a63b8a9 Mon Sep 17 00:00:00 2001 From: couchot Date: Tue, 1 Sep 2015 19:12:14 +0200 Subject: [PATCH] =?utf8?q?o=C3=B9?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- 14Secrypt.tex | 132 +++++++++++++++++++++++++++++--------------------- 1 file changed, 77 insertions(+), 55 deletions(-) diff --git a/14Secrypt.tex b/14Secrypt.tex index 0465fcf..ede1dc6 100644 --- a/14Secrypt.tex +++ b/14Secrypt.tex @@ -21,7 +21,7 @@ arête sortante et une arête entrante. % 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} +\section{Programmation logique par contraintes sur des domaines finis}\label{sec:plc} Tout d'abord, soit ${\mathsf{N}}$ le nombre d'éléments. 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 @@ -94,7 +94,7 @@ C'est évidemment une relation d'équivalence. -\subsection{Analyse de l'approche}\label{sub:prng:ana} +%\subsection{Analyse de l'approche}\label{sub:prng:ana} Exécutée sur un ordinateur personnelle, PROLOG trouve en moins d'une seconde les 49 solutions pour $n=2$, @@ -235,25 +235,27 @@ M=\dfrac{1}{3} \left( -\section{Graphes - $\textsc{giu}(f)$ - $\textsc{gig}(f)$ - fortement connexes et doublement stochastiques}\label{sec:gen:dblstc} -% Secrypt 14 +% section{Graphes +% $\textsc{giu}(f)$ +% $\textsc{gig}(f)$ +% fortement connexes et doublement stochastiques}\label{sec:gen:dblstc} +% % +%Secrypt 14 -\subsection{Suppression des cycles hamiltoniens} +\section{Suppression des cycles hamiltoniens} \label{sec:hamiltonian} -Dans un premier temps, nous montrons en section~\ref{sub:removing:theory} que la +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} +%\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 @@ -322,7 +324,7 @@ fixe ($n$), dont les éléments successifs ne différent que par un seul bit. 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} +\section{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 @@ -375,7 +377,7 @@ vérifiant $\sum_{i=1}^nNT_n(i) = 2^n$. ce code est totalement équilibré. \end{xpl} -\subsection{Génération de codes de Gray équilibrés par induction} +\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 @@ -572,7 +574,7 @@ 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}. +C'est l'algorithme~\ref{CI Algorithm:prng:g} donné ci-après. \begin{algorithm}[h] %\begin{scriptsize} @@ -610,10 +612,10 @@ généralisées. correspondante à ce graphe et $M$ une matrice $2^n\times 2^n$ définie par - $M = \dfrac{1}{n} \check{M}$. + $M = \dfrac{1}{2^n} \check{M}$. Si $\textsc{gig}(f)$ est fortement connexe, alors la sortie du générateur de nombres pseudo aléatoires détaillé par - l'algorithme~\ref{CI Algorithm} suit une loi qui + l'algorithme~\ref{CI Algorithm:prng:g} suit une loi qui tend vers la distribution uniforme si et seulement si $M$ est une matrice doublement stochastique. \end{theorem} @@ -623,8 +625,8 @@ Elle n'est donc pas rappelée. \begin{xpl} - On reprend l'exemple donné à la section~\ref{sub:prng:ana}: - Dans le $3$-cube cycle hamiltonien défini par la séquence + On reprend l'exemple donné à la section~\ref{sec:plc}. + Dans le $3$-cube, le cycle hamiltonien défini par la séquence $000,100,101,001,011,111,110,010,000$ a été supprimé engendrant la fonction $f^*$ définie par $$f^*(x_1,x_2,x_3)= @@ -639,15 +641,15 @@ la figure~\ref{fig:markov:f*}. \begin{figure}[ht] \begin{center} - \subfigure[Graphe des itérations chaotiques de $f^*$. + \subfigure[Graphe $\textsc{gig}(f^*)$ \label{fig:iteration:f*}]{ \begin{minipage}{0.55\linewidth} \centering \includegraphics[width=\columnwidth]{images/iter_f}% \end{minipage} }% - \subfigure[Matrice de Markov du graphe d'itérations chaotiques de - $f^*$\label{fig:markov:f*}]{% + \subfigure[Matrice de Markov associée au $\textsc{gig}(f^*)$ + \label{fig:markov:f*}]{% \begin{minipage}{0.35\linewidth} \begin{scriptsize} \begin{center} @@ -675,15 +677,15 @@ la figure~\ref{fig:markov:f*}. \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} + (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} \end{xpl} -\begin{table}[table:functions]{Fonctions avec matrices DSCC et le plus faible temps de mélange.} +\begin{table} \begin{center} \begin{scriptsize} \begin{tabular}{|c|l|c|c|} @@ -733,14 +735,16 @@ la figure~\ref{fig:markov:f*}. \end{tabular} \end{scriptsize} \end{center} +\label{table:functions} +\caption{Fonctions avec matrices DSCC et le plus faible temps de mélange.} \end{table} Le tableau~\ref{table:functions} reprend une synthèse de fonctions qui ont été générées selon la méthode détaillée -à la section~\ref{sec:gen:dblstc}. -Pour chaque nombre $n=3$, $4$, $5$ -,$6$, tous les cycles hamiltoniens non isomorphes ont été générés. Pour les -valeur de $n=7$ et $8$, seules $10^{5}$ configurations ont été évaluées. Parmi +à la section~\ref{sec:hamiltonian}. +Pour chaque nombre $n=3$, $4$, $5$ et $6$, +tous les cycles hamiltoniens non isomorphes ont été générés. Pour les +valeur de $n=7$ et $8$, seules $10^{5}$ cycles ont été évalués. Parmi toutes les fonctions obtenues en enlevant du $n$-cube ces cycles, n'ont été retenues que celles qui minimisaient le temps de mélange relatif à une valeur de $\epsilon$ fixée à $10^{-8}$. @@ -757,39 +761,42 @@ le nombre d'éléments alors qu'il augmente dans l'approche initiale où l'on marche. Cela s'explique assez simplement. Depuis une configuration initiale, le nombre -de configurations qu'on ne peut pas atteindre en une itération est de +de configurations qu'on ne peut pas atteindre en une itération est de: \begin{itemize} -\item $2^n-n$ en marchant, ce qui représente $\dfrac{2^n-n}{2^n} = 1-\dfrac{n}{2^n}$ +\item $2^n-n$ en unaire. Ceci représente un rapport de + $\dfrac{2^n-n}{2^n} = 1-\dfrac{n}{2^n}$ de toutes les configurations; plus $n$ est grand, plus ce nombre est proche de $1$, et plus grand devient le nombre - d'itérations suffisantes pour atteinte une déviation faible; -\item $2^n-2^{n-1}$ en sautant, soit la moitié de toutes les configurations + d'itérations nécessaires pour atteinte une déviation faible; +\item $2^n-2^{n-1}$ dans le cas généralisé, + soit la moitié de toutes les configurations quel que soit $n$; seul 1 bit reste constant tandis que tous les autres peuvent changer. Plus $n$ grandit, plus la proportion de bits constants diminue. \end{itemize} -Cependant, dans le cas où l'on saute, chaque itération a une complexité -plus élevée puisqu'il est nécessaire d'invoquer un générateur -de nombres pseudo-aléatoires entre 1 et $2^{n}$ tandis qu'il suffit -d'avoir un générateur entre 1 et $n$ dans le premier cas. - -Pour comparer les deux approches, on considère que le générateur aléatoire embarqué est binaire, \textit{i.e.} ne génère qu'un bit (0 ou 1). +Cependant, dans le cas généralisé, chaque itération a une complexité +plus élevée puisqu'il est nécessaire d'invoquer un générateur +produisant un nombre pseudo-aléatoire dans $[2^{n}]$ tandis qu'il suffit +que celui-ci soit dans $[n]$ dans le cas unaire. +Pour comparer les deux approches, +on considère que le générateur aléatoire embarqué est binaire, \textit{i.e.} ne génère qu'un bit (0 ou 1). -Lorsqu'on marche et qu'on effectue $i$ itérations, -à chaque itération, la stratégie génère un nombre entre -$1$ et $n$. -Elle fait donc $\ln(n)/\ln(2)$ appels à ce générateur en moyenne. -La démarche fait donc au total $i*\ln(n)/\ln(2)$ appels pour $n$ bits et -donc $i*\ln(n)/(n*\ln(2))$ appels pour 1 bit généré en moyenne. -Lorsqu'on saute et qu'on effectue $i'$ itérations, -à chaque itération, la stratégie génère un nombre entre +Dans le cas généralisé, si l'on effectue $b$ itérations, +à chacune d'elles, la stratégie génère un nombre entre $1$ et $2^n$. Elle fait donc $n$ appels à ce générateur. -On fait donc au total $i'*n$ appels pour $n$ bits et -donc $i'$ appels pour 1 bit généré en moyenne. +On fait donc au total $b*n$ appels pour $n$ bits et +donc $b$ appels pour 1 bit généré en moyenne. +Dans le cas unaire, si l'on effectue $b'$ itérations, +à chacune d'elle, la stratégie génère un nombre entre +$1$ et $n$. +Elle fait donc $\ln(n)/\ln(2)$ appels à ce générateur binaire en moyenne. +La démarche fait donc au total $b'*\ln(n)/\ln(2)$ appels pour $n$ bits et +donc $b'*\ln(n)/(n*\ln(2))$ appels pour 1 bit généré en moyenne. Le tableau~\ref{table:marchevssaute} donne des instances de ces valeurs pour $n \in\{4,5,6,7,8\}$ et les fonctions -données au tableau~\ref{table:fonctions}. -On constate que le nombre d'appels par bit généré décroit avec $n$ dans la -seconde démarche et est toujours plus faible que celui de la première. +données au tableau~\ref{table:functions}. +On constate que le nombre d'appels par bit généré décroit avec $n$ dans le +cas des itérations généralisées et est toujours plus faible +que celui des itérations unaires. @@ -812,25 +819,38 @@ $$ -La qualité des séquences aléatoires a été évaluée à travers la suite -de tests statistiques développée pour les générateurs de nombres -pseudo-aléatoires par le +\section{Tests statistiques} + +La qualité des séquences aléatoires produites par +le générateur des itérations unaires ainsi que +celles issues des itérations généralisées a été évaluée à travers la suite +de tests statistiques développée par le \emph{National Institute of Standards and Technology} (NIST). Pour les 15 tests, le seuil $\alpha$ est fixé à $1\%$: une valeur qui est plus grande que $1\%$ signifie que la chaîne est considérée comme aléatoire avec une confiance de $99\%$. + + + + Le tableau~\ref{fig:TEST} donne une vision synthétique de toutes les expérimentations. + + + L'expérience a montré notamment que toutes ces fonctions passent avec succès cette batterie de tests. + + + %%%%%%%%% Relancer pour n=6, n=7, n=8 %%%%%%%%% Recalculer le MT %%%%%%%%% Regenerer les 10^6 bits %%%%%%%%% Evaluer sur NIST -\begin{table}[fig:TEST]{Test de NIST réalisé sur les fonctions $f^*$ détaillées au tableau~\label{table:functions}.} +\begin{table} \centering \begin{scriptsize} \begin{tabular}{|*{5}{c|}} @@ -853,6 +873,8 @@ Série* (m=10) & 0.595 (0.995) & 0.289 (0.975) & 0.660 (0.995) & Complexité linaire & 0.816 (1.0) & 0.897 (0.98) & 0.080 (0.98) & 0.798 (1.0) \\ \hline \end{tabular} \end{scriptsize} +\label{fig:TEST} +\caption{Test de NIST réalisé sur les fonctions $f^*$ détaillées au tableau~\label{table:functions}.} \end{table} % -- 2.39.5