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.
Last updated: September 2026
Legendre Symbol
-1
Formula below · 2 sources (oeis.org, Wikipedia) · Updated Sep 2026
Compare with similar
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.
Related calculators
Sources & references
Think a result is wrong? Report a problem with this calculator.