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

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 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? Oct 12, 2022 at 15:30