From: Raphael Couturier <raphael.couturier@univ-fcomte.fr>
Date: Mon, 28 Nov 2011 16:33:45 +0000 (+0100)
Subject: bbs
X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/prng_gpu.git/commitdiff_plain/0067ddaf35f9842d01238d6d0b1161e791e66f2e?ds=inline

bbs
---

diff --git a/prng_gpu.tex b/prng_gpu.tex
index e5b80cc..6e063fd 100644
--- a/prng_gpu.tex
+++ b/prng_gpu.tex
@@ -962,6 +962,8 @@ chosen  (the   maximum  number  of   undistinguishing  is  less  or   equals  to
 $log_2(log_2(x_n))$). So  to generate a 32 bits  number, we need to  use 8 times
 the BBS algorithm, with different combinations of $M$ is required.
 
+Currently this PRNG does not succeed to pass all the tests of TestU01.
+
 \section{Experiments}
 \label{sec:experiments}
 
@@ -971,12 +973,14 @@ Intel  Xeon E5530 cadenced  at 2.40  GHz for  our experiments  and we  have used
 another one  equipped with  a less performant  CPU and  a GeForce GTX  280. Both
 cards have 240 cores.
 
-In Figure~\ref{fig:time_gpu}  we compare the number of  random numbers generated
-per second. The xor-like prng  is a xor64 described in~\cite{Marsaglia2003}.  In
-order to obtain the optimal performance  we remove the storage of random numbers
-in the GPU memory. This step is time consuming and slows down the random number
-generation.  Moreover, if you are interested by applications that consume random
-numbers  directly   when  they  are  generated,  their   storage  is  completely
+In  Figure~\ref{fig:time_xorlike_gpu} we  compare the  number of  random numbers
+generated per second with the xor-like based PRNG. In this figure, the optimized
+version use the {\it xor64} described in~\cite{Marsaglia2003}. The naive version
+use  the three  xor-like  PRNGs described  in Listing~\ref{algo:seqCIprng}.   In
+order to obtain the optimal performance we removed the storage of random numbers
+in the GPU memory. This step is time consuming and slows down the random numbers
+generation.  Moreover, if one is  interested by applications that consume random
+numbers  directly   when  they  are  generated,  their   storage  are  completely
 useless. In this  figure we can see  that when the number of  threads is greater
 than approximately 30,000 upto 5 millions the number of random numbers generated
 per second  is almost constant.  With the  naive version, it is  between 2.5 and
@@ -989,7 +993,7 @@ should be of better quality.
 \begin{center}
   \includegraphics[scale=.7]{curve_time_xorlike_gpu.pdf}
 \end{center}
-\caption{Number of random numbers generated per second with the xorlike based prng}
+\caption{Number of random numbers generated per second with the xorlike based PRNG}
 \label{fig:time_xorlike_gpu}
 \end{figure}
 
@@ -998,16 +1002,22 @@ In  comparison,   Listing~\ref{algo:seqCIprng}  allows  us   to  generate  about
 138MSample/s with only one core of the Xeon E5530.
 
 
-
+In Figure~\ref{fig:time_bbs_gpu}  we highlight the performance  of the optimized
+BBS based  PRNG on GPU. Performances are  less important. On the  Tesla C1060 we
+obtain approximately 1.8GSample/s and on the GTX 280 about 1.6GSample/s.
 
 \begin{figure}[htbp]
 \begin{center}
   \includegraphics[scale=.7]{curve_time_bbs_gpu.pdf}
 \end{center}
-\caption{Number of random numbers generated per second with the bbs based prng}
+\caption{Number of random numbers generated per second with the BBS based PRNG}
 \label{fig:time_bbs_gpu}
 \end{figure}
 
+Both  these  experimentations allows  us  to conclude  that  it  is possible  to
+generate a  huge number of pseudo-random  numbers with the  xor-like version and
+about tens  times less with the BBS  based version. The former  version has only
+chaotic properties whereas the latter also has cryptographically properties.
 
 
 %% \section{Cryptanalysis of the Proposed PRNG}
@@ -1662,15 +1672,19 @@ proving that $H$ is not secure, a contradiction.
 
 
 In  this  paper  we have  presented  a  new  class  of  PRNGs based  on  chaotic
-iterations. We have proven that these PRNGs are chaotic in the sense of Devenay. 
+iterations. We have proven that these PRNGs are chaotic in the sense of Devenay.
+We also propose a PRNG cryptographically secure and its implementation on GPU.
+
+An  efficient implementation  on  GPU based  on  a xor-like  PRNG  allows us  to
+generate   a  huge   number   of  pseudo-random   numbers   per  second   (about
+20Gsample/s). This PRNG succeeds to pass the hardest batteries of TestU01.
+
+In future  work we plan to  extend this work  for parallel PRNG for  clusters or
+grid computing. We also plan to improve  the BBS version in order to succeed all
+the tests of TestU01.
 
-An efficient implementation on GPU allows us to generate a huge number of pseudo
-random numbers  per second  (about 20Gsample/s). Our  PRNGs succeed to  pass the
-hardest batteries of test (TestU01).
 
-In future  work we plan  to extend our  work in order to  have cryptographically
-secure PRNGs because in some situations this property may be important.
 
-\bibliographystyle{plain}
+\bibliographystyle{plain} 
 \bibliography{mabase}
 \end{document}