Solve quadratic equations modulo prime powers

Question

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?

Thanks

Answer 1

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.