Score:2

# Significance of having remainder $3$ when divided by $4$ for both $p$ and $q$ in BBS

In the Blum Blum Shub random number generator, we take two random prime numbers $$p$$ and $$q$$ such that both have a remainder of $$3$$ when divided by $$4$$. My question is why can't we just take any $$2$$ random primes? What is significance of having remainder $$3$$ when divided by $$4$$ from the perspective of mathematics and security?

Score:2

This is in order to maximise the state space of the generator after multiple steps. After $$s$$ steps, the BBS generator will have state $$i^{2^s}\mod N$$ where $$i$$ is the initial seed and $$N$$ is the modulus.

In particular then, the state must be $$2^s$$th power modulo $$N$$. The number of residues modulo $$N$$ that are $$2^s$$th powers is the product of the number of $$2^s$$th powers modulo $$p$$ times by the number of $$2^s$$th powers modulo $$q$$ and so we would like to maximise both of these.

The number of distinct $$2^s$$th powers modulo a prime $$p$$ is $$(p-1)/2^{\mathrm{min}(s,k)}$$ where $$2^k$$ is the largest power of $$2$$ that divides $$p-1$$. To minimise this we choose primes $$p$$ where $$k=1$$ (resp. $$q$$). These are the primes that are 3 modulo 4 and for these the number of $$2^s$$th powers will be $$(p-1)/2$$ (resp. $$(q-1)/2$$) and so the number of $$2^s$$th powers modulo $$N$$ will be $$(p-1)(q-1)/4$$.

Isn't it crucial to the reduction from QR/Factoring to pseudorandomness/inversion too (Lemma 1, Claims 2 and 3 in the [SICOMP version](https://www.math.tamu.edu/~rojas/bbs.pdf) of the paper)? Also, not sure whether the primes being $3 \bmod 4$ is sufficient to ensure a large state-space (conditions stated in Theorem 8 do suffice). Am I missing something here?
@ckamath Claims 2 and 3 in the paper hold for moduli where the primes are not 3 mod 4, but are easiest to prove in this case. The primes being 3 mod 4 is sufficient to establish a large state-space, but the additional conditions are required to demonstrate a large cycle length.
Could you point me to some references? This is not obvious to me.
I don't have a reference to hand, but it is all elementary number theory. If you want to set up a chat room, I can go through some of it.
I see. Will try to work it out.
I sit in a Tesla and translated this thread with Ai: