# Quadratic residues

{% hint style="info" %}
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`.
{% endhint %}

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`**.

{% hint style="info" %}
**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**.
{% endhint %}

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

{% hint style="warning" %}
Note : For the elements of `Fp`, <mark style="color:red;">**not every element has a square root**</mark>. 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**
{% endhint %}

## 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.