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?

Improve this question
$\endgroup$
1
  • 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, 2012 at 20:46

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$
2
  • $\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, 2013 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$
    – user55377
    Nov 23, 2019 at 13:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.