Modern Primality Tests
Gauss Sums and Jacobi Sums
Characters, Gauss sums and Jacobi sums, and the properties that make them useful for primality testing.
Engineering / MathematicsModern Primality Tests2 min readKV-MATH-0658
Gauss and Jacobi sums are character sums with precise absolute values and predictable transformation behaviour. Those properties are what the Jacobi sum primality test exploits.
Characters
- Multiplicative character
- A homomorphism from the unit group modulo a prime to the roots of unity.
- Order of a character
- The order of its image group. Characters of order two are the Legendre symbol.
- Additive character
- A homomorphism from the additive group to the roots of unity.
Characters modulo a prime are constructed from a primitive root: sending the primitive root to a chosen root of unity determines the character completely — see primitive roots.
Gauss sums
Jacobi sums
| Property | Gauss sum | Jacobi sum |
|---|---|---|
| Lives in | A cyclotomic field including p-th roots of unity | A smaller cyclotomic field |
| Absolute value | Square root of the modulus | Square root of the modulus, typically |
| Size of the field | Degree grows with the modulus | Degree depends only on the character orders |
The relation
This identity is how Jacobi sums inherit their absolute value from Gauss sums while living in the smaller field.
Computation
Use in primality testing
The test checks whether the candidate satisfies the congruences that a prime must satisfy with respect to these sums. See the test structure.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 9.1.2. 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.