0
$\begingroup$

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!

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

1 Answer 1

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Dec 18, 2023 at 11:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .