Quadratic Residues

Cryptography · Axiom Academy

Square roots modulo n and their cryptographic significance 1. Definition: What is a Quadratic Residue? Definition: An integer a is a quadratic residue modulo n if there exists an integer x such that: If no such x exists, then a is a quadratic non-residue modulo n . Think of quadratic residues as the "perfect squares" in modular arithmetic. Just as 4, 9, and 16 are perfect squares in regular arithmetic (since 2² = 4, 3² = 9, 4² = 16), quadratic residues are numbers that can be obtained by squaring something in modular arithmetic. 4² ≡ 2 (mod 7) → 2 is a QR (again) 5² ≡ 4 (mod 7) → 4 is a QR (again) 6² ≡ 1 (mod 7) → 1 is a QR (again) For odd prime p and integer a not divisible by p , the Legendre symbol is defined as: (a/p) = 1 if a is a quadratic residue mod p (a/p) = -1 if a is a quadratic non-residue mod p The Legendre symbol is multiplicative : Key Property: Exactly (p-1)/2 of the numbers 1, 2, 3, ..., p-1 are quadratic residues modulo prime p . This means exactly half are QRs and half are non-QRs. Euler's Criterion provides a computational method to determine whether a number is a quadratic residue: Euler's Criterion: For odd prime p and integer a with gcd(a, p) = 1: This is a powerful result because it converts the question "Is a a quadratic residue mod p ?" into a modular exponentiation that can be computed efficiently using fast exponentiation algorithms. Compute: 3^((11-1)/2) = 3^5 mod 11 Since the result is 1, by Euler's Criterion, 3 is a QR mod 11.

This is the written version of the interactive lesson above. See the full Cryptography course.