# How to find the exact period of Blum-Blum-Shub random number generator?

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?

• This is not a real answer but you might get a quicker reply to this question on the SE Crypto site. 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$.
• 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.