# fastest method to solve a quadratic equation modulo p^N

What is the fastest method to solve a quadratic equation

$ax^2 + bx + c = 0 (mod p^N)$

where p is prime?

I'd start by multiplying by the inverse of $a$, to make your lead coefficient $1$: $x^2+Bx+C\equiv 0$. Then you can complete the square, replacing your coefficient $B$ with $B-p^N$ if that helps you see how to understand $\frac{B}{2}$.
This will tell you what number has to be a quadratic residue, and you can work on finding its square root. For that, you probably want to find the square root mod $p$ first, and then use Hensel's lifting lemma until you get to $p^N$.
• Of course, it's also possible that $a$ is divisible by some smaller power of $p$, in which case you first solve a linear equation mod that power of $p$... – Robert Israel Dec 26 '17 at 1:21