Merge branch 'master' of ssh://bilbo.iut-bm.univ-fcomte.fr/prng_gpu

[prng_gpu.git] / prng_gpu.tex

diff --git a/prng_gpu.tex b/prng_gpu.tex
index 1129a07e18b89155ea4519ec23c979dbe397df71..e5b80cc94aa90c5eaa6dd82c2962c3350f16e94c 100644 (file)
--- a/prng_gpu.tex
+++ b/prng_gpu.tex
@@ -949,17 +949,18 @@ It is  possible to build a  cryptographically secure prng based  on the previous
 algorithm (algorithm~\ref{algo:gpu_kernel2}).   It simply consists  in replacing
 the  {\it  xor-like} algorithm  by  another  cryptographically  secure prng.  In
 practice, we suggest  to use the BBS algorithm~\cite{BBS}  which takes the form:
 algorithm (algorithm~\ref{algo:gpu_kernel2}).   It simply consists  in replacing
 the  {\it  xor-like} algorithm  by  another  cryptographically  secure prng.  In
 practice, we suggest  to use the BBS algorithm~\cite{BBS}  which takes the form:

-$$x_{n+1}=x_n^2~ mod~  M$$ where M  is the product  of the prime  numbers. Those
+$$x_{n+1}=x_n^2~ mod~ M$$  where $M$ is the product of  two prime numbers. Those

 prime numbers  need to be congruent  to 3 modulus  4. In practice, this  PRNG is
 known to  be slow and  not efficient for  the generation of random  numbers. For
 current  GPU   cards,  the  modulus   operation  is  the  most   time  consuming
 operation. So in  order to obtain quite reasonable  performances, it is required
 to use only modulus on 32  bits integer numbers. Consequently $x_n^2$ need to be
 less than  $2^{32}$ and the  number $M$  need to be  less than $2^{16}$.   So in
 prime numbers  need to be congruent  to 3 modulus  4. In practice, this  PRNG is
 known to  be slow and  not efficient for  the generation of random  numbers. For
 current  GPU   cards,  the  modulus   operation  is  the  most   time  consuming
 operation. So in  order to obtain quite reasonable  performances, it is required
 to use only modulus on 32  bits integer numbers. Consequently $x_n^2$ need to be
 less than  $2^{32}$ and the  number $M$  need to be  less than $2^{16}$.   So in

-pratice we can choose prime number around 256 that are congruent to 3 modulus 4.
-With 32 bits numbers,  only the 4 least significant bits of  $x_n$ can be chosen
-(the   maximum    number   of   undistinguishing   is   less    or   equals   to
-$log_2(log_2(x_n))$).
+pratice we can  choose prime numbers around 256 that are  congruent to 3 modulus
+4.  With  32 bits numbers,  only the  4 least significant  bits of $x_n$  can be
+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.

 
 \section{Experiments}
 \label{sec:experiments}
 
 \section{Experiments}
 \label{sec:experiments}


@@ -986,10 +987,10 @@ should be of better quality.
 
 \begin{figure}[htbp]
 \begin{center}
 
 \begin{figure}[htbp]
 \begin{center}

-  \includegraphics[scale=.7]{curve_time_gpu.pdf}
+  \includegraphics[scale=.7]{curve_time_xorlike_gpu.pdf}

 \end{center}
 \end{center}

-\caption{Number of random numbers generated per second}
-\label{fig:time_gpu}
+\caption{Number of random numbers generated per second with the xorlike based prng}
+\label{fig:time_xorlike_gpu}

 \end{figure}
 
 
 \end{figure}
 
 


@@ -999,6 +1000,15 @@ In  comparison,   Listing~\ref{algo:seqCIprng}  allows  us   to  generate  about
 
 
 
 
 
 

+\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}
+\label{fig:time_bbs_gpu}
+\end{figure}
+
+

 
 %% \section{Cryptanalysis of the Proposed PRNG}
 
 
 %% \section{Cryptanalysis of the Proposed PRNG}