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
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
Legendre Symbol
There is a method to determine if an integer is a quadratic residue or not with a single calculation thanks to Legendre.
This equation obeys :
Which means given any integer a
, calculating pow(a,(p-1)//2,p)
is enough to determine if a
is a quadratic residue.
Last updated