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$.

Does that answer your question, or do you need more details on any of those steps?

  • $\begingroup$ 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. $\endgroup$ – Talib Dec 25 '17 at 23:20
  • $\begingroup$ 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... $\endgroup$ – G Tony Jacobs Dec 25 '17 at 23:39
  • $\begingroup$ This is a pretty good resource on Hensel: brilliant.org/wiki/hensels-lemma $\endgroup$ – G Tony Jacobs Dec 25 '17 at 23:43
  • 1
    $\begingroup$ 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$... $\endgroup$ – Robert Israel Dec 26 '17 at 1:21
  • 1
    $\begingroup$ @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? $\endgroup$ – G Tony Jacobs Dec 26 '17 at 1:27

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.