Almost polynomial, and for decades the only general proving method
The Jacobi sum test generalises Fermat's test to characters of higher order. Working in cyclotomic extensions of ℤ/nℤ, it verifies congruences involving Jacobi sums that must hold when n is prime. Passing them constrains the residue of n modulo a large auxiliary integer to a small set, and a final trial division stage eliminates the remaining candidates. The running time is (log n)O(log log log n) — not polynomial, but the triple logarithm makes it behave as though it were.
Learning objectives
- Explain the role of the auxiliary integers s and t.
- Describe how characters of order q generalise the Fermat test.
- Outline the structure of the basic test and the final stage.
- Compare the Jacobi sum test with ECPP on cost and certification.
Section 01The construction
Choose a squarefree t whose prime divisors q satisfy: q − 1 divides t. Set s to be the product of all such primes q. The key requirement is
which is achievable with t remarkably small — the highly composite structure means s grows very rapidly with t. That disparity is the source of the near-polynomial running time.
The primes q with q − 1 dividing a highly composite t are numerous, and their product s grows super-exponentially in t. A t of a few thousand yields an s with hundreds of digits, so the number of conditions to check grows only slowly as n grows.
Section 02Characters and the basic test
For a prime power qk dividing t, work in the cyclotomic ring ℤ[ζqk] reduced modulo n. Characters of order qk and their Jacobi sums satisfy congruences that follow from n being prime.
- Stage 01Set upChoose t and s with s² > n; verify gcd(n, st) = 1.
- Stage 02Test each pairFor each prime power dividing t and each prime dividing s, verify the Jacobi sum congruence in the appropriate cyclotomic extension.
- Stage 03Extract the conditionPassing tests establish that every prime factor of n is congruent to a power of n modulo s.
- Stage 04Final stageTest the candidate residues ni mod s for i = 1, …, t−1; if none divides n, then n is prime.
After all the cyclotomic machinery, the conclusion rests on checking at most t − 1 candidate divisors. That stage is elementary, cheap, and is what converts the accumulated congruence conditions into a proof.
Section 03Comparison with ECPP
| Aspect | Jacobi sum (APR-CL) | ECPP |
|---|---|---|
| Running time | (log n)O(log log log n), deterministic in practice | Heuristically O(log4+ε n), randomised |
| Certificate | None short — the proof is the computation | Short and independently verifiable |
| Implementation | Intricate cyclotomic arithmetic, but a fixed procedure | Requires CM curve construction and point counting |
| Sweet spot | A few hundred to a few thousand digits, where it is often fastest | Large numbers, and anywhere a certificate is required |
| Failure mode | Runs to completion | May need to retry with different curves |
A Jacobi sum proof cannot be handed to a third party for cheap verification — re-running the whole computation is the only check. Where a result must be independently verifiable, ECPP is the appropriate choice even when it is slower.
ReferenceFrequently asked questions
Why is the running time not polynomial?
Because the number of auxiliary primes, and hence the number of conditions to verify, grows slightly faster than any fixed power of log n. The growth involves a triple logarithm, which for any conceivable input behaves like a constant — so the distinction is theoretical rather than practical.
Is the test deterministic?
The core is deterministic. Some implementations randomise the search for suitable characters to improve speed, but the conclusion does not depend on chance, and the test always terminates with a definite answer.
Why did the Cohen-Lenstra refinement matter?
The original APR formulation was theoretically important but impractical. The reformulation using Jacobi sums rather than Gauss sums reduced the arithmetic to manageable size and made the test implementable — which is what turned a theoretical advance into the standard proving method for over a decade.
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.