Software, Tables and Sources
Choosing an Algorithm: Decision Guide
A consolidated decision guide across the main computational tasks in this collection.
Engineering / MathematicsSoftware, Tables and Sources2 min readKV-MATH-0679
This page consolidates the selection guidance distributed across the collection. Each branch links to the page treating that choice in full.
Integer arithmetic
| Task | Choice |
|---|---|
| Multiplication | Schoolbook at small sizes; Karatsuba above the measured crossover |
| Repeated modular arithmetic with a fixed modulus | Montgomery reduction |
| GCD | Binary GCD at small sizes; Lehmer above |
| Many inversions at once | Simultaneous inversion |
Linear algebra and lattices
| Task | Choice |
|---|---|
| Integer matrix normal form | Hermite with a modular bound; LLL-based when growth is severe |
| Group structure from relations | Smith normal form |
| Short lattice vectors | LLL; enumeration when exactness is required |
| Large sparse system over a small field | Structured elimination then an iterative method — see the linear algebra stage |
Polynomials
- Factoring a polynomial
- Over a small finite fieldBerlekamp
- Over a large finite fieldThe GCD pipeline
- Over the integersZassenhaus with an LLL fallback
- Over a number fieldNorm reduction
Number fields
| Task | Choice |
|---|---|
| Maximal order | Round 2, after polynomial reduction |
| Prime decomposition, p not dividing the index | Simple decomposition |
| Prime decomposition, index divisor | Buchmann-Lenstra or Newton polygons |
| Class group, quadratic, small discriminant | Form enumeration |
| Class group, general or large | Buchmann |
| Galois group | Resolvents, after discriminant and cycle type tests |
Primality and factoring
These are treated in full on their own pages: the primality landscape and the factoring comparison.
The general principles
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — collection orientation material. 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.