2
$\begingroup$

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 !

$\endgroup$
  • 1
    $\begingroup$ Hint: Use Hensel's lemma, see en.wikipedia.org/wiki/Hensel%27s_lemma#Examples or cf math.stackexchange.com/questions/599690/… $\endgroup$ – gammatester Aug 17 '16 at 13:27
  • $\begingroup$ @Crostul Could you tell me if this question is not clear? $\endgroup$ – mja Aug 17 '16 at 13:28
  • $\begingroup$ OK, now this question makes sense. Well, Hensel lemma is the tool you need. $\endgroup$ – Crostul Aug 17 '16 at 13:31
  • $\begingroup$ @Crostul Could you explain Hensel's lemma for me? A formula or a algrorithm in my case? Please. $\endgroup$ – mja Aug 17 '16 at 13:56
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.