Exploit Notes

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.

References