What is the fastest method to solve a quadratic equation
$ax^2 + bx + c = 0 (mod p^N) $
where p is prime?
Answer
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$.
Does that answer your question, or do you need more details on any of those steps?
No comments:
Post a Comment