1

By reading on Wikipedia, they say the following (these is also supported by the following work: http://www.daimi.au.dk/~mg/mamian/random-bits.pdf)

The seed x0 should be an integer that is co-prime to M (i.e. p and q are not factors of x0) and not 1 or 0.

The two primes, p and q, should both be congruent to 3 (mod 4) (this guarantees that each quadratic residue has one square root which is also a quadratic residue) and gcd(φ(p − 1), φ(q − 1)) should be small (this makes the cycle length large).

Can someone clarify why the part in bold implies that each quadratic residue has one square root which is also a QR?

Bogdan T.
  • 113

1 Answers1

1

Because $-1$ is not a quadratic residue modulo a prime $p\equiv 3 \mod 4$ and the product of two non-residues is a residue. A (non-zero) quadratic residue $r=d^2\mod p$ has the two square roots $\pm d$ which differ by a factor of $-1$. If $d$ is a non-residue, $-d$ is a residue.

Mark Bennet
  • 100,194