From: guyeux Date: Thu, 14 Jun 2012 08:56:47 +0000 (+0200) Subject: pouet X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/prng_gpu.git/commitdiff_plain/11f1ec59d1b84c34db2d61d773d6fe2c9a480938?ds=sidebyside pouet --- diff --git a/mabase.bib b/mabase.bib index 15c282d..6b41f33 100644 --- a/mabase.bib +++ b/mabase.bib @@ -14,6 +14,32 @@ 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}, diff --git a/prng_gpu.tex b/prng_gpu.tex index ba76fe2..468b218 100644 --- 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} -\subsection{About some Well-known PRNGs} \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} -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} -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. -\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} @@ -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} -\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} -\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} @@ -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} -%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.