pouet

[prng_gpu.git] / prng_gpu.tex

diff --git a/prng_gpu.tex b/prng_gpu.tex
index ba76fe2e244a35fccfa418c2452df09bc309780d..468b21825b64bbe85e43f6b942e5b75bc7d4477d 100644 (file)
--- a/prng_gpu.tex
+++ b/prng_gpu.tex
@@ -929,37 +929,39 @@ have $d((S,E),(\tilde S,E))<\epsilon$.
 \begin{color}{red}
 \section{Statistical Improvements Using Chaotic Iterations}
 
 \begin{color}{red}
 \section{Statistical Improvements Using Chaotic Iterations}
 

-\subsection{About some Well-known PRNGs}

 \label{The generation of pseudo-random sequence}
 
 
 \label{The generation of pseudo-random sequence}
 
 

-
-
-Let us now give illustration on the fact that chaos appears to improve statistical properties.
+Let us now explain why we are reasonable grounds to believe that chaos 
+can improve statistical properties.
+We will show in this section that, when mixing defective PRNGs with
+chaotic iterations, the result presents better statistical properties
+(this section summarizes the work of~\cite{bfg12a:ip}).

 
 \subsection{Details of some Existing Generators}
 
 
 \subsection{Details of some Existing Generators}
 

-Here are the modules of PRNGs we have chosen to experiment.
+The list of defective PRNGs we will use 
+as inputs for the statistical tests to come is introduced here.

 
 

-\subsubsection{LCG}
-This PRNG implements either the simple or the combined linear congruency generator (LCGs). The simple LCG is defined by the recurrence:
+Firstly, the simple linear congruency generator (LCGs) is defined by the following recurrence:

 \begin{equation}
 x^n = (ax^{n-1} + c)~mod~m
 \label{LCG}
 \end{equation}
 \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 less than $m$~\cite{testU01}. In what follows, 2LCGs and 3LCGs refer as two (resp. three) combinations of such LCGs.
-For further details, see~\cite{combined_lcg}.
+where $a$, $c$, and $x^0$ must be, among other things, non-negative and less than 
+$m$~\cite{LEcuyerS07}. In what follows, 2LCGs and 3LCGs refer as two (resp. three) 
+combinations of such LCGs. For further details, see~\cite{bfg12a:ip,combined_lcg}.

 
 

-\subsubsection{MRG}
-This module implements multiple recursive generators (MRGs), based on a linear recurrence of order $k$, modulo $m$~\cite{testU01}:
+Secondly, the multiple recursive generators (MRGs) is 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}
 Combination of two MRGs (referred as 2MRGs) is also be used in this paper.
 
 \begin{equation}
 x^n = (a^1x^{n-1}+~...~+a^kx^{n-k})~mod~m
 \label{MRG}
 \end{equation}
 Combination of two MRGs (referred as 2MRGs) is also be used in this paper.
 

-\subsubsection{UCARRY}
-Generators based on linear recurrences with carry are implemented in this module. This includes the add-with-carry (AWC) generator, based on the recurrence:
+Thirdly, generators based on linear recurrences with carry will be regarded too in experimentations. 
+This includes the add-with-carry (AWC) generator, based on the recurrence:

 \begin{equation}
 \label{AWC}
 \begin{array}{l}
 \begin{equation}
 \label{AWC}
 \begin{array}{l}


@@ -981,16 +983,14 @@ and the SWC generator designed by R. Couture, which is based on the following re
 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}
 
 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}
 

-\subsubsection{GFSR}
-This module implements the generalized feedback shift register (GFSR) generator, that is:
+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}
 
 
 \begin{equation}
 x^n = x^{n-r} \oplus x^{n-k}
 \label{GFSR}
 \end{equation}
 
 

-\subsubsection{INV}
-Finally, this module implements the nonlinear inversive generator, as defined in~\cite{testU01}, which is:
+Finally, the nonlinear inversive generator~\cite{LEcuyerS07} has been regarded too, which is:

 
 \begin{equation}
 \label{INV}
 
 \begin{equation}
 \label{INV}


@@ -1007,8 +1007,12 @@ a^1 & \text{if}~  z^{n-1} = 0 .\end{array} \right. \end{array}\end{equation}
 \subsection{Statistical tests}
 \label{Security analysis}
 
 \subsection{Statistical tests}
 \label{Security analysis}
 

-%A theoretical proof for the randomness of a generator is impossible to give, therefore statistical inference based on observed sample sequences produced by the generator seems to be the best option.
-Considering the properties of binary random sequences, various statistical tests can be designed to evaluate the assertion that the sequence is generated by a perfectly random source. We have performed some statistical tests for the CIPRNGs proposed here. These tests include NIST suite~\cite{ANDREW2008} and DieHARD battery of tests~\cite{DieHARD}. For completeness and for reference, we give in the following subsection a brief description of each of the aforementioned tests.
+Considering the properties of binary random sequences, various statistical tests can be designed 
+to evaluate the assertion that the sequence is generated by a perfectly random source. We have 
+performed some statistical tests for the CIPRNGs proposed here. These tests include NIST 
+suite~\cite{ANDREW2008} and DieHARD battery of tests~\cite{DieHARD}. For completeness and 
+for reference, we give in the following subsection a brief description of each of the 
+aforementioned tests.