I've read the original paper and some related ones. But the best I can find about the period of BBS is that the period is a factor of $λ(λ(M))$, where $λ$ is Carmichael function and $M$ is the product of two large primes that are congruent to 3 (mod 4).

Is there any way to determine the exact period of BBS?


migrated from stackoverflow.com Mar 20 '12 at 14:24

This question came from our site for professional and enthusiast programmers.

  • 1
    $\begingroup$ This is not a real answer but you might get a quicker reply to this question on the SE Crypto site. $\endgroup$ – William Hird Mar 21 '12 at 20:46

You can determine the period reasonably easily if you know the factorization of $M$ as $pq$, the factorization of $(p-1)\cdot (q-1)$ and the factorization of $\ell-1$ for any prime $\ell$ that divides $(p-1)\cdot (q-1)$.

This requires two steps, first find the order of $x_0$ modulo $M$. Since this divides $(p-1)\cdot (q-1)$ whose factorization is known, this is standard. Let $L$ denote this order, the period of BBS is the order of $2$ modulo $L$ and you can compute it in the same way as we computed $L$.

  • $\begingroup$ Looks like I am wrong again, you got a faster reply here ! You only had to be patient and wait 18 months for your answer. $\endgroup$ – William Hird Jul 8 '13 at 22:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy