Quadratic congruences

Question

Is there an algorithm to solve the quadratic congruence $x^2\equiv D \pmod m$ for any $D$ and $m$? I searched a bit and found algorithms for $m$ prime and $\gcd(D, m) = 1$. None of them gave a comprehensive way to solve the general equation.Thanks in advance.

Answer 1

If you know how to find solutions (or show nonexistence) if $m$ is prime and $D\not \equiv 0\pmod m$, you can extend this to $m=p^k$ a prime power (and $D$ still prime to it) using Hensel's lemma (watch out for $p=2$, primes are slippery when even). You can combine this to solve the case of arbitrary $m$ coprime to $D$ using the chinese remainder theorem.

What if $\gcd(m,D)\ne 1$? If $p|m$ and $p|D$, then in a solution of $x^2\equiv D\pmod m$ necessarily $p|x$, so writing $x=px', D=pD', m=pm'$, we need to solve $px'^2=D'\pmod{m'}$. If $p\not| m'$, $p$ is invertible mod $m$, so we can bring it to the other side. If $p|m'$ (i.e. $p^2|m$), however, we need $p|D'$ as well and can remove one factor of $p$ altogether.