How to find modulus square root?

Question

Given integers $m$, $c$ and $n$. Find $m$ such that $m^2 \equiv c \pmod n $

I used Tonelli-Shanks algorithm to caculate the square root, but in my case $n$ is not a prime number, $n = p^2,\ p$ is a prime number.

I read this page. It is said that:

In this article we will consider the case when the modulus is prime. Otherwise we can compute the square roots modulo the prime factors of $p$ and then generate a solution using the Chinese Remainder Theorem.

Using Tonelli-Shanks algorithm again, I found $m_p$ such that $m_p^2 \equiv {c} \ (\mod p)$.

I'm stuck with finding $m$ from $m_p$. That page above does not tell me clearly about how to solve that case. Please help me !

Answer 1

An algorithm to compute $\sqrt{c} \pmod {p^2}$ from $\sqrt{c} \pmod {p}$ is given below. It is a simplified version of Alg 2.3.11 (Hensel lifting) from Crandall/Pomerance: Prime Numbers, A Computational Perspective, 2nd ed., 2005 using their notation with $f(x)=c-x^2,\,$ $f'(x)=-2x.$ I include the values for $p=17, c=13$ with the root $r\equiv \sqrt{13} \equiv 8 \pmod {17}$

1.  r = sqrt(c) mod p         = 8
2.  z = (2r)^(-1) mod p       = 16
3.  x = (c-r^2)/p mod p       = -3 = 14
4.  y = x*z mod p             = 14*16 = 3
5.  r = (r + y*p) mod p^2     = 8 + 3*17 = 59 

Check: $59^2 \equiv 3481 \equiv 13 \pmod {289}$

And with some larger values using $p=10000000019, c=5:$

1. r = 8068369918
2. z = 8806837007
3. x = 3490140718
4. y = 6519460323
5. r = 65194603361938116055

See also the section Powers of odd primes of John Cook's Solving quadratic congruences and the already cited Wikipedia section from my comment (using $p=7, c=2$).

Answer 2

If $f(x)$ is a polynomial, Hensel's Lemma says that if $f(r) \equiv 0 \mod(p^k)$ then you can usually lift the solution to a solution $\mod{p^{k+1}}$. In your case, $f(x) = x^2-c$. There are 3 things that can happen. If $f^{\prime}(r) \not\equiv 0 \mod{p}$, then the solution lifts uniquely. Otherwise the solution either splits into $p$ solutions or doesn't lift at all. In your case, $f^{\prime}(r) = 2r$ and presumably your square root was not zero, so you're in the first case. Hensel says that the lifted solution is $r+tp^k$ where $t \equiv -(f^{\prime}(r))^{-1}(f(r)/p^k) \mod{p}$, that is $t \equiv -(2r)^{-1}(r^2-c)/p \mod{p}$. So most of the work is computing the modular inverse of $-2r$ modulo $p.$ Then your lifted solution is $r+tp$.