From: couturie Date: Sun, 27 Nov 2011 19:10:55 +0000 (+0100) Subject: new X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/prng_gpu.git/commitdiff_plain/d010317c87f30b6e833bb9880b710a013b0e8509?ds=sidebyside new --- diff --git a/prng_gpu.tex b/prng_gpu.tex index 1129a07..efcc4d5 100644 --- 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: -$$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 -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}