From: couchot Date: Sat, 14 Mar 2015 15:38:31 +0000 (+0100) Subject: ajout du début des expériementations X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/rairo15.git/commitdiff_plain/9fc003099dc86caaa2ccf0645be2764c81418534?ds=sidebyside;hp=2644c7bc8564e7829d6f0d9b2e2a66e6460aec67 ajout du début des expériementations --- diff --git a/main.tex b/main.tex index 92832e5..3072c78 100644 --- a/main.tex +++ b/main.tex @@ -137,7 +137,7 @@ the classical statsitcal tests. \section{Experiments}\label{sec:prng} \input{prng} -\JFC{ajouter ici les expérimentations} + \section{Conclusion} diff --git a/prng.tex b/prng.tex index 45fcfcd..0667cca 100644 --- a/prng.tex +++ b/prng.tex @@ -52,3 +52,182 @@ only adds propbability constraints on existing edges, it preserves this property. +For each number $\mathsf{N}=4,5,6,7,8$ of bits, we have generated +the functions according the method +given in Sect.~\ref{sec:SCCfunc} . +For each $\mathsf{N}$, we have then restricted this evaluation to the function +whose Markov Matrix (issued from Eq.~(\ref{eq:Markov:rairo})) +has the smallest practical mixing time. +Such functions are +given in Table~\ref{table:nc}. +In this table, let us consider for instance +the function $\textcircled{a}$ from $\Bool^4$ to $\Bool^4$ +defined by the following images : +$[13, 10, 9, 14, 3, 11, 1, 12, 15, 4, 7, 5, 2, 6, 0, 8]$. +In other words, the image of $3~(0011)$ by $\textcircled{a}$ is $14~(1110)$: +it is obtained as the binary value of the fourth element in +the second list (namely~14). + +In this table the column +which is labeled with $b$ (respectively by $E[\tau]$) +gives the practical mixing time +where the deviation to the standard distribution is less than $10^{-6}$ +(resp. the theoretical upper bound ofstopping time as described in +Sect.~\ref{sec:hypercube}). + + + +\begin{table*}[t] +\begin{center} +\begin{scriptsize} +\begin{tabular}{|c|c|c|c|c|} +\hline +Function $f$ & $f(x)$, for $x$ in $(0,1,2,\hdots,2^n-1)$ & $\mathsf{N}$ & $b$ +&$E[\tau]$\\ +\hline +%%%%% n= 4 +$\textcircled{a}$&[13,10,9,14,3,11,1,12,15,4,7,5,2,6,0,8]&4&64&\\ +\hline +%%%%% n= 5 +$\textcircled{b}$& +[29, 22, 25, 30, 19, 27, 24, 16, 21, 6, 5, 28, 23, 26, 1, 17, & 5 & 78 & \\ +& + 31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 7, 20, 11, 18, 0, 4] +&&&\\ +%%%%% n= 6 +\hline +& +[55, 60, 45, 44, 58, 62, 61, 48, 53, 50, 52, 36, 59, 34, 33, 49, +&&&\\ +& + 15, 42, 47, 46, 35, 10, 57, 56, 7, 54, 39, 37, 51, 2, 1, 40, 63, +&&&\\ +$\textcircled{c}$& + 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, 16, 24, 13, +&6&88&\\ +& +12, 29, 8, 43, 14, 41, 0, 5, 38, 4, 6, 11, 3, 9, 32] +&&&\\ +%%%%% n= 7 +\hline +& +[111, 94, 93, 116, 122, 90, 125, 88, 115, 126, 119, 84, 123, 98, +&&&\\ +& + 81, 120, 109, 106, 105, 110, 99, 107, 104, 72, 71, 118, 117, + &&&\\ +& +96, 103, 102, 113, 64, 79, 86, 95, 124, 83, 91, 121, 24, 85, 22, +&&&\\ +$\textcircled{d}$& +69, 20, 19, 114, 17, 112, 77, 76, 13, 108, 74, 10, 9, 73, 67, 66, +&7 & 99&\\ + +& + 101, 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, 87, 30, +&&&\\ +& +23, 4, 27, 2, 16, 80, 31, 78, 15, 14, 3, 11, 8, 12, 5, 70, 21, +&&&\\ +& +68, 7, 6, 65, 1] +&&&\\ + + +%%%%%n=8 +\hline +& +[223, 190, 249, 254, 187, 251, 233, 232, 183, 230, 247, 180, 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, +&&&\\ +$\textcircled{e}$& +8, 7, 198, 197, 4, 195, 2, 161, 160, 255, 124, 109, 108, 122, +&8&110&\\ +& + 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] +&&&\\ +\hline +\end{tabular} +\end{scriptsize} +\end{center} +\caption{Functions with DSCC Matrix and smallest MT\label{table:nc}} +\end{table*} + + + +Let us first discuss about results against the NIST test suite. +In our experiments, 100 sequences (s = 100) of 1,000,000 bits are generated and tested. +If the value $\mathbb{P}_T$ of any test is smaller than 0.0001, the sequences are considered to be not good enough +and the generator is unsuitable. Table~\ref{The passing rate} shows $\mathbb{P}_T$ of sequences based on discrete +chaotic iterations using different schemes. If there are at least two statistical values in a test, this test is +marked with an asterisk and the average value is computed to characterize the statistics. +We can see in Table \ref{The passing rate} that all the rates are greater than 97/100, \textit{i. e.}, all the generators pass the NIST test. + + +\begin{table} +\renewcommand{\arraystretch}{1.3} +\begin{center} +\begin{scriptsize} +\setlength{\tabcolsep}{2pt} + + +\end{scriptsize} +\end{center} +\caption{NIST SP 800-22 test results ($\mathbb{P}_T$)} +\label{The passing rate} +\end{table} + + diff --git a/stopping.tex b/stopping.tex index eec08aa..d3b4f4d 100644 --- a/stopping.tex +++ b/stopping.tex @@ -165,14 +165,16 @@ has been removed. We define the Markov matrix $P_h$ for each line $X$ and each column $Y$ as follows: -$$\left\{ +\begin{equation} +\left\{ \begin{array}{ll} P_h(X,X)=\frac{1}{2}+\frac{1}{2{\mathsf{N}}} & \\ P_h(X,Y)=0 & \textrm{if $(X,Y)\notin E_h$}\\ P_h(X,Y)=\frac{1}{2{\mathsf{N}}} & \textrm{if $X\neq Y$ and $(X,Y) \in E_h$} \end{array} \right. -$$ +\label{eq:Markov:rairo} +\end{equation} We denote by $\ov{h} : \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ the function such that for any $X \in \Bool^{\mathsf{N}} $,