X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/eb4e301626c295e21a63aa3eb3d42a76e1a90588..f4997f36924772119b653509ff5ae4e8aef4200a:/14Secrypt.tex diff --git a/14Secrypt.tex b/14Secrypt.tex index fd6cbaf..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?} @@ -713,48 +799,44 @@ la figure~\ref{fig:markov:f*}. & & 40, 63, 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, & & \\ & & 16, 24, 13, 12, 29, 8, 10, 42, 41, 0, 5, 2, 4, 6, 11, 34, 9, 32] & & \\ \hline - - - - - - - &$f^{*7}$ & [111, 94, 93, 116, 122, 114, 125, 88, 87, 126, 119, 84, 123, & 10 & 63 \\ - & & 98, 81, 120, 109, 106, 105, 110, 99, 107, 104, 108, 101, 70, & & \\ - & & 117, 96, 67, 102, 113, 64, 79, 30, 95, 124, 83, 91, 121, 24, & & \\ - & & 23, 118, 69, 20, 115, 90, 17, 112, 77, 14, 73, 78, 74, 10, 72, & & \\ - & & 76, 103, 6, 71, 100, 75, 82, 97, 0, 127, 54, 57, 62, 51, 59, & & \\ - & & 56, 48, 53, 38, 37, 60, 55, 58, 33, 49, 63, 44, 47, 40, 42, & & \\ - & & 46, 45, 41, 35, 34, 39, 52, 43, 50, 32, 36, 29, 28, 61, 92, & & \\ - & & 26, 18, 89, 25, 19, 86, 85, 4, 27, 2, 16, 80, 31, 12, 15, 8, & & \\ - & & 3, 11, 13, 9, 5, 22, 21, 68, 7, 66, 65, 1] & & \\ + \multirow{9}{0.5cm}{7} &$f^{*7}$ & [111, 94, 93, 116, 122, 114, 125, 88, 115, 126, 85, 84, 123, & \multirow{9}{0.5cm}{\textbf{10}} & \multirow{9}{0.5cm}{\textbf{63}} \\ + & & 98, 81, 120, 109, 78, 105, 110, 99, 107, 104, 108, 101, 118, & & \\ + & & 117, 96, 103, 66, 113, 64, 79, 86, 95, 124, 83, 91, 121, 24, & & \\ + & & 119, 22, 69, 20, 87, 18, 17, 112, 77, 76, 73, 12, 74, 106, 72, & & \\ + & & 8, 7, 102, 71, 100, 75, 82, 97, 0, 127, 54, 57, 62, 51, 59, & & \\ + & & 56, 48, 53, 38, 37, 60, 55, 58, 33, 49, 63, 44, 47, 40, 42, & & \\ + & & 46, 45, 41, 35, 34, 39, 52, 43, 50, 32, 36, 29, 28, 61, 92, & & \\ + & & 26, 90, 89, 25, 19, 30, 23, 4, 27, 2, 16, 80, 31, 10, 15, 14, & & \\ + & & 3, 11, 13, 9, 5, 70, 21, 68, 67, 6, 65, 1] & & \\ \hline - & $f^{*8}$ &[223, 190, 249, 254, 187, 251, 233, 232, 183, 230, 247, 180,& 9 & 72 \\ - & & 227, 178, 240, 248, 237, 236, 253, 172, 203, 170, 201, 168, &&\\ - & & 229, 166, 165, 244, 163, 242, 241, 192, 215, 220, 205, 216, &&\\ - & & 218, 222, 221, 208, 213, 210, 212, 214, 219, 211, 217, 209, &&\\ - & & 239, 202, 207, 140, 139, 234, 193, 204, 135, 196, 199, 132, &&\\ - & & 194, 130, 225, 200, 159, 62, 185, 252, 59, 250, 169, 56, 191,&&\\ - & & 246, 245, 52, 243, 50, 176, 48, 173, 238, 189, 44, 235, 42, &&\\ - & & 137, 184, 231, 38, 37, 228, 35, 226, 177, 224, 151, 156, 141,&&\\ - & & 152, 154, 158, 157, 144, 149, 146, 148, 150, 155, 147, 153, &&\\ - & & 145, 175, 206, 143, 136, 11, 142, 129, 8, 7, 198, 197, 4, 195, &&\\ - & & 2, 161, 160, 255, 124, 109, 108, 122, 126, 125, 112, 117, 114, &&\\ - & & 116, 100, 123, 98, 97, 113, 79, 106, 111, 110, 99, 74, 121, 120,&&\\ - & & 71, 118, 103, 101, 115, 66, 65, 104, 127, 90, 89, 94, 83, 91, 81,&&\\ - & & 92, 95, 84, 87, 85, 82, 86, 80, 88, 77, 76, 93, 72, 107, 78, 105, &&\\ - & & 64, 69, 102, 68, 70, 75, 67, 73, 96, 55, 58, 45, 188, 51, 186, 61, &&\\ - & & 40, 119, 182, 181, 53, 179, 54, 33, 49, 15, 174, 47, 60, 171, && \\ - & & 46, 57, 32, 167, 6, 36, 164, 43, 162, 1, 0, 63, 26, 25, 30, 19,&&\\ - & & 27, 17, 28, 31, 20, 23, 21, 18, 22, 16, 24, 13, 10, 29, 14, 3, &&\\ - & &138, 41, 12, 39, 134, 133, 5, 131, 34, 9, 128]&&\\ + \multirow{20}{0.5cm}{8} & $f^{*8}$ & +[223, 190, 249, 254, 187, 251, 233, 232, 183, 230, 247, 180,& +\multirow{20}{0.5cm}{9}& +\multirow{20}{0.5cm}{71}\\ +& & 227, 178, 240, 248, 237, 236, 253, 172, 203, 170, 201, 168,& & \\ +& & 229, 166, 165, 244, 163, 242, 241, 192, 215, 220, 205, 216,& & \\ +& & 218, 222, 221, 208, 213, 210, 212, 214, 219, 211, 217, 209,& & \\ +& & 239, 202, 207, 140, 139, 234, 193, 204, 135, 196, 199, 132,& & \\ +& & 194, 130, 225, 200, 159, 62, 185, 252, 59, 250, 169, 56, 191,& & \\ +& & 246, 245, 52, 243, 50, 176, 48, 173, 238, 189, 44, 235, 42,& & \\ +& & 137, 184, 231, 38, 37, 228, 35, 226, 177, 224, 151, 156, 141,& & \\ +& & 152, 154, 158, 157, 144, 149, 146, 148, 150, 155, 147, 153,& & \\ +& & 145, 175, 206, 143, 12, 11, 142, 129, 128, 7, 198, 197, 4, 195,& & \\ +& & 2, 161, 160, 255, 124, 109, 108, 122, 126, 125, 112, 117, 114,& & \\ +& & 116, 100, 123, 98, 97, 113, 79, 106, 111, 110, 99, 74, 121,& & \\ +& & 120, 71, 118, 103, 101, 115, 66, 65, 104, 127, 90, 89, 94, 83,& & \\ +& & 91, 81, 92, 95, 84, 87, 85, 82, 86, 80, 88, 77, 76, 93, 72,& & \\ +& & 107, 78, 105, 64, 69, 102, 68, 70, 75, 67, 73, 96, 55, 58, 45,& & \\ +& & 188, 51, 186, 61, 40, 119, 182, 181, 53, 179, 54, 33, 49, 15,& & \\ +& & 174, 47, 60, 171, 46, 57, 32, 167, 6, 36, 164, 43, 162, 1, 0,& & \\ +& & 63, 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, 16,& & \\ +& & 24, 13, 10, 29, 14, 3, 138, 41, 136, 39, 134, 133, 5, 131,& & \\ +& & 34, 9, 8]&&\\ \hline \end{tabular} \end{scriptsize} \end{center} -\label{table:functions} -\caption{Fonctions avec matrices DSCC et le plus faible temps de mélange.} - +\caption{Fonctions avec matrices DSCC et le plus faible temps de mélange}\label{table:functions} \end{table} Le tableau~\ref{table:functions} reprend une synthèse de @@ -765,14 +847,19 @@ 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}$. +$\epsilon$ fixée à $10^{-8}$ et pour un mode donné. Ce nombre d'itérations (\textit{i.e.}, ce temps de mélange) est stocké dans la troisième colonne sous la variable $b$. La variable $b'$ reprend le temps de mélange pour -l'algorithme~\ref{CI Algorithm}. - -Un premier résultat est que ce nouvel algorithme réduit grandement le nombre +l'algorithme~\ref{CI Algorithm}. +On note que pour un nombre $n$ de bits fixé et un mode donné d'itérations, +il peut avoir plusieurs fonctions minimisant ce temps de mélange. De plus, comme ce temps +de mélange est construit à partir de la matrice de Markov et que celle-ci dépend +du mode, une fonction peut être optimale pour un mode et ne pas l'être pour l'autre +(c.f. pour $n=5$). + +Un second résultat est que ce nouvel algorithme réduit grandement le nombre d'itérations suffisant pour obtenir une faible déviation par rapport à une distribution uniforme. On constate de plus que ce nombre décroit avec le nombre d'éléments alors qu'il augmente dans l'approche initiale où @@ -824,9 +911,9 @@ $$ \hline \textrm{Itérations} & 4 & 5 & 6 & 7 & 8 \\ \hline -\textrm{Unaires} & 19.0 & 22.2905097109 & 23.6954895899 & 25.2661942985 & 27.0\\ +\textrm{Unaires} & 19.0 & 22.3 & 23.7 & 25.3 & 27.0\\ \hline -\textrm{Généralisées} & 17 & 13 & 11 & 10 & 9\\ +\textrm{Généralisées} & 17 & 13 & 11 & 10 & 9\\ \hline \end{array} $$ @@ -844,18 +931,33 @@ 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). +En interne, c'est l'implantation de l'algorithme de Mersenne Twister qui +permet de générer la stratégie aléatoire. + + + + 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 ces expérimentations. +Les tableau~\ref{fig:TEST:generalise} donnent +une vision synthétique de ces expérimentations. Nous avons évalué les fonctions préfixées par -$f$ (respecitvement $g$) avec le générateur issu des itérations +$f$ (respecitvement $g$) avec les générateurs issus des itérations généralisées (resp. unaires). -%L'expérience a montré notamment que toutes ces fonctions -%passent avec succès cette batterie de tests. +Quelle que soit la méthode utilisée, on constate que chacun des +générateurs passe +avec succes le test de NIST. + +Interpréter ces resultats en concluant que ces générateurs sont +tous équivalents serait erroné: la meilleur des +méthodes basées sur le mode des itérations +généralisées (pour $n=8$ par exemple) +est au moins deux fois plus rapide que la meilleur de celles qui +sont basées sur les itérations unaires. @@ -870,26 +972,104 @@ généralisées (resp. unaires). \begin{scriptsize} - +\begin{tabular}{|l|r|r|r|r|} + \hline +Test & $f^{*5}$ &$f^{*6}$ &$f^{*7}$ &$f^{*8}$ \\ \hline +Fréquence (Monobit)& 0.401 (0.97)& 0.924 (1.0)& 0.779 (0.98)& 0.883 (0.99)\\ \hline +Fréquence ds un bloc& 0.574 (0.98)& 0.062 (1.0)& 0.978 (0.98)& 0.964 (0.98)\\ \hline +Somme Cumulé*& 0.598 (0.975)& 0.812 (1.0)& 0.576 (0.99)& 0.637 (0.99)\\ \hline +Exécution& 0.998 (0.99)& 0.213 (0.98)& 0.816 (0.98)& 0.494 (1.0)\\ \hline +Longue exécution dans un bloc& 0.085 (0.99)& 0.971 (0.99)& 0.474 (1.0)& 0.574 (0.99)\\ \hline +Rang& 0.994 (0.96)& 0.779 (1.0)& 0.191 (0.99)& 0.883 (0.99)\\ \hline +Fourier rapide& 0.798 (1.0)& 0.595 (0.99)& 0.739 (0.99)& 0.595 (1.0)\\ \hline +Patron sans superposition*& 0.521 (0.987)& 0.494 (0.989)& 0.530 (0.990)& 0.520 (0.989)\\ \hline +Patron avec superposition& 0.066 (0.99)& 0.040 (0.99)& 0.304 (1.0)& 0.249 (0.98)\\ \hline +Statistiques universelles& 0.851 (0.99)& 0.911 (0.99)& 0.924 (0.96)& 0.066 (1.0)\\ \hline +Entropie approchée (m=10)& 0.637 (0.99)& 0.102 (0.99)& 0.115 (0.99)& 0.350 (0.98)\\ \hline +Suite aléatoire *& 0.573 (0.981)& 0.144 (0.989)& 0.422 (1.0)& 0.314 (0.984)\\ \hline +Suite aléatoire variante *& 0.359 (0.968)& 0.401 (0.982)& 0.378 (0.989)& 0.329 (0.985)\\ \hline +Série* (m=10)& 0.469 (0.98)& 0.475 (0.995)& 0.473 (0.985)& 0.651 (0.995)\\ \hline +Complexité linaire& 0.129 (1.0)& 0.494 (1.0)& 0.062 (1.0)& 0.739 (1.0)\\ \hline + +\end{tabular} \end{scriptsize} -\label{fig:TEST:generalise} + \caption{Test de NIST pour les fonctions - du tableau~\ref{table:functions} selon les itérations généralisées} + du tableau~\ref{table:functions} selon les itérations généralisées}\label{fig:TEST:generalise} \end{table} \begin{table}[ht] \centering \begin{scriptsize} +\begin{tabular}{|l|r|r|r|r|} +\hline +Test & $g^{*5}$& $g^{*6}$& $f^{*7}$& $f^{*8}$\\ \hline +Fréquence (Monobit)& 0.236 (1.0)& 0.867 (0.99)& 0.437 (0.99)& 0.911 (1.0)\\ \hline +Fréquence ds un bloc& 0.129 (0.98)& 0.350 (0.99)& 0.366 (0.96)& 0.657 (1.0)\\ \hline +Somme Cumulé*& 0.903 (0.995)& 0.931 (0.985)& 0.863 (0.995)& 0.851 (0.995)\\ \hline +Exécution& 0.699 (0.98)& 0.595 (0.99)& 0.181 (1.0)& 0.437 (0.99)\\ \hline +Longue exécution dans un bloc& 0.009 (0.99)& 0.474 (0.97)& 0.816 (1.0)& 0.051 (1.0)\\ \hline +Rang& 0.946 (0.96)& 0.637 (0.98)& 0.494 (1.0)& 0.946 (1.0)\\ \hline +Fourier rapide& 0.383 (0.99)& 0.437 (1.0)& 0.616 (0.98)& 0.924 (0.99)\\ \hline +Patron sans superposition*& 0.466 (0.990)& 0.540 (0.989)& 0.505 (0.990)& 0.529 (0.991)\\ \hline +Patron avec superposition& 0.202 (0.96)& 0.129 (0.98)& 0.851 (0.99)& 0.319 (0.98)\\ \hline +Statistiques universelles& 0.319 (0.97)& 0.534 (0.99)& 0.759 (1.0)& 0.657 (0.99)\\ \hline +Entropie approchée (m=10)& 0.075 (0.97)& 0.181 (0.99)& 0.213 (0.98)& 0.366 (0.98)\\ \hline +Suite aléatoire *& 0.357 (0.986)& 0.569 (0.991)& 0.539 (0.987)& 0.435 (0.992)\\ \hline +Suite aléatoire variante *& 0.398 (0.989)& 0.507 (0.986)& 0.668 (0.991)& 0.514 (0.994)\\ \hline +Série* (m=10)& 0.859 (0.995)& 0.768 (0.99)& 0.427 (0.995)& 0.637 (0.98)\\ \hline +Complexité linaire& 0.897 (0.99)& 0.366 (0.98)& 0.153 (1.0)& 0.437 (1.0)\\ \hline + +\end{tabular} +\end{scriptsize} + + +\caption{Test de NIST pour les fonctions + du tableau~\ref{table:functions} selon les itérations unaires}\label{fig:TEST:unaire} +\end{table} + + +\begin{table}[ht] + \centering + \begin{scriptsize} + +\begin{tabular}{|l|r|r|r|r|} + \hline +Test & 5 bits& 6 bits & 7 bits & 8bits \\ \hline +Fréquence (Monobit)& 0.289 (1.0)& 0.437 (1.0)& 0.678 (1.0)& 0.153 (0.99)\\ \hline +Fréquence ds un bloc& 0.419 (1.0)& 0.971 (0.98)& 0.419 (0.99)& 0.275 (1.0)\\ \hline +Somme Cumulé*& 0.607 (0.99)& 0.224 (0.995)& 0.645 (0.995)& 0.901 (0.99)\\ \hline +Exécution& 0.129 (0.99)& 0.005 (0.99)& 0.935 (0.98)& 0.699 (0.98)\\ \hline +Longue exécution dans un bloc& 0.514 (1.0)& 0.739 (0.99)& 0.994 (1.0)& 0.834 (0.99)\\ \hline +Rang& 0.455 (0.97)& 0.851 (0.99)& 0.554 (1.0)& 0.964 (0.99)\\ \hline +Fourier rapide& 0.096 (0.98)& 0.955 (0.99)& 0.851 (0.97)& 0.037 (1.0)\\ \hline +Patron sans superposition*& 0.534 (0.990)& 0.524 (0.990)& 0.508 (0.987)& 0.515 (0.99)\\ \hline +Patron avec superposition& 0.699 (0.99)& 0.616 (0.95)& 0.071 (1.0)& 0.058 (1.0)\\ \hline +Statistiques universelles& 0.062 (0.99)& 0.071 (1.0)& 0.637 (1.0)& 0.494 (0.98)\\ \hline +Entropie approchée (m=10)& 0.897 (0.99)& 0.383 (0.99)& 0.366 (1.0)& 0.911 (0.99)\\ \hline +Suite aléatoire *& 0.365 (0.983)& 0.442 (0.994)& 0.579 (0.992)& 0.296 (0.993)\\ \hline +Suite aléatoire variante *& 0.471 (0.978)& 0.559 (0.992)& 0.519 (0.987)& 0.340 (0.995)\\ \hline +Série* (m=10)& 0.447 (0.985)& 0.298 (0.995)& 0.648 (1.0)& 0.352 (0.995)\\ \hline +Complexité linaire& 0.005 (0.98)& 0.534 (0.99)& 0.085 (0.97)& 0.996 (1.0)\\ \hline + +\end{tabular} + + + + + + + \end{scriptsize} -\label{fig:TEST:unaire} -\caption{Test de NIST pour les fonctions - du tableau~\ref{table:functions} selon les itérations unaires} + +\caption{Test de NIST pour l'algorithme de Mersenne Twister}\label{fig:TEST:Mersenne} \end{table} + %