Orientation
Computational Algebraic Number Theory: Field Overview
What computational algebraic number theory actually computes, why the problems are hard, and how the subject's algorithms fit together.
Engineering / MathematicsOrientation4 min readKV-MATH-0501
Algebraic number theory studies finite extensions of the rational numbers. Computational algebraic number theory asks a narrower and much more demanding question: given such a field written down explicitly, can a machine determine its arithmetic invariants in reasonable time?
The distinction matters more than it first appears. The classical theory proves that every number field has a finite class group and a unit group of known rank. Neither proof tells you how to compute either object. Constructing the maximal order of a field of degree 12, or the class group of a quadratic field with a 60-digit discriminant, requires machinery that is largely absent from the classical texts.
The shape of the subject
Nearly every algorithm in this area is built by stacking four layers. Each layer is a complete subject in its own right, and a weakness at any level propagates upward as a performance collapse rather than a wrong answer, which makes the failures hard to diagnose.
- Layer 1 — Integer and modular arithmeticMultiprecision arithmetic, GCD, modular exponentiation, square roots
- Feeds everything above it
- Layer 2 — Linear algebra and latticesGaussian elimination, Hermite and Smith normal forms, LLL reduction
- Normal forms represent modules and ideals
- LLL controls coefficient growth throughout
- Layer 3 — Polynomial algorithmsGCD, resultants, factorisation over finite fields and over Z
- Number fields are quotients by an irreducible polynomial
- Prime decomposition is polynomial factorisation mod p
- Layer 4 — Number field algorithmsMaximal orders, ideal arithmetic, class groups, units, regulators
Why the problems resist easy algorithms
Three obstructions recur, and recognising which one you are facing is usually the fastest route to a workable method.
Coefficient explosion
Intermediate values grow far beyond the size of the input and the output. Hermite normal form computation on a modest integer matrix can produce entries with thousands of digits before reducing back to a small answer. See coefficient explosion in HNF.
No polynomial-time algorithm known
Integer factorisation and class group computation both sit in the sub-exponential range. The best general methods run in L(1/3) or L(1/2) time, not polynomial time.
Dependence on unproven hypotheses
Several standard algorithms are only proved correct, or only proved fast, assuming the Generalised Riemann Hypothesis. Results carry a conditional flag that must be tracked.
The two central hard problems
Almost all the computational difficulty in the subject concentrates into two problems, and they are closely related.
| Problem | Best known complexity | Principal methods |
|---|---|---|
| Integer factorisation | Sub-exponential, L(1/3) for the number field sieve | ECM for small factors, MPQS mid-range, NFS at the top end |
| Class group and regulator | Sub-exponential, L(1/2), conditional on GRH | Buchmann's relation-collection method over a factor base |
The kinship is structural rather than superficial. Both are solved by collecting smooth relations over a factor base and then performing linear algebra on the resulting sparse matrix. Recognising this shared shape is the single most useful organising idea in the subject — see smoothness and sub-exponential complexity.
Primality versus factoring
These are genuinely different problems, and conflating them is a common source of confusion. Proving a number composite is cheap; a single Fermat test usually suffices. Proving it prime is harder but still tractable — the Jacobi sum and elliptic curve tests handle numbers of thousands of digits. Producing the factors is the hard one, and there is a wide gap between the three.
What a practitioner actually needs
- A multiprecision library you trust
- Almost never worth writing yourself. The arithmetic is subtle and the performance difference between a careful implementation and a naive one is an order of magnitude.
- An LLL implementation with an integral variant
- Floating-point LLL is faster but can fail silently on ill-conditioned bases. See integral LLL.
- Verification independent of the computation
- Analytic class number formulas and primality certificates let you check a result by a different route. Use them.
Frequently Asked Questions
Is this subject the same as computational number theory?
Do I need to understand the theory to use the algorithms?
Why are so many results conditional on the Riemann Hypothesis?
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.