Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.