From: couturie Date: Sun, 11 Dec 2011 16:43:04 +0000 (+0100) Subject: modif dans le bbs X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/prng_gpu.git/commitdiff_plain/ef5711321ecf848ad064bef33993b326d804152c?ds=sidebyside modif dans le bbs --- diff --git a/prng_gpu.tex b/prng_gpu.tex index 4feac7c..de8f464 100644 --- a/prng_gpu.tex +++ b/prng_gpu.tex @@ -1092,13 +1092,12 @@ As a comparison, Listing~\ref{algo:seqCIPRNG} leads to the generation of -In Figure~\ref{fig:time_bbs_gpu} we highlight the performances of the optimized -BBS-based PRNG on GPU. On the Tesla C1060 we -obtain approximately 700MSample/s and on the GTX 280 about 670MSample/s, which is -obviously slower than the xorlike-based PRNG on GPU. However, we will show in the -next sections that -this new PRNG has a strong level of security, which is necessary paid by a speed -reduction. +In Figure~\ref{fig:time_bbs_gpu} we highlight the performances of the optimized +BBS-based PRNG on GPU. On the Tesla C1060 we obtain approximately 700MSample/s +and on the GTX 280 about 670MSample/s, which is obviously slower than the +xorlike-based PRNG on GPU. However, we will show in the next sections that this +new PRNG has a strong level of security, which is necessary paid by a speed +reduction. \begin{figure}[htbp] \begin{center} @@ -1339,20 +1338,24 @@ on the variable $t$ and stores the result in $t$, and $BBS1(bbs1)\&15$ selects the last four bits of the result of $BBS1$. Thus an operation of the form $t<<=4; t|=BBS1(bbs1)\&15\;$ realizes in $t$ a left shift of 4 bits, and then puts the 4 last bits of $BBS1(bbs1)$ in the four last positions of $t$. Let us -remark that to initialize $t$ is not a necessity as we fill it 4 bits by 4 bits, -until having obtained 32-bits. The two last new shifts are realized in order to -enlarge the small periods of the BBS used here, to introduce a kind of +remark that the initialization $t$ is not a necessity as we fill it 4 bits by 4 +bits, until having obtained 32-bits. The two last new shifts are realized in +order to enlarge the small periods of the BBS used here, to introduce a kind of variability. In these operations, we make twice a left shift of $t$ of \emph{at most} 3 bits, represented by \texttt{shift} in the algorithm, and we put \emph{exactly} the \texttt{shift} last bits from a BBS into the \texttt{shift} -last bits of $t$. +last bits of $t$. For this, an array named \texttt{array\_shift}, containing the +correspondance between the shift and the number obtained with \texttt{shift} 1 +to make the \texttt{and} operation is used. For example, with a left shift of 0, +we make an and operation with 0, with a left shift of 3, we make an and +operation with 7 (represented by 111 in binary mode). -It should be noticed that this generator has another time the form $x^{n+1} = x^n \oplus S^n$, +It should be noticed that this generator has once more the form $x^{n+1} = x^n \oplus S^n$, where $S^n$ is referred in this algorithm as $t$: each iteration of this PRNG ends with $x = x \wedge t$. This $S^n$ is only constituted by secure bits produced by the BBS generator, and thus, due to Proposition~\ref{cryptopreuve}, the resulted PRNG is cryptographically -secure +secure.