Quadratic Residue
Last modified: 2023-09-02
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.