From fc073e86031fc91a73a2f1c436f91a697cb98668 Mon Sep 17 00:00:00 2001 From: cguyeux Date: Thu, 25 Oct 2012 10:08:08 +0200 Subject: [PATCH] Une section en moins, sniff --- prng_gpu.tex | 634 ++++++++++++++++++++++++++------------------------- 1 file changed, 318 insertions(+), 316 deletions(-) diff --git a/prng_gpu.tex b/prng_gpu.tex index b3a844a..085ce1e 100644 --- a/prng_gpu.tex +++ b/prng_gpu.tex @@ -968,329 +968,331 @@ have $d((S,E),(\tilde S,E))<\epsilon$. \end{proof} -\section{Statistical Improvements Using Chaotic Iterations} - -\label{The generation of pseudorandom sequence} - - -Let us now explain why we have reasonable ground to believe that chaos -can improve statistical properties. -We will show in this section that chaotic properties as defined in the -mathematical theory of chaos are related to some statistical tests that can be found -in the NIST battery. Furthermore, we will check that, when mixing defective PRNGs with -chaotic iterations, the new generator presents better statistical properties -(this section summarizes and extends the work of~\cite{bfg12a:ip}). - - - -\subsection{Qualitative relations between topological properties and statistical tests} - - -There are various relations between topological properties that describe an unpredictable behavior for a discrete -dynamical system on the one -hand, and statistical tests to check the randomness of a numerical sequence -on the other hand. These two mathematical disciplines follow a similar -objective in case of a recurrent sequence (to characterize an intrinsically complicated behavior for a -recurrent sequence), with two different but complementary approaches. -It is true that the following illustrative links give only qualitative arguments, -and proofs should be provided later to make such arguments irrefutable. However -they give a first understanding of the reason why we think that chaotic properties should tend -to improve the statistical quality of PRNGs. -% -Let us now list some of these relations between topological properties defined in the mathematical -theory of chaos and tests embedded into the NIST battery. %Such relations need to be further -%investigated, but they presently give a first illustration of a trend to search similar properties in the -%two following fields: mathematical chaos and statistics. - - -\begin{itemize} - \item \textbf{Regularity}. As stated in Section~\ref{subsec:Devaney}, a chaotic dynamical system must -have an element of regularity. Depending on the chosen definition of chaos, this element can be the existence of -a dense orbit, the density of periodic points, etc. The key idea is that a dynamical system with no periodicity -is not as chaotic as a system having periodic orbits: in the first situation, we can predict something and gain a -knowledge about the behavior of the system, that is, it never enters into a loop. A similar importance for periodicity is emphasized in -the two following NIST tests~\cite{Nist10}: - \begin{itemize} - \item \textbf{Non-overlapping Template Matching Test}. Detect generators that produce too many occurrences of a given non-periodic (aperiodic) pattern. - \item \textbf{Discrete Fourier Transform (Spectral) Test}. Detect periodic features (i.e., repetitive patterns that are close one to another) in the tested sequence that would indicate a deviation from the assumption of randomness. - \end{itemize} - -\item \textbf{Transitivity}. This topological property previously introduced states that the dynamical system is intrinsically complicated: it cannot be simplified into -two subsystems that do not interact, as we can find in any neighborhood of any point another point whose orbit visits the whole phase space. -This focus on the places visited by the orbits of the dynamical system takes various nonequivalent formulations in the mathematical theory -of chaos, namely: transitivity, strong transitivity, total transitivity, topological mixing, and so on~\cite{bg10:ij}. A similar attention -is brought on the states visited during a random walk in the two tests below~\cite{Nist10}: - \begin{itemize} - \item \textbf{Random Excursions Variant Test}. Detect deviations from the expected number of visits to various states in the random walk. - \item \textbf{Random Excursions Test}. Determine if the number of visits to a particular state within a cycle deviates from what one would expect for a random sequence. - \end{itemize} - -\item \textbf{Chaos according to Li and Yorke}. Two points of the phase space $(x,y)$ define a couple of Li-Yorke when $\limsup_{n \rightarrow +\infty} d(f^{(n)}(x), f^{(n)}(y))>0$ et $\liminf_{n \rightarrow +\infty} d(f^{(n)}(x), f^{(n)}(y))=0$, meaning that their orbits always oscillate as the iterations pass. When a system is compact and contains an uncountable set of such points, it is claimed as chaotic according -to Li-Yorke~\cite{Li75,Ruette2001}. A similar property is regarded in the following NIST test~\cite{Nist10}. - \begin{itemize} - \item \textbf{Runs Test}. To determine whether the number of runs of ones and zeros of various lengths is as expected for a random sequence. In particular, this test determines whether the oscillation between such zeros and ones is too fast or too slow. - \end{itemize} - \item \textbf{Topological entropy}. The desire to formulate an equivalency of the thermodynamics entropy -has emerged both in the topological and statistical fields. Once again, a similar objective has led to two different -rewritting of an entropy based disorder: the famous Shannon definition of entropy is approximated in the statistical approach, -whereas topological entropy is defined as follows: -$x,y \in \mathcal{X}$ are $\varepsilon-$\emph{separated in time $n$} if there exists $k \leqslant n$ such that $d\left(f^{(k)}(x),f^{(k)}(y)\right)>\varepsilon$. Then $(n,\varepsilon)-$separated sets are sets of points that are all $\varepsilon-$separated in time $n$, which -leads to the definition of $s_n(\varepsilon,Y)$, being the maximal cardinality of all $(n,\varepsilon)-$separated sets. Using these notations, -the topological entropy is defined as follows: $$h_{top}(\mathcal{X},f) = \displaystyle{\lim_{\varepsilon \rightarrow 0} \Big[ \limsup_{n \rightarrow +\infty} \dfrac{1}{n} \log s_n(\varepsilon,\mathcal{X})\Big]}.$$ -This value measures the average exponential growth of the number of distinguishable orbit segments. -In this sense, it measures the complexity of the topological dynamical system, whereas -the Shannon approach comes to mind when defining the following test~\cite{Nist10}: - \begin{itemize} -\item \textbf{Approximate Entropy Test}. Compare the frequency of the overlapping blocks of two consecutive/adjacent lengths ($m$ and $m+1$) against the expected result for a random sequence. - \end{itemize} - - \item \textbf{Non-linearity, complexity}. Finally, let us remark that non-linearity and complexity are -not only sought in general to obtain chaos, but they are also required for randomness, as illustrated by the two tests below~\cite{Nist10}. - \begin{itemize} -\item \textbf{Binary Matrix Rank Test}. Check for linear dependence among fixed length substrings of the original sequence. -\item \textbf{Linear Complexity Test}. Determine whether or not the sequence is complex enough to be considered random. - \end{itemize} -\end{itemize} - - -We have proven in our previous works~\cite{guyeux12:bc} that chaotic iterations satisfying Theorem~\ref{Th:Caractérisation des IC chaotiques} are, among other -things, strongly transitive, topologically mixing, chaotic as defined by Li and Yorke, -and that they have a topological entropy and an exponent of Lyapunov both equal to $ln(\mathsf{N})$, -where $\mathsf{N}$ is the size of the iterated vector. -These topological properties make that we are ground to believe that a generator based on chaotic -iterations will probably be able to pass all the existing statistical batteries for pseudorandomness like -the NIST one. The following subsections, in which we prove that defective generators have their -statistical properties improved by chaotic iterations, show that such an assumption is true. - -\subsection{Details of some Existing Generators} - -The list of defective PRNGs we will use -as inputs for the statistical tests to come is introduced here. - -Firstly, the simple linear congruency generators (LCGs) will be used. -They are defined by the following recurrence: -\begin{equation} -x^n = (ax^{n-1} + c)~mod~m, -\label{LCG} -\end{equation} -where $a$, $c$, and $x^0$ must be, among other things, non-negative and inferior to -$m$~\cite{LEcuyerS07}. In what follows, 2LCGs and 3LCGs refer to two (resp. three) -combinations of such LCGs. For further details, see~\cite{bfg12a:ip,combined_lcg}. +%\section{Statistical Improvements Using Chaotic Iterations} + +%\label{The generation of pseudorandom sequence} + + +%Let us now explain why we have reasonable ground to believe that chaos +%can improve statistical properties. +%We will show in this section that chaotic properties as defined in the +%mathematical theory of chaos are related to some statistical tests that can be found +%in the NIST battery. Furthermore, we will check that, when mixing defective PRNGs with +%chaotic iterations, the new generator presents better statistical properties +%(this section summarizes and extends the work of~\cite{bfg12a:ip}). + + + +%\subsection{Qualitative relations between topological properties and statistical tests} + + +%There are various relations between topological properties that describe an unpredictable behavior for a discrete +%dynamical system on the one +%hand, and statistical tests to check the randomness of a numerical sequence +%on the other hand. These two mathematical disciplines follow a similar +%objective in case of a recurrent sequence (to characterize an intrinsically complicated behavior for a +%recurrent sequence), with two different but complementary approaches. +%It is true that the following illustrative links give only qualitative arguments, +%and proofs should be provided later to make such arguments irrefutable. However +%they give a first understanding of the reason why we think that chaotic properties should tend +%to improve the statistical quality of PRNGs. +%% +%Let us now list some of these relations between topological properties defined in the mathematical +%theory of chaos and tests embedded into the NIST battery. %Such relations need to be further +%%investigated, but they presently give a first illustration of a trend to search similar properties in the +%%two following fields: mathematical chaos and statistics. + + +%\begin{itemize} +% \item \textbf{Regularity}. As stated in Section~\ref{subsec:Devaney}, a chaotic dynamical system must +%have an element of regularity. Depending on the chosen definition of chaos, this element can be the existence of +%a dense orbit, the density of periodic points, etc. The key idea is that a dynamical system with no periodicity +%is not as chaotic as a system having periodic orbits: in the first situation, we can predict something and gain a +%knowledge about the behavior of the system, that is, it never enters into a loop. A similar importance for periodicity is emphasized in +%the two following NIST tests~\cite{Nist10}: +% \begin{itemize} +% \item \textbf{Non-overlapping Template Matching Test}. Detect generators that produce too many occurrences of a given non-periodic (aperiodic) pattern. +% \item \textbf{Discrete Fourier Transform (Spectral) Test}. Detect periodic features (i.e., repetitive patterns that are close one to another) in the tested sequence that would indicate a deviation from the assumption of randomness. +% \end{itemize} + +%\item \textbf{Transitivity}. This topological property previously introduced states that the dynamical system is intrinsically complicated: it cannot be simplified into +%two subsystems that do not interact, as we can find in any neighborhood of any point another point whose orbit visits the whole phase space. +%This focus on the places visited by the orbits of the dynamical system takes various nonequivalent formulations in the mathematical theory +%of chaos, namely: transitivity, strong transitivity, total transitivity, topological mixing, and so on~\cite{bg10:ij}. A similar attention +%is brought on the states visited during a random walk in the two tests below~\cite{Nist10}: +% \begin{itemize} +% \item \textbf{Random Excursions Variant Test}. Detect deviations from the expected number of visits to various states in the random walk. +% \item \textbf{Random Excursions Test}. Determine if the number of visits to a particular state within a cycle deviates from what one would expect for a random sequence. +% \end{itemize} + +%\item \textbf{Chaos according to Li and Yorke}. Two points of the phase space $(x,y)$ define a couple of Li-Yorke when $\limsup_{n \rightarrow +\infty} d(f^{(n)}(x), f^{(n)}(y))>0$ et $\liminf_{n \rightarrow +\infty} d(f^{(n)}(x), f^{(n)}(y))=0$, meaning that their orbits always oscillate as the iterations pass. When a system is compact and contains an uncountable set of such points, it is claimed as chaotic according +%to Li-Yorke~\cite{Li75,Ruette2001}. A similar property is regarded in the following NIST test~\cite{Nist10}. +% \begin{itemize} +% \item \textbf{Runs Test}. To determine whether the number of runs of ones and zeros of various lengths is as expected for a random sequence. In particular, this test determines whether the oscillation between such zeros and ones is too fast or too slow. +% \end{itemize} +% \item \textbf{Topological entropy}. The desire to formulate an equivalency of the thermodynamics entropy +%has emerged both in the topological and statistical fields. Once again, a similar objective has led to two different +%rewritting of an entropy based disorder: the famous Shannon definition of entropy is approximated in the statistical approach, +%whereas topological entropy is defined as follows: +%$x,y \in \mathcal{X}$ are $\varepsilon-$\emph{separated in time $n$} if there exists $k \leqslant n$ such that $d\left(f^{(k)}(x),f^{(k)}(y)\right)>\varepsilon$. Then $(n,\varepsilon)-$separated sets are sets of points that are all $\varepsilon-$separated in time $n$, which +%leads to the definition of $s_n(\varepsilon,Y)$, being the maximal cardinality of all $(n,\varepsilon)-$separated sets. Using these notations, +%the topological entropy is defined as follows: $$h_{top}(\mathcal{X},f) = \displaystyle{\lim_{\varepsilon \rightarrow 0} \Big[ \limsup_{n \rightarrow +\infty} \dfrac{1}{n} \log s_n(\varepsilon,\mathcal{X})\Big]}.$$ +%This value measures the average exponential growth of the number of distinguishable orbit segments. +%In this sense, it measures the complexity of the topological dynamical system, whereas +%the Shannon approach comes to mind when defining the following test~\cite{Nist10}: +% \begin{itemize} +%\item \textbf{Approximate Entropy Test}. Compare the frequency of the overlapping blocks of two consecutive/adjacent lengths ($m$ and $m+1$) against the expected result for a random sequence. +% \end{itemize} + +% \item \textbf{Non-linearity, complexity}. Finally, let us remark that non-linearity and complexity are +%not only sought in general to obtain chaos, but they are also required for randomness, as illustrated by the two tests below~\cite{Nist10}. +% \begin{itemize} +%\item \textbf{Binary Matrix Rank Test}. Check for linear dependence among fixed length substrings of the original sequence. +%\item \textbf{Linear Complexity Test}. Determine whether or not the sequence is complex enough to be considered random. +% \end{itemize} +%\end{itemize} + + +%We have proven in our previous works~\cite{guyeux12:bc} that chaotic iterations satisfying Theorem~\ref{Th:Caractérisation des IC chaotiques} are, among other +%things, strongly transitive, topologically mixing, chaotic as defined by Li and Yorke, +%and that they have a topological entropy and an exponent of Lyapunov both equal to $ln(\mathsf{N})$, +%where $\mathsf{N}$ is the size of the iterated vector. +%These topological properties make that we are ground to believe that a generator based on chaotic +%iterations will probably be able to pass all the existing statistical batteries for pseudorandomness like +%the NIST one. The following subsections, in which we prove that defective generators have their +%statistical properties improved by chaotic iterations, show that such an assumption is true. + +%\subsection{Details of some Existing Generators} + +%The list of defective PRNGs we will use +%as inputs for the statistical tests to come is introduced here. + +%Firstly, the simple linear congruency generators (LCGs) will be used. +%They are defined by the following recurrence: +%\begin{equation} +%x^n = (ax^{n-1} + c)~mod~m, +%\label{LCG} +%\end{equation} +%where $a$, $c$, and $x^0$ must be, among other things, non-negative and inferior to +%$m$~\cite{LEcuyerS07}. In what follows, 2LCGs and 3LCGs refer to two (resp. three) +%combinations of such LCGs. For further details, see~\cite{bfg12a:ip,combined_lcg}. -Secondly, the multiple recursive generators (MRGs) which will be used, -are based on a linear recurrence of order -$k$, modulo $m$~\cite{LEcuyerS07}: -\begin{equation} -x^n = (a^1x^{n-1}+~...~+a^kx^{n-k})~mod~m . -\label{MRG} -\end{equation} -The combination of two MRGs (referred as 2MRGs) is also used in these experiments. +%Secondly, the multiple recursive generators (MRGs) which will be used, +%are based on a linear recurrence of order +%$k$, modulo $m$~\cite{LEcuyerS07}: +%\begin{equation} +%x^n = (a^1x^{n-1}+~...~+a^kx^{n-k})~mod~m . +%\label{MRG} +%\end{equation} +%The combination of two MRGs (referred as 2MRGs) is also used in these experiments. -Generators based on linear recurrences with carry will be regarded too. -This family of generators includes the add-with-carry (AWC) generator, based on the recurrence: -\begin{equation} -\label{AWC} -\begin{array}{l} -x^n = (x^{n-r} + x^{n-s} + c^{n-1})~mod~m, \\ -c^n= (x^{n-r} + x^{n-s} + c^{n-1}) / m, \end{array}\end{equation} -the SWB generator, having the recurrence: -\begin{equation} -\label{SWB} -\begin{array}{l} -x^n = (x^{n-r} - x^{n-s} - c^{n-1})~mod~m, \\ -c^n=\left\{ -\begin{array}{l} -1 ~~~~~\text{if}~ (x^{i-r} - x^{i-s} - c^{i-1})<0\\ -0 ~~~~~\text{else},\end{array} \right. \end{array}\end{equation} -and the SWC generator, which is based on the following recurrence: -\begin{equation} -\label{SWC} -\begin{array}{l} -x^n = (a^1x^{n-1} \oplus ~...~ \oplus a^rx^{n-r} \oplus c^{n-1}) ~ mod ~ 2^w, \\ -c^n = (a^1x^{n-1} \oplus ~...~ \oplus a^rx^{n-r} \oplus c^{n-1}) ~ / ~ 2^w. \end{array}\end{equation} +%Generators based on linear recurrences with carry will be regarded too. +%This family of generators includes the add-with-carry (AWC) generator, based on the recurrence: +%\begin{equation} +%\label{AWC} +%\begin{array}{l} +%x^n = (x^{n-r} + x^{n-s} + c^{n-1})~mod~m, \\ +%c^n= (x^{n-r} + x^{n-s} + c^{n-1}) / m, \end{array}\end{equation} +%the SWB generator, having the recurrence: +%\begin{equation} +%\label{SWB} +%\begin{array}{l} +%x^n = (x^{n-r} - x^{n-s} - c^{n-1})~mod~m, \\ +%c^n=\left\{ +%\begin{array}{l} +%1 ~~~~~\text{if}~ (x^{i-r} - x^{i-s} - c^{i-1})<0\\ +%0 ~~~~~\text{else},\end{array} \right. \end{array}\end{equation} +%and the SWC generator, which is based on the following recurrence: +%\begin{equation} +%\label{SWC} +%\begin{array}{l} +%x^n = (a^1x^{n-1} \oplus ~...~ \oplus a^rx^{n-r} \oplus c^{n-1}) ~ mod ~ 2^w, \\ +%c^n = (a^1x^{n-1} \oplus ~...~ \oplus a^rx^{n-r} \oplus c^{n-1}) ~ / ~ 2^w. \end{array}\end{equation} -Then the generalized feedback shift register (GFSR) generator has been implemented, that is: -\begin{equation} -x^n = x^{n-r} \oplus x^{n-k} . -\label{GFSR} -\end{equation} +%Then the generalized feedback shift register (GFSR) generator has been implemented, that is: +%\begin{equation} +%x^n = x^{n-r} \oplus x^{n-k} . +%\label{GFSR} +%\end{equation} -Finally, the nonlinear inversive (INV) generator~\cite{LEcuyerS07} has been studied, which is: +%Finally, the nonlinear inversive (INV) generator~\cite{LEcuyerS07} has been studied, which is: -\begin{equation} -\label{INV} -\begin{array}{l} -x^n=\left\{ -\begin{array}{ll} -(a^1 + a^2 / z^{n-1})~mod~m & \text{if}~ z^{n-1} \neq 0 \\ -a^1 & \text{if}~ z^{n-1} = 0 .\end{array} \right. \end{array}\end{equation} - - - -\begin{table} -%\renewcommand{\arraystretch}{1} -\caption{TestU01 Statistical Test Failures} -\label{TestU011} -\centering - \begin{tabular}{lccccc} - \toprule -Test name &Tests& Logistic & XORshift & ISAAC\\ -Rabbit & 38 &21 &14 &0 \\ -Alphabit & 17 &16 &9 &0 \\ -Pseudo DieHARD &126 &0 &2 &0 \\ -FIPS\_140\_2 &16 &0 &0 &0 \\ -SmallCrush &15 &4 &5 &0 \\ -Crush &144 &95 &57 &0 \\ -Big Crush &160 &125 &55 &0 \\ \hline -Failures & &261 &146 &0 \\ -\bottomrule - \end{tabular} -\end{table} - - - -\begin{table} -%\renewcommand{\arraystretch}{1} -\caption{TestU01 Statistical Test Failures for Old CI algorithms ($\mathsf{N}=4$)} -\label{TestU01 for Old CI} -\centering - \begin{tabular}{lcccc} - \toprule -\multirow{3}*{Test name} & \multicolumn{4}{c}{Old CI}\\ -&Logistic& XORshift& ISAAC&ISAAC \\ -&+& +& + & + \\ -&Logistic& XORshift& XORshift&ISAAC \\ \cmidrule(r){2-5} -Rabbit &7 &2 &0 &0 \\ -Alphabit & 3 &0 &0 &0 \\ -DieHARD &0 &0 &0 &0 \\ -FIPS\_140\_2 &0 &0 &0 &0 \\ -SmallCrush &2 &0 &0 &0 \\ -Crush &47 &4 &0 &0 \\ -Big Crush &79 &3 &0 &0 \\ \hline -Failures &138 &9 &0 &0 \\ -\bottomrule - \end{tabular} -\end{table} - - - - - -\subsection{Statistical tests} -\label{Security analysis} - -Three batteries of tests are reputed and regularly used -to evaluate the statistical properties of newly designed pseudorandom -number generators. These batteries are named DieHard~\cite{Marsaglia1996}, -the NIST suite~\cite{ANDREW2008}, and the most stringent one called -TestU01~\cite{LEcuyerS07}, which encompasses the two other batteries. - - - -\label{Results and discussion} -\begin{table*} -%\renewcommand{\arraystretch}{1} -\caption{NIST and DieHARD tests suite passing rates for PRNGs without CI} -\label{NIST and DieHARD tests suite passing rate the for PRNGs without CI} -\centering - \begin{tabular}{|l||c|c|c|c|c|c|c|c|c|c|} - \hline\hline -Types of PRNGs & \multicolumn{2}{c|}{Linear PRNGs} & \multicolumn{4}{c|}{Lagged PRNGs} & \multicolumn{1}{c|}{ICG PRNGs} & \multicolumn{3}{c|}{Mixed PRNGs}\\ \hline -\backslashbox{\textbf{$Tests$}} {\textbf{$PRNG$}} & LCG& MRG& AWC & SWB & SWC & GFSR & INV & LCG2& LCG3& MRG2 \\ \hline -NIST & 11/15 & 14/15 &\textbf{15/15} & \textbf{15/15} & 14/15 & 14/15 & 14/15 & 14/15& 14/15& 14/15 \\ \hline -DieHARD & 16/18 & 16/18 & 15/18 & 16/18 & \textbf{18/18} & 16/18 & 16/18 & 16/18& 16/18& 16/18\\ \hline -\end{tabular} -\end{table*} - -Table~\ref{NIST and DieHARD tests suite passing rate the for PRNGs without CI} shows the -results on the two first batteries recalled above, indicating that all the PRNGs presented -in the previous section -cannot pass all these tests. In other words, the statistical quality of these PRNGs cannot -fulfill the up-to-date standards presented previously. We have shown in~\cite{bfg12a:ip} that the use of chaotic -iterations can solve this issue. -%More precisely, to -%illustrate the effects of chaotic iterations on these defective PRNGs, experiments have been divided in three parts~\cite{bfg12a:ip}: -%\begin{enumerate} -% \item \textbf{Single CIPRNG}: The PRNGs involved in CI computing are of the same category. -% \item \textbf{Mixed CIPRNG}: Two different types of PRNGs are mixed during the chaotic iterations process. -% \item \textbf{Multiple CIPRNG}: The generator is obtained by repeating the composition of the iteration function as follows: $x^0\in \mathds{B}^{\mathsf{N}}$, and $\forall n\in \mathds{N}^{\ast },\forall i\in \llbracket1;\mathsf{N}\rrbracket, x_i^n=$ %\begin{equation} +%\label{INV} %\begin{array}{l} -%\left\{ -%\begin{array}{l} -%x_i^{n-1}~~~~~\text{if}~S^n\neq i \\ -%\forall j\in \llbracket1;\mathsf{m}\rrbracket,f^m(x^{n-1})_{S^{nm+j}}~\text{if}~S^{nm+j}=i.\end{array} \right. \end{array} -%\end{equation} -%$m$ is called the \emph{functional power}. -%\end{enumerate} -% -The obtained results are reproduced in Table -\ref{NIST and DieHARD tests suite passing rate the for single CIPRNGs}. -The scores written in boldface indicate that all the tests have been passed successfully, whereas an -asterisk ``*'' means that the considered passing rate has been improved. -The improvements are obvious for both the ``Old CI'' and the ``New CI'' generators. -Concerning the ``Xor CI PRNG'', the score is less spectacular. Because of a large speed improvement, the statistics - are not as good as for the two other versions of these CIPRNGs. -However 8 tests have been improved (with no deflation for the other results). - - -\begin{table*} -%\renewcommand{\arraystretch}{1.3} -\caption{NIST and DieHARD tests suite passing rates for PRNGs with CI} -\label{NIST and DieHARD tests suite passing rate the for single CIPRNGs} -\centering - \begin{tabular}{|l||c|c|c|c|c|c|c|c|c|c|c|c|} - \hline -Types of PRNGs & \multicolumn{2}{c|}{Linear PRNGs} & \multicolumn{4}{c|}{Lagged PRNGs} & \multicolumn{1}{c|}{ICG PRNGs} & \multicolumn{3}{c|}{Mixed PRNGs}\\ \hline -\backslashbox{\textbf{$Tests$}} {\textbf{$Single~CIPRNG$}} & LCG & MRG & AWC & SWB & SWC & GFSR & INV& LCG2 & LCG3& MRG2 \\ \hline\hline -Old CIPRNG\\ \hline \hline -NIST & \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} & \textbf{15/15} & \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} *& \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} \\ \hline -DieHARD & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} & \textbf{18/18} * & \textbf{18/18} *& \textbf{18/18} * & \textbf{18/18} *& \textbf{18/18} * \\ \hline -New CIPRNG\\ \hline \hline -NIST & \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} & \textbf{15/15} & \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} *& \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} \\ \hline -DieHARD & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} *& \textbf{18/18} *\\ \hline -Xor CIPRNG\\ \hline\hline -NIST & 14/15*& \textbf{15/15} * & \textbf{15/15} & \textbf{15/15} & 14/15 & \textbf{15/15} * & 14/15& \textbf{15/15} * & \textbf{15/15} *& \textbf{15/15} \\ \hline -DieHARD & 16/18 & 16/18 & 17/18* & \textbf{18/18} * & \textbf{18/18} & \textbf{18/18} * & 16/18 & 16/18 & 16/18& 16/18\\ \hline -\end{tabular} -\end{table*} - - -We have then investigated in~\cite{bfg12a:ip} if it were possible to improve -the statistical behavior of the Xor CI version by combining more than one -$\oplus$ operation. Results are summarized in Table~\ref{threshold}, illustrating -the progressive increasing effects of chaotic iterations, when giving time to chaos to get settled in. -Thus rapid and perfect PRNGs, regarding the NIST and DieHARD batteries, can be obtained -using chaotic iterations on defective generators. - -\begin{table*} -%\renewcommand{\arraystretch}{1.3} -\caption{Number of $\oplus$ operations to pass the whole NIST and DieHARD batteries} -\label{threshold} -\centering - \begin{tabular}{|l||c|c|c|c|c|c|c|c|} - \hline -Inputted $PRNG$ & LCG & MRG & SWC & GFSR & INV& LCG2 & LCG3 & MRG2 \\ \hline\hline -Threshold value $m$& 19 & 7 & 2& 1 & 11& 9& 3& 4\\ \hline\hline -\end{tabular} -\end{table*} - -Finally, the TestU01 battery has been launched on three well-known generators -(a logistic map, a simple XORshift, and the cryptographically secure ISAAC, -see Table~\ref{TestU011}). These results can be compared with -Table~\ref{TestU01 for Old CI}, which gives the scores obtained by the -Old CI PRNG that has received these generators. -The obvious improvement speaks for itself, and together with the other -results recalled in this section, it reinforces the opinion that a strong -correlation between topological properties and statistical behavior exists. - - -The next subsection will now give a concrete original implementation of the Xor CI PRNG, the -fastest generator in the chaotic iteration based family. In the remainder, -this generator will be simply referred to as CIPRNG, or ``the proposed PRNG'', if this statement does not -raise ambiguity. - +%x^n=\left\{ +%\begin{array}{ll} +%(a^1 + a^2 / z^{n-1})~mod~m & \text{if}~ z^{n-1} \neq 0 \\ +%a^1 & \text{if}~ z^{n-1} = 0 .\end{array} \right. \end{array}\end{equation} + + + +%\begin{table} +%%\renewcommand{\arraystretch}{1} +%\caption{TestU01 Statistical Test Failures} +%\label{TestU011} +%\centering +% \begin{tabular}{lccccc} +% \toprule +%Test name &Tests& Logistic & XORshift & ISAAC\\ +%Rabbit & 38 &21 &14 &0 \\ +%Alphabit & 17 &16 &9 &0 \\ +%Pseudo DieHARD &126 &0 &2 &0 \\ +%FIPS\_140\_2 &16 &0 &0 &0 \\ +%SmallCrush &15 &4 &5 &0 \\ +%Crush &144 &95 &57 &0 \\ +%Big Crush &160 &125 &55 &0 \\ \hline +%Failures & &261 &146 &0 \\ +%\bottomrule +% \end{tabular} +%\end{table} + + + +%\begin{table} +%%\renewcommand{\arraystretch}{1} +%\caption{TestU01 Statistical Test Failures for Old CI algorithms ($\mathsf{N}=4$)} +%\label{TestU01 for Old CI} +%\centering +% \begin{tabular}{lcccc} +% \toprule +%\multirow{3}*{Test name} & \multicolumn{4}{c}{Old CI}\\ +%&Logistic& XORshift& ISAAC&ISAAC \\ +%&+& +& + & + \\ +%&Logistic& XORshift& XORshift&ISAAC \\ \cmidrule(r){2-5} +%Rabbit &7 &2 &0 &0 \\ +%Alphabit & 3 &0 &0 &0 \\ +%DieHARD &0 &0 &0 &0 \\ +%FIPS\_140\_2 &0 &0 &0 &0 \\ +%SmallCrush &2 &0 &0 &0 \\ +%Crush &47 &4 &0 &0 \\ +%Big Crush &79 &3 &0 &0 \\ \hline +%Failures &138 &9 &0 &0 \\ +%\bottomrule +% \end{tabular} +%\end{table} + + + + + +%\subsection{Statistical tests} +%\label{Security analysis} + +%Three batteries of tests are reputed and regularly used +%to evaluate the statistical properties of newly designed pseudorandom +%number generators. These batteries are named DieHard~\cite{Marsaglia1996}, +%the NIST suite~\cite{ANDREW2008}, and the most stringent one called +%TestU01~\cite{LEcuyerS07}, which encompasses the two other batteries. + + + +%\label{Results and discussion} +%\begin{table*} +%%\renewcommand{\arraystretch}{1} +%\caption{NIST and DieHARD tests suite passing rates for PRNGs without CI} +%\label{NIST and DieHARD tests suite passing rate the for PRNGs without CI} +%\centering +% \begin{tabular}{|l||c|c|c|c|c|c|c|c|c|c|} +% \hline\hline +%Types of PRNGs & \multicolumn{2}{c|}{Linear PRNGs} & \multicolumn{4}{c|}{Lagged PRNGs} & \multicolumn{1}{c|}{ICG PRNGs} & \multicolumn{3}{c|}{Mixed PRNGs}\\ \hline +%\backslashbox{\textbf{$Tests$}} {\textbf{$PRNG$}} & LCG& MRG& AWC & SWB & SWC & GFSR & INV & LCG2& LCG3& MRG2 \\ \hline +%NIST & 11/15 & 14/15 &\textbf{15/15} & \textbf{15/15} & 14/15 & 14/15 & 14/15 & 14/15& 14/15& 14/15 \\ \hline +%DieHARD & 16/18 & 16/18 & 15/18 & 16/18 & \textbf{18/18} & 16/18 & 16/18 & 16/18& 16/18& 16/18\\ \hline +%\end{tabular} +%\end{table*} + +%Table~\ref{NIST and DieHARD tests suite passing rate the for PRNGs without CI} shows the +%results on the two first batteries recalled above, indicating that all the PRNGs presented +%in the previous section +%cannot pass all these tests. In other words, the statistical quality of these PRNGs cannot +%fulfill the up-to-date standards presented previously. We have shown in~\cite{bfg12a:ip} that the use of chaotic +%iterations can solve this issue. +%%More precisely, to +%%illustrate the effects of chaotic iterations on these defective PRNGs, experiments have been divided in three parts~\cite{bfg12a:ip}: +%%\begin{enumerate} +%% \item \textbf{Single CIPRNG}: The PRNGs involved in CI computing are of the same category. +%% \item \textbf{Mixed CIPRNG}: Two different types of PRNGs are mixed during the chaotic iterations process. +%% \item \textbf{Multiple CIPRNG}: The generator is obtained by repeating the composition of the iteration function as follows: $x^0\in \mathds{B}^{\mathsf{N}}$, and $\forall n\in \mathds{N}^{\ast },\forall i\in \llbracket1;\mathsf{N}\rrbracket, x_i^n=$ +%%\begin{equation} +%%\begin{array}{l} +%%\left\{ +%%\begin{array}{l} +%%x_i^{n-1}~~~~~\text{if}~S^n\neq i \\ +%%\forall j\in \llbracket1;\mathsf{m}\rrbracket,f^m(x^{n-1})_{S^{nm+j}}~\text{if}~S^{nm+j}=i.\end{array} \right. \end{array} +%%\end{equation} +%%$m$ is called the \emph{functional power}. +%%\end{enumerate} +%% +%The obtained results are reproduced in Table +%\ref{NIST and DieHARD tests suite passing rate the for single CIPRNGs}. +%The scores written in boldface indicate that all the tests have been passed successfully, whereas an +%asterisk ``*'' means that the considered passing rate has been improved. +%The improvements are obvious for both the ``Old CI'' and the ``New CI'' generators. +%Concerning the ``Xor CI PRNG'', the score is less spectacular. Because of a large speed improvement, the statistics +% are not as good as for the two other versions of these CIPRNGs. +%However 8 tests have been improved (with no deflation for the other results). + + +%\begin{table*} +%%\renewcommand{\arraystretch}{1.3} +%\caption{NIST and DieHARD tests suite passing rates for PRNGs with CI} +%\label{NIST and DieHARD tests suite passing rate the for single CIPRNGs} +%\centering +% \begin{tabular}{|l||c|c|c|c|c|c|c|c|c|c|c|c|} +% \hline +%Types of PRNGs & \multicolumn{2}{c|}{Linear PRNGs} & \multicolumn{4}{c|}{Lagged PRNGs} & \multicolumn{1}{c|}{ICG PRNGs} & \multicolumn{3}{c|}{Mixed PRNGs}\\ \hline +%\backslashbox{\textbf{$Tests$}} {\textbf{$Single~CIPRNG$}} & LCG & MRG & AWC & SWB & SWC & GFSR & INV& LCG2 & LCG3& MRG2 \\ \hline\hline +%Old CIPRNG\\ \hline \hline +%NIST & \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} & \textbf{15/15} & \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} *& \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} \\ \hline +%DieHARD & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} & \textbf{18/18} * & \textbf{18/18} *& \textbf{18/18} * & \textbf{18/18} *& \textbf{18/18} * \\ \hline +%New CIPRNG\\ \hline \hline +%NIST & \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} & \textbf{15/15} & \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} *& \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} \\ \hline +%DieHARD & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} *& \textbf{18/18} *\\ \hline +%Xor CIPRNG\\ \hline\hline +%NIST & 14/15*& \textbf{15/15} * & \textbf{15/15} & \textbf{15/15} & 14/15 & \textbf{15/15} * & 14/15& \textbf{15/15} * & \textbf{15/15} *& \textbf{15/15} \\ \hline +%DieHARD & 16/18 & 16/18 & 17/18* & \textbf{18/18} * & \textbf{18/18} & \textbf{18/18} * & 16/18 & 16/18 & 16/18& 16/18\\ \hline +%\end{tabular} +%\end{table*} + + +%We have then investigated in~\cite{bfg12a:ip} if it were possible to improve +%the statistical behavior of the Xor CI version by combining more than one +%$\oplus$ operation. Results are summarized in Table~\ref{threshold}, illustrating +%the progressive increasing effects of chaotic iterations, when giving time to chaos to get settled in. +%Thus rapid and perfect PRNGs, regarding the NIST and DieHARD batteries, can be obtained +%using chaotic iterations on defective generators. + +%\begin{table*} +%%\renewcommand{\arraystretch}{1.3} +%\caption{Number of $\oplus$ operations to pass the whole NIST and DieHARD batteries} +%\label{threshold} +%\centering +% \begin{tabular}{|l||c|c|c|c|c|c|c|c|} +% \hline +%Inputted $PRNG$ & LCG & MRG & SWC & GFSR & INV& LCG2 & LCG3 & MRG2 \\ \hline\hline +%Threshold value $m$& 19 & 7 & 2& 1 & 11& 9& 3& 4\\ \hline\hline +%\end{tabular} +%\end{table*} + +%Finally, the TestU01 battery has been launched on three well-known generators +%(a logistic map, a simple XORshift, and the cryptographically secure ISAAC, +%see Table~\ref{TestU011}). These results can be compared with +%Table~\ref{TestU01 for Old CI}, which gives the scores obtained by the +%Old CI PRNG that has received these generators. +%The obvious improvement speaks for itself, and together with the other +%results recalled in this section, it reinforces the opinion that a strong +%correlation between topological properties and statistical behavior exists. + + +%The next subsection will now give a concrete original implementation of the Xor CI PRNG, the +%fastest generator in the chaotic iteration based family. In the remainder, +%this generator will be simply referred to as CIPRNG, or ``the proposed PRNG'', if this statement does not +%raise ambiguity. + + +\section{Toward Efficiency and Improvement for CI PRNG} \subsection{First Efficient Implementation of a PRNG based on Chaotic Iterations} \label{sec:efficient PRNG} @@ -1379,7 +1381,7 @@ this fast generator cannot be proven as secure. -\section{Efficient PRNGs based on Chaotic Iterations on GPU} +\subsection{Efficient PRNGs based on Chaotic Iterations on GPU} \label{sec:efficient PRNG gpu} In order to take benefits from the computing power of GPU, a program -- 2.39.5