Sub-exponential Class Group Computation
Ideal Reduction in Number Fields
Finding a small ideal in a given ideal class by lattice reduction, and why reduction is the enabling step for relation collection.
Engineering / MathematicsSub-exponential Class Group Computation2 min readKV-MATH-0627
Ideal reduction finds a small ideal equivalent to a given one. Without it, products of ideals grow without bound and relation collection stalls immediately.
What reduction means
Two ideals are equivalent when their quotient is principal. Reduction replaces an ideal by an equivalent one of small norm, by dividing out a suitably chosen principal ideal.
Reducing an ideal
- View the ideal as a latticeUsing the conjugate embedding with the T2 quadratic form.
- Reduce the latticeApply LLL.
- Take a short elementThe first reduced basis vector is a small element of the ideal.
- DivideDivide the ideal by the principal ideal generated by that element.
- RecordStore the element; it carries the logarithmic data needed for the regulator.
Why the T2 form
The bound achieved
Reduction is not canonical
When to reduce
Relation to the quadratic case
For quadratic fields this reduces to form reduction in the imaginary case and cycle traversal in the real case, both of which are exact and cheaper than general LLL.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 6.5.1. 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.