A residuacity test that costs no more than a GCD
The Legendre symbol records whether an integer is a square modulo an odd prime. Euler's criterion evaluates it by modular exponentiation, but the Jacobi extension to composite moduli can be evaluated far faster using quadratic reciprocity — in time comparable to a GCD, and crucially without factoring the modulus. The extension comes at a cost in meaning: a Jacobi symbol of +1 does not imply that the argument is a quadratic residue.
Learning objectives
- Define the Legendre symbol and evaluate it by Euler's criterion.
- State quadratic reciprocity and its supplementary laws.
- Implement the binary reciprocity algorithm for the Jacobi symbol.
- Explain exactly what a Jacobi value of +1 does and does not mean.
- Identify where the Kronecker extension is required.
Section 01Residues and the Legendre symbol
For an odd prime p the group (ℤ/pℤ)* is cyclic of order p−1, so exactly half its elements are squares. The Legendre symbol is
Euler's criterion gives a direct evaluation:
This costs a modular exponentiation, roughly O(log p) modular multiplications. The reciprocity algorithm below is asymptotically better, and it does not require p to be prime.
Section 02Extensions and their meaning
| Symbol | Denominator | Definition | Meaning of +1 |
|---|---|---|---|
| Legendre | Odd prime p | Euler's criterion | a is a quadratic residue mod p — exact |
| Jacobi | Odd positive n | Product of Legendre symbols over the prime factorisation of n, with multiplicity | Only that the number of prime factors with −1 is even — not residuacity |
| Kronecker | Any integer, including 0, −1 and 2 | Jacobi extended by convention on the factors 0, −1 and 2 | As Jacobi; used mainly for discriminants and character evaluation |
If the Jacobi symbol is −1, the argument is definitely a non-residue. If it is +1, nothing follows: a may be a non-residue modulo every prime factor, with the signs cancelling. Only the −1 outcome is conclusive. This asymmetry is exactly what the Solovay–Strassen primality test exploits, and misunderstanding it is a common source of incorrect residuacity code.
Section 03Evaluation by reciprocity
Quadratic reciprocity relates the symbol to its reverse, allowing the arguments to be reduced alternately in a manner closely parallel to the Euclidean algorithm:
- If n is even or n ≤ 0, reject — the Jacobi symbol requires odd positive n.
- Set a ← a mod n and s ← 1.
- While a ≠ 0:
- While a is even: set a ← a/2, and if n ≡ 3 or 5 (mod 8) set s ← −s. Supplementary law for the factor 2.
- Swap a and n; if both are ≡ 3 (mod 4), set s ← −s. Main reciprocity law.
- Set a ← a mod n.
- If n = 1 return s, otherwise return 0. n ≠ 1 means gcd(a, n) > 1.
The Jacobi symbol is computable without knowing the factorisation of the modulus. That single property is what makes it usable in primality testing, in the quadratic sieve's factor base selection, and in the definition of genus characters — all settings where the factorisation is precisely what is unknown.
ReferenceFrequently asked questions
When do I need the Kronecker symbol rather than the Jacobi symbol?
Whenever the lower argument may be even, negative or zero — which happens constantly when the argument is a field discriminant. Discriminants are congruent to 0 or 1 modulo 4 and are frequently negative, so quadratic field work uses Kronecker throughout.
Is Euler's criterion ever preferable?
Only when the modular power is needed anyway — for instance inside Tonelli–Shanks, where the exponentiation both decides residuacity and initialises the square-root search. As a standalone residuacity test, reciprocity is faster.
How does this relate to primality testing?
The Solovay–Strassen test compares the Jacobi symbol, computed by reciprocity, against Euler's criterion, computed by exponentiation. For a prime the two must agree; a disagreement proves compositeness. Miller–Rabin has since superseded it, being strictly stronger for the same cost.
NavigateContinue in this stream
Curated next steps from this page. The site also surfaces algorithmically related reading below.
ProvenanceSources and further reading
This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.