Orders, Ideals and Prime Decomposition
Ideal Multiplication and Division
Multiplying, inverting and dividing ideals as module operations, and controlling the growth these operations cause.
Engineering / MathematicsOrders, Ideals and Prime Decomposition2 min readKV-MATH-0587
Ideal arithmetic is module arithmetic with a stability condition. The operations are straightforward to state and expensive to perform, because each ends in a normal form computation.
Multiplication
Ideal multiplication as modules
- Form pairwise productsMultiply each basis element of one ideal by each of the other.
- AssembleCollect the resulting elements as columns of a matrix.
- NormaliseReduce to Hermite normal form, using the product of norms as the modulus.
- Reduce the denominatorTo lowest terms.
Inversion
The inverse of a fractional ideal is the set of field elements multiplying it into the order. It is computed as a colon ideal, which reduces to a linear algebra problem.
Division
Division is multiplication by the inverse. When the divisor is known to divide exactly, the colon ideal computation gives the quotient directly and more cheaply.
| Operation | Method | Relative cost |
|---|---|---|
| Product | Pairwise products then normalise | Moderate |
| Sum | Concatenate bases then normalise | Cheap |
| Inverse | Colon ideal | Moderate |
| Exact division | Colon ideal, no inversion needed | Moderate |
| Power | Repeated squaring on ideals | Grows; reduce between steps |
Growth control
Coprimality and the CRT
For coprime ideals the Chinese remainder theorem applies, allowing simultaneous congruence conditions to be solved. This is how elements with prescribed valuations at several primes are constructed, which is needed in relation construction.
Verification
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.