Factor the defining polynomial modulo p — usually that is the whole answer
A rational prime generates an ideal that factors into primes of ℤK with exponents ei and residue degrees fi satisfying ∑eifi = n. When p does not divide the index, Dedekind's theorem says the decomposition is read directly off the factorisation of the defining polynomial modulo p. The hard case is the finitely many primes dividing the index, which need the Buchmann–Lenstra machinery.
Learning objectives
- State the fundamental identity and interpret e and f.
- Apply Dedekind's theorem to decompose a prime.
- Identify split, inert and ramified primes.
- Compute the valuation of an element or ideal at a prime.
- Recognise when the simple algorithm does not apply.
Section 01The fundamental identity
Here ei is the ramification index and fi the residue degree, the degree of ℤK/𝔽i over Fp. The norm of 𝔽i is pfi.
| Type | Pattern | Meaning |
|---|---|---|
| Totally split | g = n, all e = f = 1 | n distinct primes of norm p |
| Inert | g = 1, e = 1, f = n | p remains prime; one prime of norm pn |
| Totally ramified | g = 1, e = n, f = 1 | pℤK = 𝔽n |
| Partially split | 1 < g < n | The general unramified case |
| Ramified | some ei > 1 | Occurs only for p dividing dK — finitely many primes |
In a Galois extension the Galois group permutes the primes above p transitively, so all ei are equal and all fi are equal: efg = n. This rigidity is what makes decomposition in cyclotomic and other Galois fields predictable from congruence conditions alone.
Section 02Dedekind's theorem and the simple algorithm
If p does not divide the index [ℤK : ℤ[θ]], the decomposition mirrors the factorisation of the defining polynomial:
- Factor T modulo p as ∏ g̅i(x)ei with each g̅i irreducible.
- For each i, lift g̅i arbitrarily to gi ∈ ℤ[x].
- Set 𝔽i ← (p, gi(θ)) — a two-element representation. The lift does not matter; different lifts give the same ideal.
- Then ei is the multiplicity and fi = deg g̅i.
- Verify ∑ eifi = n as a consistency check.
Applying this to a prime dividing the index produces ideals that are not prime, or misses primes entirely, with no internal signal of failure. Since only primes whose square divides disc(T) can divide the index, the check is cheap — but it must be made.
Section 03Valuations
The valuation v𝔽(α) is the exponent of 𝔽 in the factorisation of (α). It is computed without factoring the norm by using an element π that is a uniformiser at 𝔽 and a unit at the other primes above p.
- Precompute π ∈ 𝔽 \ 𝔽2 with π ∉ 𝔽j for j ≠ i. Constructed once per prime by the Chinese remainder theorem.
- Set v ← 0 and β ← α.
- While β ∈ 𝔽: set β ← βπ−1 · p (kept integral), and increment v.
- Return v.
Relation collection in class group algorithms produces elements whose ideals must be expressed as exponent vectors over the factor base. Each entry of such a vector is a valuation, so this routine runs enormously often and is worth optimising.
Section 04The hard primes
For p dividing the index, Dedekind's theorem does not apply. Two approaches exist, and both are covered in the Number Fields II stream.
Compute the maximal order first
Run the Round 2 algorithm to obtain ℤK, then decompose using the structure of ℤK/pℤK directly.
Buchmann–Lenstra
Decompose the separable algebra ℤK/pℤK into local factors without first computing a full integral basis.
Newton polygons
Read ramification data off the Newton polygon of T at p. Often gives the answer immediately when the polygon has distinct slopes.
ReferenceFrequently asked questions
How do I know in advance whether p ramifies?
p ramifies exactly when it divides the field discriminant dK. Since only finitely many primes divide it, all but finitely many primes are unramified and fall under the simple algorithm.
Do the exponents in the fundamental identity depend on the defining polynomial?
No. The e and f are invariants of the field and the prime. Different defining polynomials give different intermediate factorisations but the same decomposition type, which makes the identity a useful cross-check between representations.
What is the residue field used for?
It is the finite field ℤK/𝔽, of size p^f. Reduction into it converts questions about algebraic integers into finite field computations — the basis of point counting on curves and of modular methods over number fields.
NavigateContinue in this stream
Curated next steps from this page. The site also surfaces algorithmically related reading below.
ProvenanceSources and further reading
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.