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.
Every page in the KEVOS library tagged Class Group. 10 pages.
Buchmann's algorithm for class groups and units of arbitrary number fields, its structure, and where its cost concentrates.
Why class group and unit computation are a single problem, what the combined algorithm produces, and how the results are verified.
What computational algebraic number theory actually computes, why the problems are hard, and how the subject's algorithms fit together.
Shanks's method factoring an integer by finding an ambiguous form in the class group of the corresponding discriminant.
Sub-exponential class group and regulator computation for quadratic fields by relation collection over a factor base.
The four fundamental computational problems for a number field, their dependencies, and what counts as a complete answer to each.
The class group as the obstruction to unique factorisation, its finiteness, and what a complete computation must produce.
Factoring via class groups of quadratic orders, and its place as the conceptual bridge to the elliptic curve method.
Practical considerations in running class group computations: parameter tuning, parallelism, precision management and diagnostics.
The ideal class group, Dirichlet's unit theorem, the regulator, Minkowski's bound, and the analytic class number formula used to verify computed values.