Quadratic Fields
Sub-exponential Class Group Computation for Quadratic Fields
Sub-exponential class group and regulator computation for quadratic fields by relation collection over a factor base.
Engineering / MathematicsQuadratic Fields2 min readKV-MATH-0608
Enumeration and cycle traversal both cost roughly the square root of the discriminant. The sub-exponential method collects relations over a factor base instead, reducing the exponent from one half to the sub-exponential range.
The method
Sub-exponential class group computation
- Build the factor basePrime ideals of norm below a bound, equivalently forms with small first coefficient.
- Generate random formsCompose random products of factor base elements and reduce.
- Test smoothnessA reduced form whose first coefficient factors over the base gives a relation.
- Assemble the matrixRows are relations, columns are factor base primes.
- ReduceStructured elimination then Smith normal form.
- Read the resultsInvariant factors give the class group; the kernel gives the regulator.
Why reduction produces smooth forms
The real quadratic complication
Comparison
| Method | Cost | Range |
|---|---|---|
| Form enumeration | Square root of the discriminant | Up to about 12 digits |
| Cycle traversal | Square root of the discriminant | Real fields, modest size |
| Analytic formula | Grows with required precision | Verification, small cases |
| Sub-exponential relations | L(1/2), conditional on GRH | Large discriminants |
Relation to factoring
The general case
The same approach extends to arbitrary number fields as Buchmann's algorithm, with ideals in place of forms and a more elaborate reduction step.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 5.3.4-5.4.3. 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.