Legendre Symbol
The Legendre symbol (a/p) decides whether a is a quadratic residue modulo a prime p: 1 (yes), -1 (no), or 0 (p|a).
Purpose
To decide the solvability of quadratic equations modulo a prime; the basis of the Tonelli-Shanks algorithm.
Mechanism
(a/p) = a^((p-1)/2) mod p (Euler's criterion). Properties: (ab/p)=(a/p)(b/p), and (a/p)*(a/q) is governed by quadratic reciprocity. It decides whether x^2≡a (mod p) has a solution.
Use cases
- Quadratic residue testing
- Number-theoretic algorithms
- Cryptography
Related tools
Modular Exponentiation
Modular Exponentiation — pure client-side tool. Privacy-first, no server round-trip. TOOL
Legendre Symbol
Legendre Symbol — pure client-side tool. Privacy-first, no server round-trip. TOOL
Jacobi Symbol
Jacobi Symbol — pure client-side tool. Privacy-first, no server round-trip. TOOL
Kronecker Symbol
Kronecker Symbol — pure client-side tool. Privacy-first, no server round-trip. TOOL