Class Group and Unit Computation in General Number Fields

Executive summary

One relation matrix, four answers

The general algorithm chooses a factor base of small prime ideals, generates random ideals that factor completely over it, and records each factorisation as a relation. The Smith normal form of the resulting matrix gives the class group; its kernel gives the units and hence the regulator. Under GRH the factor base can be taken far smaller than Minkowski's bound, which is what makes the method sub-exponential — and what makes the result conditional.

Learning objectives

Select a factor base and state the GRH-conditional bound.
Generate relations by reducing random ideals.
Extract the class group from the relation matrix.
Extract units and the regulator from its kernel.
Verify the result and solve the principal ideal problem.

Section 01Factor base selection

The factor base is the set of prime ideals of norm below a bound B. Unconditionally B must reach Minkowski's bound to guarantee generation of the class group; under GRH a bound of order (log|d_K|)² suffices.

Minkowskiunconditional, exponentially large

O(log²|d_K|)GRH-conditional, practical

L[1/2]resulting complexity

The bound decides the conditionality

Choosing the GRH bound is what makes the algorithm feasible and what makes its output conditional. A computation run to Minkowski's bound is unconditional but usually infeasible; one run to the GRH bound is fast and must be reported as conditional. There is no middle option, and the choice must be recorded.

Section 02Relation collection

AlgorithmRelation collectionin: factor base → out: a relation matrix and generating elements

Choose random exponents and form the ideal 𝔼 = ∏ 𝔽_i^a_i over the factor base.
Reduce 𝔼: find a short element α in the ideal lattice by LLL and replace 𝔼 by (α)𝔼⁻¹. Reduction keeps norms bounded by roughly √|d_K|.
Attempt to factor N(𝔼) over the factor base primes. If it does not split completely, discard and return to step 1.
Record the relation: the exponent vector, together with the element α and its logarithmic embedding.
Repeat until there are comfortably more relations than factor base elements.

Reduction is what makes this possible

Without ideal reduction the norms grow with each multiplication and never factor over a fixed factor base. LLL-based reduction bounds them, which is the precise point at which lattice reduction becomes indispensable to class group computation.

Section 03Extracting the invariants

From the matrixThe class group

The Smith normal form of the relation matrix gives the invariant factors, hence the structure of Cl(K) and the class number as their product.

From the kernelThe units and the regulator

A kernel vector corresponds to a product of the generating elements that is a unit. The logarithmic embeddings of independent such units form a matrix whose determinant is the regulator.

Stage 01Assemble the matrixRows are relations, columns are factor base primes.
Stage 02Smith normal formInvariant factors give the class group structure.
Stage 03KernelKernel vectors give units; take r independent ones.
Stage 04RegulatorDeterminant of the logarithmic embedding matrix, to certified precision.
Stage 05VerifyCompare hR against the analytic estimate; if short by a factor, collect more relations.

A subgroup is the default failure mode

Too few relations yields a proper subgroup of the class group and a proper subgroup of the units — and therefore a class number too small and a regulator too large, in a compensating way that leaves the product looking plausible. Only comparison against an independent analytic estimate reliably detects it.

Section 04The principal ideal problem

Deciding whether a given ideal is principal, and if so finding a generator, is a distinct problem solved with the same machinery: reduce the ideal, factor it over the factor base, and solve the resulting linear system against the relation matrix. A solution yields a generator as a product of the recorded elements.

Generators can be astronomically large

The generator produced is a product of powers of relation elements and may have enormous height. It is stored in compact form — as the exponent vector over the relation elements — and expanded only if genuinely required, which it usually is not.

ReferenceFrequently asked questions

How large must the factor base be?

Large enough that random reduced ideals factor over it with workable probability, and small enough that the linear algebra remains tractable. The optimum balances the two and is found by the same L-notation analysis that governs the quadratic sieve.

Why are both the class group and the units obtained together?

Because a relation says that a specific product of factor base ideals is principal, generated by a specific element. The exponent vectors give the class group; the elements attached to kernel combinations give units. The two are different readings of the same data.

Can the result ever be certified unconditionally?

Yes, by re-verifying with a factor base extended to Minkowski's bound, which is feasible only for small discriminants. Otherwise the standard practice is to report the result as correct under GRH, together with the analytic consistency check.

NavigateContinue in this stream

Curated next steps from this page. The site also surfaces algorithmically related reading below.

ProvenanceSources and further reading

This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.