Quadratic residues

This page is about modular arithmetic. The integers modulo p define a field, denoted Fp.\

A finite field Fp is the set of integers {0,1,...,p-1}, and under both addition and multiplication there is an inverse element b for every element a in the set, such that a + b = 0 and a * b = 1.

A quadratic residue is a number that is the result of squaring another number. In other words, a number x is a quadratic residue (modulo p) if there exists another number a such that

$$x^2 \equiv a \bmod p$$

The set of all quadratic residues modulo **p ** is called the set of quadratic residues of p.

The concept of quadratic residues is important in number theory and cryptography.

For example, the problem of finding quadratic residues is known as the "quadratic residue problem", and it is a hard problem in the sense that solving it for large integers is computationally infeasible.

This makes it useful for creating secure encryption algorithms.

Here is an example :

An integer a=21 has the following square mod 31 : a² ≡ 7 mod 31 .

As a = 21, a² = 7 , the square root of 7 is 21

Note : For the elements of Fp, not every element has a square root. In fact, what we find is that for roughly one half of the elements of Fp, there is no square root.

Theses elements are called quadratic non-residue

Interesting properties

Quadratic Residue * Quadratic Residue = Quadratic Residue
Quadratic Residue * Quadratic Non-residue = Quadratic Non-residue
Quadratic Non-residue * Quadratic Non-residue = Quadratic Residue

Legendre Symbol

There is a method to determine if an integer is a quadratic residue or not with a single calculation thanks to Legendre.

$$\frac{a}{p} \equiv a^{\frac{p-1}{2}} \bmod p$$

This equation obeys :

(a / p) = 1 if a is a quadratic residue and a ≢ 0 mod p
(a / p) = -1 if a is a quadratic non-residue mod p
(a / p) = 0 if a ≡ 0 mod p

Which means given any integer a, calculating pow(a,(p-1)//2,p) is enough to determine if a is a quadratic residue.