From 0067ddaf35f9842d01238d6d0b1161e791e66f2e Mon Sep 17 00:00:00 2001 From: Raphael Couturier Date: Mon, 28 Nov 2011 17:33:45 +0100 Subject: [PATCH] bbs --- prng_gpu.tex | 46 ++++++++++++++++++++++++++++++---------------- 1 file changed, 30 insertions(+), 16 deletions(-) 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} -- 2.39.5