Sub-exponential Class Group Computation
Relation Matrix Construction
Generating relations among ideal classes, assembling the sparse matrix, and knowing when enough relations have been collected.
Engineering / MathematicsSub-exponential Class Group Computation2 min readKV-MATH-0629
Relation collection is where the time goes. Each relation is a product of factor base ideals that turns out to be principal, recorded as an exponent vector together with its generator.
Generating candidates
Generating one relation
- Form a random productTake a random product of factor base ideals with small exponents.
- ReduceApply ideal reduction, recording the element divided out.
- Test smoothnessFactor the norm of the reduced ideal against the base.
- Record on successThe exponent vector of the original product minus that of the reduced ideal is a relation.
- Discard on failureMost candidates fail; this is expected.
The matrix
Rows are relations, columns are factor base primes, entries are exponents. Each row also carries an associated element and its logarithmic embedding for the unit computation.
Matrix properties
How many relations
| Condition | Consequence |
|---|---|
| Too few relations | The computed class number is a multiple of the truth |
| Just enough | Correct, if the base generates |
| Surplus | Correct, with redundancy that helps verification |
Improving the yield
Large prime variation
Accept relations with one prime slightly outside the base, then combine pairs sharing that prime to eliminate it. Substantially raises the yield.
Sieving
Rather than testing candidates individually, sieve over a range to identify smooth values in bulk — the same technique as in the quadratic sieve.
Better starting points
Products of small-norm primes reduce to smaller ideals, raising smoothness probability.
Parallelism
Precision in the side data
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 6.5.2. 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.