# Quadratic Residue

Last modified: 2023-09-02

Cryptography
Math
Modular Arithmetic

## Basic

An integer ** x** is called a quadratic residue modulo

**.**

`p`

```
a**2 = x mod p
```

### Brute Force

To calculate a quadratic residue, the following Python script is an example for that.

```
p = 71
for a in range(p):
qr = (pow(a, 2, p))
print(f"a={a} : qr={qr}")
```

### Legendre Symbol

According to Legendre Symbol, the following rules hold:

```
# `a` is a quadratic residue and `a != 0 mod p`
a**(p-1)/2 mod p == 1
# `a` is a quadratic non-residue mod p
a**(p-1)/2 mod p == -1
# `a ≡ 0 mod p`
a**(p-1)/2 mod p == 0
```

We can check if an integer is a quadratic residue or not referring to the above.

```
print(pow(a, (p-1)//2, p) == 1)
# If True, `a` is a quadratic resudiue.
```