To find if $x^2 = a \mod p$, I use the Tonelli-Shanks algorithm. However, how do I find the roots for $x^2 = a \mod p^t$, if I have solved the previous equation?


  • $\begingroup$ Hensel's Lemma. Google it. $\endgroup$ – Timbuc Nov 7 '14 at 13:17

We can use a special case of Hensel lifting. We show how to lift a $b_1$ such that $b_1^2\equiv a\pmod{p}$ to a solution of $x^2\equiv a\pmod{p^2}$. Let $p$ be an odd prime.

Any solution of $x^2\equiv a\pmod{p^2}$ which is congruent to $b_1$ modulo $p$ has the shape $b_1+tp$. Square this. We want to have $b_1^2+2b_1tp+p^2\equiv a\pmod{p^2}$, so we want $$2b_1tp\equiv a-b_1^2\pmod{p^2}.$$ Note that $p$ divides $a-b_1^2$. Let $a-b_1^2=cp$. We want to solve $$2b_1t\equiv c\pmod{p}.$$ This is cheap to solve for $t$.

Now we have found a $b_2$ such that $b_2^2\equiv a \pod{p^2}$. We can lift this to a solution $b_3$ of $x^2\equiv a\pmod{p^3}$ by using the same method. Any such solution congruent to $b_2$ modulo $p^2$ has the shape $b_2+tp^2$. Continue.

  • $\begingroup$ You are welcome. For actual big number computations, one can tweak the algorithm for better performance. $\endgroup$ – André Nicolas Nov 7 '14 at 14:46

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.