Engineering / Mathematics — Quadratic Residues
Computing the Jacobi Symbol
The Euclid-style algorithm for evaluating a Jacobi symbol in quadratic time without factoring either argument.
Executive summary
The Jacobi symbol is computed by alternating reduction, extraction of powers of two, and reciprocity swaps. The structure mirrors the Euclidean algorithm exactly.
The cost is quadratic in the operand length, faster than Euler's criterion, and it requires no factorisation.
Learning objectives
- State the algorithm and its termination argument.
- Track the sign correctly through both rules.
- Compare with Euler's criterion.
01The algorithm
Jacobi symbol
integer a, odd positive nthe Jacobi symbol (a|n)- Reduce a modulo n. If a = 0, return 1 if n = 1 else 0.
- Set result t = 1.
- While a ≠ 0:
- While a is even: divide a by 2, and if n ≡ 3 or 5 (mod 8), negate t.
- Swap a and n.
- If a ≡ 3 (mod 4) and n ≡ 3 (mod 4), negate t.
- Set a = a mod n.
- If n = 1 return t, else return 0.
O(len(n)²) bit operationsThe two sign rules correspond to the two laws. Halving invokes the supplementary law for 2, whose sign depends on n modulo 8; swapping invokes reciprocity, whose sign depends on both arguments modulo 4.
02Termination and correctness
Each swap-and-reduce step is a Euclidean step, so the arguments decrease exactly as in a gcd computation and the loop terminates in O(len(n)) iterations.
Reduce
Replacing a by a mod n leaves the symbol unchanged, since the symbol depends only on the residue class.
Extract twos
Each halving applies the supplementary law and adjusts the sign; the numerator becomes odd.
Swap
Reciprocity permits exchanging odd arguments with a sign correction.
Terminate
If the final n is 1 the symbol is the accumulated sign; if it exceeds 1 the arguments shared a factor and the symbol is 0.
03Comparison with Euler's criterion
- Jacobi algorithm
O(len(n)²)No factorisation; works for composite n - Euler's criterion
O(len(n)³)Prime moduli only; one modular exponentiation
| Situation | Method | Reason |
|---|---|---|
| Residuosity mod a prime | Jacobi algorithm | Same answer, one order faster |
| Jacobi symbol mod a composite | Jacobi algorithm | Euler's criterion does not apply |
| Inside a constant-time routine | Euler's criterion | Fixed exponentiation ladder; no data-dependent branching |
04Frequently asked questions
Why does the sign for 2 depend on n modulo 8 rather than 4?
Because the supplementary law for 2 is stated in terms of n mod 8: the symbol is +1 for n ≡ ±1 and −1 for n ≡ ±3. The residues 3 and 5 mod 8 are exactly the ±3 cases.
Does the algorithm reveal the factorisation?
No. It computes the symbol and incidentally the gcd, neither of which yields the factorisation of a composite modulus.
Can a binary variant avoid division entirely?
Yes, mirroring the binary gcd — subtraction and shifting replace division, with the same sign bookkeeping. It is often faster in practice and easier to make branch-light.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 290-291.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.