One discipline, four hard problems, one enabling technique
Computational algebraic number theory turns the abstract objects of number theory — rings of integers, ideals, class groups, unit groups — into data structures that a machine can hold, and the theorems about them into procedures a machine can run. The discipline rests on a deep layering: every high-level computation about a number field decomposes into polynomial arithmetic, which decomposes into linear algebra and lattice reduction, which decomposes into multiprecision integer arithmetic. Get a lower layer wrong and every result above it is silently wrong.
Learning objectives
- Identify the four central computational tasks associated with a number field.
- Explain why lattice reduction is the single most load-bearing technique in the subject.
- Trace any high-level computation down through the algorithmic layer stack.
- Distinguish polynomial-time, sub-exponential and exponential regimes in this domain.
- Select the correct KEVOS knowledge stream for a given computational problem.
- Recognise where results are conditional on unproven hypotheses such as GRH.
Section 01The layer stack
Almost nothing in this field is computed directly. A request as innocuous as “what is the class number of this field?” resolves into a chain of sub-computations, each of which is a substantial algorithm in its own right. Understanding this stack is the fastest route to understanding both the subject and its failure modes.
- Stage 01Multiprecision arithmeticIntegers of arbitrary size, modular reduction, GCD. Every layer above assumes it is exact.
- Stage 02Linear algebra & latticesHermite and Smith normal forms, Gram–Schmidt, LLL reduction over ℤ.
- Stage 03Polynomial algorithmsGCD, resultants, factorisation modulo p, Hensel lifting, factorisation over ℤ.
- Stage 04Number field machineryMaximal orders, ideal arithmetic, prime decomposition, valuations.
- Stage 05InvariantsClass group, regulator, fundamental units, Galois group, L-functions.
The dependency runs strictly downward. Rounding error in a Gram–Schmidt step propagates into an LLL basis, which corrupts a polynomial factorisation, which yields a wrong prime decomposition, which yields a class group that looks entirely plausible and is entirely false. This is why implementations in this field are unusually conservative about exactness and unusually fond of independent verification.
The characteristic risk in computational number theory is not the crash — it is the plausible wrong answer. A class group of the right approximate size with the wrong structure carries no diagnostic signal. Verification steps are therefore not optional extras; they are part of the algorithm.
Section 02The four central tasks
For a number field K given by a defining polynomial, four computations dominate every practical application. They are ordered here by difficulty, and each generally depends on the ones before it.
Find the ring of integers and an integral basis. Reduces to factoring the polynomial discriminant — which is why this task inherits the hardness of integer factoring.
For a rational prime p, find the prime ideals above it with their ramification indices and residue degrees. Polynomial time once the maximal order is known.
The finite abelian group measuring failure of unique factorisation. Computed from a relation matrix by Smith normal form; sub-exponential in the best known methods.
A fundamental system of units and the covolume of the unit lattice. Computed alongside the class group; the numerical conditioning here is delicate.
Tasks 3 and 4 are conventionally computed together, because the same relation-collection phase produces the data for both. Their outputs are linked by the analytic class number formula, which supplies the single most valuable independent check available in the subject: the product h · R can be estimated analytically from the Dedekind zeta function and compared against the computed values.
Section 03Why lattice reduction is everywhere
If one technique had to be identified as the engine of modern computational number theory, it would be lattice basis reduction. The LLL algorithm produces, in polynomial time, a basis of a lattice whose vectors are short and near-orthogonal — not optimally short, but short enough, and provably so.
Polynomial factorisation over ℤ
Recombination of modular factors becomes a short-vector problem, converting an exponential search into a polynomial-time reduction.
Algebraic dependence
Given a floating-point number, recover a plausible minimal polynomial — the basis of integer relation detection.
Integer kernels and images
Compute kernels of integer matrices without coefficient explosion.
Ideal reduction
Find small representatives of ideal classes, which is what makes class group relation collection tractable.
The number field sieve
Lattice sieving over the sieving region is the dominant cost of the fastest known general factoring algorithm.
Subfield detection
Locate subfields of a number field by finding short vectors encoding algebraic relations.
Section 04Complexity regimes
Three regimes appear repeatedly. Knowing which one a problem inhabits sets realistic expectations about input sizes.
| Regime | Notation | Characteristic problems | Practical ceiling |
|---|---|---|---|
| Polynomial | O(nk) | GCD, modular exponentiation, HNF/SNF, prime decomposition given ℤK, factorisation modulo p | Very large inputs; usually limited by memory, not time |
| Sub-exponential | LN[1/2] to LN[1/3] | Integer factoring (QS, NFS), discrete logarithms, class groups and regulators of quadratic fields | Hundreds of decimal digits with serious compute |
| Exponential | O(2n), O(√N) | Exhaustive Galois group determination in high degree, baby-step giant-step over large groups, shortest-vector in high dimension | Small parameters only |
Many practical algorithms for class groups and regulators are only proven correct, or only achieve their stated complexity, under the Generalised Riemann Hypothesis. Results should be reported as conditional unless an unconditional verification step has been run. This is a reporting discipline, not a mathematical technicality.
Section 05How this knowledge stream is organised
The KEVOS Mathematics library divides this subject into ten linked streams. Each page is standalone; the streams describe reading order for someone working through the whole domain.
| Stream | Covers | Depends on |
|---|---|---|
| Foundational algorithms | Multiprecision arithmetic, GCD, CRT, modular roots, symbols | — |
| Linear algebra & lattices | Gaussian elimination, HNF, SNF, Gram–Schmidt, LLL | Foundations |
| Polynomial algorithms | GCD in UFDs, resultants, factorisation, Hensel lifting | Foundations, lattices |
| Number fields I | Algebraic numbers, orders, ideals, prime decomposition | Polynomials |
| Quadratic fields | Forms, class numbers, infrastructure, Cohen–Lenstra | Number fields I |
| Number fields II | Maximal orders, Galois groups, general class groups | Number fields I |
| Elliptic curves | Group law, complex multiplication, L-functions | Polynomials |
| Primality | Compositeness tests, Pocklington, Jacobi sum, ECPP | Foundations |
| Factoring | ρ, SQUFOF, p−1, ECM, quadratic sieve, number field sieve | Foundations, number fields |
| Resources | Software packages, table sourcing policy | — |
ReferenceFrequently asked questions
Is this subject the same as cryptography?
No, though they overlap heavily. Cryptography consumes results from computational number theory — primality proving, factoring hardness, elliptic curve group orders — but the discipline itself is concerned with computing invariants of number fields, which has no cryptographic purpose. The shared machinery is the reason a cryptographic engineer and a number theorist reach for the same libraries.
Where should a newcomer start?
With multiprecision arithmetic and the Euclidean algorithm, then modular exponentiation, then lattice reduction. Lattice reduction is the earliest point at which the subject stops looking elementary and starts delivering surprising results, so it repays early study.
Why do results need to be marked conditional?
Because the fastest algorithms for class groups and regulators assume the Generalised Riemann Hypothesis in order to bound the size of a generating set of prime ideals. Without that assumption the algorithm may terminate with a subgroup of the true class group rather than the class group itself. The output is still useful, but its status must be recorded.
NavigateContinue in this stream
Curated next steps from this page. The site also surfaces algorithmically related reading below.
ProvenanceSources and further reading
Standard references for the field include Cohen's A Course in Computational Algebraic Number Theory (Springer GTM 138), Pohst and Zassenhaus on algorithmic algebraic number theory, and Knuth's The Art of Computer Programming volume 2 for the arithmetic layer.
This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.