Sub-exponential Class Group Computation
The Sub-exponential Algorithm in Practice
Practical considerations in running class group computations: parameter tuning, parallelism, precision management and diagnostics.
Engineering / MathematicsSub-exponential Class Group Computation2 min readKV-MATH-0632
The theoretical description of Buchmann's algorithm leaves most of the engineering unspecified. The parameters that actually determine whether a computation finishes are chosen by measurement, not by the complexity analysis.
Parameters that matter
| Parameter | Effect | How to set it |
|---|---|---|
| Factor base bound | The central trade-off | Measure yield at several sizes and extrapolate |
| Large prime bound | Raises relation yield substantially | Typically a modest multiple of the base bound |
| Relation surplus | Guards against dependency | A few per cent above the base size |
| Working precision | Determines regulator correctness | Exceed the expected regulator size with margin |
| Reduction frequency | Controls ideal growth | After every multiplication, without exception |
Precision management
Parallelism
Relation collection
Embarrassingly parallel. Workers search independently and report successes; no coordination is needed beyond deduplication.
Linear algebra
Poorly parallel. Block methods help but require tight communication — see sparse elimination.
Verification
Independent of both and can run concurrently once a candidate answer exists.
Diagnostics
Several quantities should be monitored during a run, because they reveal problems long before the computation completes.
- Relation yield per unit of search time — a collapsing yield indicates a factor base that is too small.
- Rank of the accumulated matrix — should approach the base size steadily rather than plateauing early.
- Distribution of reduced ideal norms — should cluster near the expected bound, not drift upward.
- Precision loss in the accumulated logarithmic vectors.
When to stop
Termination
- Reach the target relation countSlightly above the base size.
- Compute a candidate answerRun the linear algebra.
- VerifyAgainst the analytic formula — see verification.
- Collect more if the ratio is a small integerIndicates missing relations or units.
Software
These computations are not usually implemented from scratch. Mature systems encode years of parameter tuning and edge case handling — see software packages.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 6.5.4. 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.