Solving the congruence $b\equiv x^2$ mod $p$ is pretty simple using either closed formulas (e.g. if $p\equiv 3$ mod $4$, then $x=b^{(p+1)/4}$ is a solution) or the Tonelli-Shanks algorithm.

But what about the congruence $b\equiv x^2$ mod $p^m$ for some $m\in\mathbb Z_{\ge1}$ ? My idea is the following: Assuming I already know a solution $x_0$ to $b\equiv x^2$ mod $p$, then in order to solve, say, $b\equiv x^2$ mod $p^2$ all I need to do is check if one of $x_0,\ x_0+p,\ x_0+2p,\ \ldots,\ x_0+ (p-1)p$ is a solution. So I have to check at most $p$ values. And in general I can solve $b\equiv x^2$ mod $p^m$ by taking a solution from $b\equiv x^2$ mod $p^{m-1}$ and, again, checking at most $p$ values.

Is this a viable technique or is my idea rubbish?

  • 2
    $\begingroup$ Look at this question and its comments. $\endgroup$ – ccorn Aug 10 '13 at 12:49
  • $\begingroup$ It might be helpful to recall that the multiplicative group of every finite field is cyclic. Hence, one can deal with powers of a given primitive to translate the problem into a simple congruence. $\endgroup$ – Jonathan Y. Aug 10 '13 at 19:18
  • 3
    $\begingroup$ The finite field with $p^m$ elements is not the same thing as taking the integers modulo $p^m$. $\endgroup$ – Pgatti Oct 10 '16 at 16:00

Your Answer

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

Browse other questions tagged or ask your own question.