Orders, Ideals and Prime Decomposition
Ideal Representation by Two Elements
Representing an ideal by two generators, why two always suffice, and the trade-off against the canonical matrix form.
Engineering / MathematicsOrders, Ideals and Prime Decomposition2 min readKV-MATH-0586
Every ideal of the maximal order can be generated by two elements, one of which may be chosen to be a rational integer. This gives a far more compact representation than a full basis matrix, at the cost of canonicity.
The result
Finding the second generator
Constructing a two-element representation
- Fix the firstTake the norm, or the rational prime for a prime ideal.
- Choose a candidatePick a random element of the ideal.
- TestCheck whether the two generate the whole ideal, by computing the module they generate and comparing Hermite forms.
- RetryA random candidate succeeds with high probability; retry if not.
Trade-offs
| Operation | Two-element | Hermite matrix |
|---|---|---|
| Storage | Two elements | n by n matrix plus denominator |
| Multiplication | Four products, then normalise | Full module product |
| Equality test | Not directly possible | Matrix comparison |
| Norm | Requires conversion | Product of diagonal entries |
| Membership | Requires conversion | Triangular reduction |
Multiplication
The product of two ideals given by generators is generated by the four pairwise products. In practice the result is normalised back to two generators or converted to Hermite form, because the generator count would otherwise grow at every multiplication.
Prime ideals
Prime ideals are naturally produced in two-element form by decomposition algorithms: the rational prime below, together with a polynomial in the generator coming from a factor modulo that prime. See the simple decomposition algorithm.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 4.7.2. 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.