# 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?

## 1 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?

• Please tell me what is the fastest method of finding square root mod p. I will also appreciate if you guide me to an novice's explanation for Hensel's lifting lemma. – Talib Dec 25 '17 at 23:20
• First, you need to know whether your number even is a square - Legendre symbols are good for that. If it is, you can use a primitive root to find a square root for it. Whether this is really quicker than trial-and-error will vary from prime to prime. For the Hensel stuff, let me see what I can either find, or write up quickly... – G Tony Jacobs Dec 25 '17 at 23:39
• This is a pretty good resource on Hensel: brilliant.org/wiki/hensels-lemma – G Tony Jacobs Dec 25 '17 at 23:43
• 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
• @RobertIsrael, because when someone isn't particularly used to this, they might find completing the square easier that way. Quick, what's 15/2 mod 19? Did you add or subtract 19 in your head to come up with the answer? – G Tony Jacobs Dec 26 '17 at 1:27