Modern Primality Tests
Implementing the Jacobi Sum Test
Practical implementation of the Jacobi sum test: precomputation, cyclotomic arithmetic, and the final divisor search.
Engineering / MathematicsModern Primality Tests2 min readKV-MATH-0661
The Jacobi sum test is intricate to implement. Most of the difficulty is in the bookkeeping — parameter tables, cyclotomic arithmetic and character construction — rather than in any single hard step.
Precomputation
| Precomputed data | Why |
|---|---|
| Parameter tables by size range | Selecting the auxiliary integer at run time is a search in its own right |
| Primitive roots for the auxiliary primes | Needed to construct characters |
| Character tables | Reused across many candidates |
| Cyclotomic reduction data | Multiplication in the cyclotomic ring needs the reduction relations |
Cyclotomic arithmetic
Elements are represented as coefficient vectors over a basis of the cyclotomic ring, with all coefficients reduced modulo the candidate. Multiplication is a convolution followed by reduction using the cyclotomic relations.
The final search
The final divisor search
- Collect the constraintsEach passed condition restricts divisors to a congruence class.
- Enumerate candidatesPowers of the candidate modulo the auxiliary integer, reduced into the range below the square root.
- Trial divideTest each against the candidate.
- ConcludeFinding no divisor proves primality.
Failure handling
Testing
Practical guidance
This is a test worth using through a mature library rather than implementing. The parameter tables alone represent substantial work — see software packages.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 9.1.5-9.1.6. 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.