[Math] How to find modulus square root

exponentiationmodular arithmeticnumber theoryradicals

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 !

Best Answer

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