Modern Primality Tests
Structure of the Jacobi Sum Primality Test
The overall design of the Jacobi sum primality test, its two phases, and where its complexity comes from.
Engineering / MathematicsModern Primality Tests2 min readKV-MATH-0659
The Jacobi sum test, also known as APR-CL, proves primality by checking cyclotomic congruences for many small characters. It is the fastest method for candidates of moderate size.
The idea
If the candidate is prime, Jacobi sums satisfy congruences reflecting the action of the Frobenius map. If it is composite, those congruences fail — and the same data restricts the possible divisors so tightly that a short final search settles the matter.
The two phases
The Jacobi sum test
- Choose a squarefree integerWhose prime power divisors minus one divide it, and whose associated product exceeds the square root of the candidate.
- Check the congruencesFor each character of each prime power order, verify the Jacobi sum condition — see condition C_p.
- Derive the constraintPassing all conditions forces every divisor of the candidate to be congruent to a power of the candidate modulo the chosen integer.
- SearchCheck the resulting short list of possible divisors directly.
Parameter selection
The auxiliary integer must be highly composite with small prime factors, so that its associated product grows quickly while the individual characters stay cheap.
Complexity
The certificate problem
Where it wins
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 9.1.1-9.1.3. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.