2
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – ckamath
    Oct 12, 2022 at 15:30
  • $\begingroup$ @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. $\endgroup$
    – Daniel S
    Oct 13, 2022 at 16:35
  • $\begingroup$ Could you point me to some references? This is not obvious to me. $\endgroup$
    – ckamath
    Oct 14, 2022 at 7:23
  • $\begingroup$ 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. $\endgroup$
    – Daniel S
    Oct 14, 2022 at 7:43
  • $\begingroup$ I see. Will try to work it out. $\endgroup$
    – ckamath
    Oct 14, 2022 at 13:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.