# Square roots in finite fields, i.e. mod $p^m$

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?

• Look at this question and its comments. – ccorn Aug 10 '13 at 12:49
• 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. – Jonathan Y. Aug 10 '13 at 19:18
• The finite field with $p^m$ elements is not the same thing as taking the integers modulo $p^m$. – Pgatti Oct 10 '16 at 16:00