Quadratic Residues

Sometimes we might be interested in the question of whether certain numbers are congruent to the square of some other number modulo a prime. One option to answer this question is trial and error, for instance the question of whether 3 is congruent to the square of a number mod 7:

x x2 (Raw) x2(mod7)

0 0 0

1 1 1

2 4 4

3 9 2

4 16 2

5 25 4

6 36 1

We can see that there’s no 3 here in this table. What I love about Silverman is that he has us “experiment” with different numbers to really see the patterns we care about. So in the spirit of this we can try another example.

x x2(mod11)

0 0

1, 10 1

2, 9 4

3, 8 9

4, 7 5

5, 6 3

 

1, 2, and 4 are Quadratic Residues (QR), while 3, 5, and 6 are Non-residues (NR). 3 is not a square mod 7. In our p=11 experiment, Quadratic Residues are 1, 3, 4, 5, 9. The Quadratic Non-Residues are 2, 6, 7, 8, 10. If you were a number living in the world of Modulo 11, and you were a 7, you could never be the result of a square. You are an impossible value.

So in a nutshell, that’s what quadratic residues are. Easy enough to understand, but why do we care about them? This is one of those cool cases in math where doing something one way is very easy, but reversing the operation is incredibly hard. For a single prime, these patterns are easy to find. But if we multiply two massive primes together and create a composite number, finding out if a number is a square becomes a hard puzzle for anyone who doesn't know the secret prime factors. This trapdoor—easy to do one way, hard to reverse—is the engine behind Zero Knowledge Proofs and the encryption that keeps your credit card safe online