Elements lose unique factorisation; ideals recover it
In a general ring of integers, elements do not factor uniquely into irreducibles. Dedekind's resolution is to work with ideals instead: in the maximal order every non-zero ideal factors uniquely into prime ideals. Computationally an ideal is a full-rank ℤ-submodule, stored as a Hermite normal form against the integral basis, with the norm available on the diagonal. Multiplication is a module product followed by a re-reduction to HNF.
Learning objectives
- Define an order and the maximal order, and distinguish them.
- State the unique factorisation property of ideals in a Dedekind domain.
- Represent an ideal by a Hermite normal form and by two elements.
- Multiply, invert and test containment of ideals.
- Explain the significance of the failure of unique factorisation for elements.
Section 01Orders
An order in K is a subring that is also a ℤ-module of full rank n. The ring of integers ℤK contains every order and is the unique maximal one. The equation order ℤ[θ] is the most obvious example and generally not maximal.
Unique factorisation of ideals holds only in the maximal order. In a non-maximal order the ideals dividing the conductor are not invertible, factorisation fails, and results computed as though it held are wrong. Establishing maximality — or restricting attention to ideals coprime to the conductor — is a precondition, not a detail.
Non-maximal orders are nevertheless important: the theory of binary quadratic forms of non-fundamental discriminant is exactly the theory of ideals in a non-maximal quadratic order, and Shanks's class group methods operate there.
Section 02Ideals and unique factorisation
ℤK is a Dedekind domain: Noetherian, integrally closed, and of dimension one. The consequence that matters is
Fractional ideals form a group under multiplication, with the inverse of 𝔼 given by {x ∈ K : x𝔼 ⊆ ℤK}. The class group measures how far this group is from consisting only of principal ideals.
In ℤ[√−5], the number 6 factors as 2·3 and as (1+√−5)(1−√−5), with all four factors irreducible. The factorisations are genuinely different.
The same example resolves: each of those elements generates a product of prime ideals, and the two element factorisations are two groupings of the same four prime ideals.
Section 03Representation and arithmetic
An ideal is a full-rank sublattice of ℤK, so it is stored as the Hermite normal form of its coordinate matrix against the integral basis.
| Operation | Method | Cost |
|---|---|---|
| Storage | n×n HNF matrix, often with a common denominator for fractional ideals | O(n2) integers |
| Norm | Product of the HNF diagonal entries | Free — already computed |
| Equality | Compare HNFs entry by entry | O(n2) |
| Membership | Solve against the HNF and require integer coordinates | O(n2) |
| Sum 𝔼 + 𝔽 | HNF of the stacked generator matrices | One HNF |
| Product 𝔼𝔽 | All n2 pairwise products, then HNF | O(n3) plus an HNF — the expensive operation |
| Inverse | Via the different, or by solving a linear system | One HNF plus a solve |
Every ideal in a Dedekind domain is generated by two elements, one of which can be taken to be any non-zero rational integer in the ideal — usually its norm. Storing 𝔼 = (a, α) needs O(n) data rather than O(n2) and makes multiplication far cheaper, at the cost of a conversion whenever a canonical form is needed. Production systems keep both forms.
Section 04Ideal reduction
Repeated multiplication makes ideal coefficients grow. Reduction replaces an ideal by a small ideal in the same class: find a short element α in 𝔼 using LLL on the lattice of 𝔼 under the embedding, then take (α)𝔼−1.
Without it, the ideals produced during relation collection grow until arithmetic becomes impossible. Reduction keeps every ideal bounded by roughly the square root of the discriminant, which is what makes sub-exponential class group algorithms practical.
ReferenceFrequently asked questions
Why is the two-element representation always possible?
It is a standard consequence of the Dedekind property together with the Chinese remainder theorem: choose an element whose valuation is exactly right at each prime dividing the norm, and it generates the ideal together with the norm.
How do I factor an ideal into primes?
Factor its norm as a rational integer, then for each rational prime p dividing the norm compute the primes above p and determine the valuation of the ideal at each. The factoring of the norm is the expensive step.
What breaks in a non-maximal order?
Ideals dividing the conductor are not invertible, so the fractional ideals no longer form a group and factorisation into primes fails. Algorithms designed for the maximal order will return confident, wrong answers if applied there.
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.