Jacobi Symbol
The Jacobi symbol extends the Legendre symbol to composite moduli: for n=∏p_i, (a/n)=∏(a/p_i).
Purpose
To extend quadratic-residue testing to composite moduli, used in primality testing and number-theoretic algorithms.
Mechanism
It is computed efficiently via quadratic reciprocity and Jacobi properties, without factoring n. (a/n)=1 does not guarantee that a is a quadratic residue mod n (but -1 proves it is not). The Solovay-Strassen primality test uses the Jacobi symbol.
Use cases
- Primality testing
- Quadratic residues
- Number-theoretic algorithms