3

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 !

Martin Sleziak
  • 53,687
mja
  • 1,389
  • 1
    Hint: Use Hensel's lemma, see https://en.wikipedia.org/wiki/Hensel%27s_lemma#Examples

    or cf http://math.stackexchange.com/questions/599690/hensels-lemma-and-roots-of-a-polynomial-mod-n

     – gammatester Aug 17 '16 at 13:27
  • @Crostul Could you tell me if this question is not clear? – mja Aug 17 '16 at 13:28
  • OK, now this question makes sense. Well, Hensel lemma is the tool you need. – Crostul Aug 17 '16 at 13:31
  • @Crostul Could you explain Hensel's lemma for me? A formula or a algrorithm in my case? Please. – mja Aug 17 '16 at 13:56

2 Answers2

4

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

gammatester
  • 18,827
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$.

B. Goddard
  • 1