Quadratic reciprocity algorithm

The quadratic reciprocity theorem addresses the question of whether a number is a square modulo a prime. For an odd prime p, the Legendre symbol

is defined to be 0 if a is a multiple of p, 1 if a is a (non-zero) square mod p, and -1 otherwise. It looks like a fraction, but it's not. It acts something like a fraction, which was presumably the motivation for the notation.

The quadratic reciprocity theorem says that if p and q are odd primes, then

We can rewrite this in the less symmetric but more useful form

The idea behind quadratic reciprocity as an algorithm is that when p < q, we can use the equation above to turn a question about the existence of square roots mod q into a question about the existence of square roots mod p. This is progress because p is smaller, and we get to reduce q modulo p.

The quadratic reciprocity theorem only applies to the case of odd primes. So we need a couple more facts to complete our algorithm: how to deal with numbers that are not odd or not prime.

If the numerator" of our Legendre symbol is not prime, we factor it using the theorem that

for numbers m and n that are not multiples of p. And if we get a factor of 2 in a numerator there is a theorem that says

result

Is today a square for Jenny?

As an example, we will determine whether 112023, today's date, is a square mod 8675309, the telephone number in the 1981 pop song 867-5309/Jenny.

We begin by factoring 112023. A consequence of the factoring rule above is that we can throw away prime factors with an even exponent, and we can replace odd exponents with 1. Therefore

The full calculation is worked out in detail here. We apply the factoring rule and quadratic reciprocity over and over until we get Legendre symbols with such small numbers that we can evaluate them directly. In our case, all we need to know is that 1 is a square mod 3 and 2 is not.

The bottom line of our calculation is 1, so yes, 112023 is a square mod 8675309.

Calculating modular square roots

The quadratic reciprocity theorem gives us a way to determine whether a number has a square root mod p but it does not give us a way to calculate that root. Or rather those roots. Always two there are, like siths.

We could calculate the square roots of 112023 mod 8675309 using the Tonelli-Shanks algorithm, which is unfortunately more complicated than the quadratic reciprocity algorithm.

Mathematica can give us the roots, presumably by using some variation of the Tonelli-Shanks algorithm, or perhaps a newer algorithm. In any case,

 Reduce[x^2 == 112023, x, Modulus->8675309]

tells us the roots are 1955529 and 6719780. The latter is the negative of the former, modulo 8675309, i.e. -1955529 = 6719780 mod 8675309.

You can verify that the roots are correct by computing

1955529*1955529 - 440802*8675309 = 112023

and

6719780*6719780 - 5205053*8675309 = 112023.

The post Quadratic reciprocity algorithm first appeared on John D. Cook.