pouet

diff --git a/mabase.bib b/mabase.bib
index 15c282dcb4aed81e6757a8ceac34d9f64b1c9d90..6b41f33cde043b6b38ec6146c874409286f9c0be 100644 (file)
--- a/mabase.bib
+++ b/mabase.bib
@@ -14,6 +14,32 @@
   timestamp = {2009.06.29}
 }
 
   timestamp = {2009.06.29}
 }
 

+@inproceedings{bfg12a:ip,
+inhal = {no},
+domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
+equipe = {and},
+classement = {ACTI},
+author = {Bahi, Jacques and Fang, Xiaole and Guyeux, Christophe},
+title = {An optimization technique on pseudorandom generators based on chaotic iterations},
+booktitle = {INTERNET'2012, 4-th Int. Conf. on Evolving Internet},
+pages = {***--***},
+address = {Venice, Italy},
+month = jun,
+year = 2012,
+note = {To appear},
+
+}
+
+@Article{combined_lcg,
+       title = "Efficient and portable combined random number generators",
+       journal = "Communications of the ACM",
+       volume = "31",
+       number = "6",
+       pages = "742--749",
+       year = "1988",
+}
+
+

 @INPROCEEDINGS{Fischlin,
   author = {Fischlin, R. and Schnorr, C. P.},
   title = {Stronger security proofs for RSA and rabin bits},
 @INPROCEEDINGS{Fischlin,
   author = {Fischlin, R. and Schnorr, C. P.},
   title = {Stronger security proofs for RSA and rabin bits},

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.