# 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

is a quadratic residue (modulo **x**

) if there exists another number **p**

such that**a**

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

is **7****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