3
$\begingroup$

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?

$\endgroup$
  • 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
4
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • $\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
  • $\begingroup$ Note that this result is not correct. The period of BBS is the order of $2$ modulo $L/2^{\text{max}}$ where $2^{\text{max}}$ is the greatest power of $2$ that divides $L$. Furthermore, because of that, but also in your answer, some more factorizations need to be known (or the user being able to find out), in order to compute the (minimum) aforementioned period. $\endgroup$ – Jason Nov 23 '19 at 13:23

Your Answer

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