Modern Primality Tests
Checking the Condition C_p
The central congruence condition of the Jacobi sum test, what it asserts, and how it is verified in practice.
Engineering / MathematicsModern Primality Tests2 min readKV-MATH-0660
The condition at the heart of the Jacobi sum test asserts that the candidate acts on Jacobi sums the way a prime would. Verifying it for enough characters is what constrains the divisors.
What the condition says
For a prime, raising a Jacobi sum to the power of the candidate has a predictable effect: it equals a root of unity times the sum with its character argument permuted. The condition asserts exactly this.
Verification
Verifying the condition
- Construct the Jacobi sumIn the cyclotomic ring, from the auxiliary prime and character orders.
- Raise to the powerBy binary powering in the cyclotomic ring modulo the candidate.
- Apply the automorphismPermute the cyclotomic basis accordingly.
- CompareThe two must differ by a root of unity.
- Record the rootThe specific root found carries the information used for the divisor constraint.
The arithmetic
Special cases
What passing establishes
Each successful check constrains the possible prime divisors of the candidate to lie in a specific congruence class. Accumulating constraints across all characters leaves only a short list, which the final phase checks directly.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 9.1.4. 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.