1
$\begingroup$

I'm rather confused. Based on my understanding, you can solve a quadratic in some ring if the discriminant is a square in that ring. So if I have:

$$ax^2 + bx + c \equiv 0 \pmod{n}$$

Then all I need to do is determine is where $b^2 - 4ac$ is a square modulo $n$. So if I calculate:

$$\left( \frac{b^2 - 4ac}{p} \right)$$

Where $\left( \frac{p}{q} \right)$ is the Legendre symbol (not sure how to actually write it). If I get $1$, then I can solve it, and if I get $-1$, then I can't. Why then do I need the Law of Quadratic Reciprocity, which, as I understand, is simply that:

$$\left( \frac{p}{q} \right)\left( \frac{q}{p} \right) = (-1)^{\frac{p-1}{2} \frac{q-1}{2}}$$

But I could also simply calculate it by trying every number modulo $n$, no? So is the Law of Quadratic Reciprocity necessary for determining whether a given quadratic can be solved, or does it just speed up the calculation?

$\endgroup$
1
  • $\begingroup$ (I've fixed the statement of QR in your question, which I'm assuming was just a typo.) $\endgroup$ Mar 27, 2017 at 17:01

1 Answer 1

3
$\begingroup$

It just speeds up the calculation, but it speeds up calculation rather dramatically. To compute $\left(\frac ap\right)$ by checking each value $0 \le b < p$ to see if $a \equiv b^2 \pmod p$, we need $O(p)$ steps.

On the other hand, we have an $O(\log a \log p)$ algorithm by doing two things: using quadratic reciprocity, and extending our calculations to the Jacobi symbol when the bottom number is composite. (It's essentially the Euclidean algorithm, where at every step we also track the sign changes that follow from QR.)

If we just use quadratic reciprocity, but stick to the Legendre symbol, it's still slow, since for something like $\left(\frac{15}{17}\right)$ we first have to do the hard computational work of factoring $15$ into $3\cdot 5$.

(But occasionally, the Legendre symbol is also useful in proofs, not just for computation.)


Note that all this will just tell you whether a square root exists, not find it for you. But even if you want to do the latter, either the Tonelli–Shanks algorithm or Cipolla's algorithm is still faster than brute force for large primes $p$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .