Quadratic Residues Calculator
Computes the Legendre symbol (a/p) for any integer a and odd prime p, classifying a as a quadratic residue (+1), non-residue (−1), or zero (0). Useful for modular arithmetic and cryptographic analysis.
About this calculator
The Legendre symbol (a/p) classifies an integer a relative to an odd prime p: it equals 0 if p | a, +1 if a is a quadratic residue mod p (i.e., x² ≡ a (mod p) has a solution), and −1 otherwise. It is computed via Euler's criterion using modular exponentiation: (a/p) ≡ a^((p−1)/2) (mod p). This calculator uses the fast repeated-squaring algorithm, evaluating modPow(a, (p−1)/2, p) efficiently even for large inputs. A result of p−1 is interpreted as −1 (a non-residue). For a ≡ 0 (mod p) the symbol is 0. The Legendre symbol is multiplicative: (ab/p) = (a/p)(b/p), which enables factoring complex residuosity questions into simpler ones.
How to use
Compute the Legendre symbol (5/11). Reduce: 5 mod 11 = 5. Compute the exponent: (11−1)/2 = 5. Calculate 5⁵ mod 11: 5² = 25 mod 11 = 3; 3² = 9; 9 × 5 = 45 mod 11 = 1. Since the result is 1, (5/11) = +1, so 5 is a quadratic residue mod 11. Verify: 4² = 16 ≡ 5 (mod 11) ✓. Enter a = 5 and p = 11 in the calculator to confirm.
Frequently asked questions
What is the Legendre symbol and how does it differ from ordinary division?
The Legendre symbol (a/p) is a number-theoretic function, not a fraction. It outputs only three values: 0, +1, or −1, encoding whether a is divisible by p, a perfect square mod p, or a non-square mod p respectively. Unlike division, it carries no size information about a relative to p; it purely classifies the multiplicative character of a in the field ℤ/pℤ.
How does modular exponentiation make computing Legendre symbols practical for large numbers?
Direct evaluation of a^((p−1)/2) would require multiplying astronomically large integers for big p. The repeated-squaring (fast exponentiation) method reduces this to O(log p) multiplications, always keeping intermediate results reduced modulo p. For a 1024-bit prime p, this means roughly 1024 modular multiplications instead of 2^1023, making the computation instantaneous even on modest hardware.
Why is the Legendre symbol important in public-key cryptography?
The Legendre symbol underpins the Goldwasser–Micali (GM) cryptosystem, which encrypts single bits using the hardness of the quadratic residuosity problem — determining whether a random integer is a quadratic residue mod n = p × q without knowing p and q. It also drives the Jacobi symbol (a generalisation to composite moduli) used in primality tests such as the Solovay–Strassen test, which probabilistically distinguishes primes from composites.