# 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?

## migrated from stackoverflow.comMar 20 '12 at 14:24

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

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

## 1 Answer

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

• 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. – William Hird Jul 8 '13 at 22:04