Sub-exponential Class Group Computation
Buchmann's Sub-exponential Algorithm: Overview
Buchmann's algorithm for class groups and units of arbitrary number fields, its structure, and where its cost concentrates.
Engineering / MathematicsSub-exponential Class Group Computation2 min readKV-MATH-0626
Buchmann's algorithm computes the class group, unit group and regulator of an arbitrary number field in sub-exponential time. It generalises the quadratic method and shares its structure completely.
The structure
Buchmann's algorithm
- Choose a factor basePrime ideals of norm below a bound — see factor base selection.
- Collect relationsFind principal ideals that factor over the base, recording the exponent vector and the generator.
- Build the matrixRows are relations, columns are factor base primes.
- ReduceStructured elimination then Smith normal form.
- Read the class groupFrom the invariant factors.
- Recover unitsFrom the kernel — see regulator recovery.
- VerifyAgainst the analytic class number formula.
Where the cost lies
| Stage | Share of cost | Nature |
|---|---|---|
| Relation collection | Usually dominant | Embarrassingly parallel |
| Smoothness testing | Inside relation collection | Integer factorisation of ideal norms |
| Sparse linear algebra | Significant and growing | Requires tight communication; hard to parallelise |
| Unit recovery | Modest | High-precision numerical work |
| Verification | Modest | Analytic formula evaluation |
Differences from the quadratic case
Ideal reduction is harder
In rank two, form reduction is exact and cheap. In higher rank it requires lattice reduction — see ideal reduction.
Units are multi-dimensional
Rank one for real quadratic fields, but up to r_1 + r_2 - 1 in general, so the unit lattice is genuinely higher-dimensional.
Archimedean bookkeeping
Each relation carries a real vector recording logarithmic data, needed for the regulator and requiring careful precision management.
Conditionality
Practical limits
Field degree and discriminant both matter. Small degree with large discriminant is the well-understood case; high degree introduces expensive ideal arithmetic and a higher-dimensional unit lattice, and is considerably harder in practice than the complexity bound suggests.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 6.5. 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.