Sub-exponential Class Group Computation
Factor Base Selection and Smoothness
Choosing the factor base for class group computation, the smoothness trade-off, and how base size interacts with the linear algebra.
Engineering / MathematicsSub-exponential Class Group Computation2 min readKV-MATH-0628
The factor base is the set of prime ideals over which relations are expressed. Its size controls a trade-off that determines the entire running time of the algorithm.
The trade-off
| Larger factor base | Smaller factor base |
|---|---|
| Relations easier to find | Relations harder to find |
| More relations needed | Fewer relations needed |
| Larger matrix; harder linear algebra | Smaller matrix |
| Higher smoothness probability | Lower smoothness probability |
Construction
Building the factor base
- Choose a norm boundGuided by the theory and by measurement.
- Enumerate rational primesUp to the bound.
- Decompose eachFind the primes above it — see simple decomposition.
- Filter by normKeep prime ideals whose norm is below the bound; inert primes of high residue degree are usually excluded.
- IndexStore in a structure supporting fast smoothness testing.
The generation guarantee
Under GRH, prime ideals of norm below a bound proportional to the square of the logarithm of the discriminant generate the class group. This is what makes a small factor base sufficient — see Minkowski and Bach bounds.
Smoothness
An ideal is smooth over the base when its norm factors entirely over the corresponding rational primes and every prime ideal appearing is in the base.
Testing smoothness
Practical sizing
In practice the base is sized by measurement rather than by the theoretical optimum: run a short relation collection at several base sizes and extrapolate. The theoretical bound then serves as a completeness guarantee rather than as the operative sizing rule.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 6.5.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.