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