# Finding the period of the BBS sequence

Let $$n=pq$$, where $$p,q$$ are primes and $$p \equiv q \equiv 3 \mod 4$$. Choose an integer, $$x_0$$, such that $$x_0$$ and $$n$$ are co-primes. We define the sequence: \begin{align} x_i = x_0^{2^i} \mod n \end{align}

This sequence is periodic, but I am having a really hard time calculating its period. In other words, I am having a hard time finding a $$T = T(p,q,x_0)$$ such that $$x_{i + T} = x_i$$. If it helps, the above sequence is the pseudorandom number generator Blum-Blum-Shub. In the cryptography forum, I have found this question that might be of some use.

I would appreciate any help in finding the period $$T$$. Thanks in advance!

• To clarify: You want to find a function $T$ that will return the period for any given $p, q, x_0$? Dec 16, 2023 at 22:27
• Exactly, since the period $T$ depends on the values of $p,q,x_0$. Dec 16, 2023 at 23:03

$$\def\ed{\stackrel{\text{def}}{=}}$$

First off, the sequence will not necessarily be strictly periodic unless you start it at $$\ i=1\$$ rather than $$\ i=0\ .$$ If $$\ p=7,q=11,\$$ and $$\ x_0=5,\$$ for instance, then \begin{align} x_{4i}&=16\\ x_{4i+1}&=25\\ x_{4i+2}&=9\\ x_{4i+3}&=4 \end{align} for $$\ i\ge1\ ,$$ but $$\ x_4=16\ne5=x_0\ .$$

Let $$\ r\$$ be the multiplicative order $$\mod n\$$of $$\ x_0\ .$$ This must be a divisor of $$\ \lambda(n)\ed\text{lcm}(p-1,q-1)^\color{red}{\dagger} ,$$ and since $$\ p\equiv q\equiv3\pmod{4}\ ,$$ it cannot be divisible by $$\ 4\ .$$ Let $$\ s\ed r\$$ if $$\ r\$$ is odd, or $$\ s\ed\frac{r}{2}\$$ if $$\ r\$$ is even, and let $$\ T\$$ be the multiplicative order $$\mod s\$$ of $$\ 2\ .^\color{red}{\dagger\dagger}$$ Then $$\ T\$$ will be the period you're looking for. If $$\ r\$$ is odd, then the sequence will be strictly periodic. If $$\ r\$$ is even, however, it will only be ultimately periodic, with $$\ x_T\ne x_0\ .$$

In the above example $$\ r=\lambda(77)=30\ ,\ s=15\$$ and $$\ T=\lambda(15)=4\$$.

In the general case, when $$\ r=2s\$$ is even, we have \begin{align} x_0^{2s}&\equiv1\pmod{n}\ \ \text{and}\\ 2^T&\equiv1\pmod{s}\ . \end{align} Therefore, $$\ 2^T=ks+1\$$ for some positive odd integer $$\ k\ ,$$ and \begin{align} x_0^{2^{i+T}}&=\left(x_0^{2^T}\right)^{2^i}\\ &=\left(x_0^{ks+1}\right)^{2^i}\\ &=x_0^{2^iks}x_0^{2^i}\\ &=\left(x_0^{2s}\right)^{2^{i-1}k}x_0^{2^i}\\ &\equiv x_0^{2^i}\pmod{n}\ , \end{align} provided $$\ i\ge1\$$. Note that $$\ ks\$$ in this case is not a multiple of the order (i.e. $$\ r=2s\$$) $$\mod n\$$ of $$\ x_0\ ,$$ so $$\ x_0^{ks}\not\equiv1\pmod{n}\ ,$$ and therefore \begin{align} x_0^{2^T}&=x_0^{ks+1}\\ &=x_0x_0^{ks}\\ &\not\equiv x_0\pmod{n}\ . \end{align} Conversely if $$x_i=x_{i+L}\ ,$$ then \begin{align} x_0^{2^i\left(2^L-1\right)}\equiv 1\pmod{n}\ , \end{align} whence $$\ 2^i\left(2^L-1\right)\$$ must be a multiple of the order $$\ r=2s\$$ of $$\ x_0\mod n\ .$$ Since $$\ s\$$ is odd, this will be the case if and only if $$\ i\ge1\$$ and $$\ 2^L-1\$$ is a multiple of $$\ s\$$—that is $$\ 2^L\equiv1\pmod{s}\$$, and therefore $$\ L\$$ must be a multiple of the order $$\ \mod s\$$ of $$\ 2\ ,$$ namely, $$\ T\ .$$

For the case when $$\ r\$$ is odd, the proof that $$\ T\$$ is the period is essentially the same, except that now $$\ x_0^{2^T}=\,x_0^{kr+1}\equiv\,x_0\pmod{n}\ ,$$ so it's no longer necessary to exclude the $$\ i=0\$$ term from the sequence to make it strictly, rather than ultimately, periodic.

$$\left.\right.^\color{red}{\dagger}$$ $$\ \lambda\$$ here being the Carmichael function.

$$\left.\right.^\color{red}{\dagger\dagger}$$ $$\ T\$$ must be a divisor of $$\ \lambda(s)\$$.

• Thanks! This was really helpful. If you are interested, there was a conversation held in the cryptography forum using some fine techniques. You can find it here. Dec 18, 2023 at 11:53