Number Fields and Algebraic Numbers
The Polynomial Reduction Algorithm
Finding a small defining polynomial for a number field using lattice reduction on the maximal order, and why this pays for itself.
Engineering / MathematicsNumber Fields and Algebraic Numbers2 min readKV-MATH-0580
The same field admits infinitely many defining polynomials. Finding a small one is cheap and makes every subsequent computation cheaper, which makes it one of the highest-return operations available.
Why it matters
| Consequence of a large polynomial | Effect |
|---|---|
| Large discriminant | Maximal order computation requires factoring a large number |
| Large index | More primes fall into the hard decomposition case |
| Large coefficients | Bigger intermediates in every operation |
| Large element sizes | Slower ideal arithmetic and reduction |
The method
Elements of the maximal order form a lattice under the trace form or under the sum of squared conjugate absolute values. Reducing that lattice yields small elements; those that generate the whole field give small defining polynomials.
Polynomial reduction
- Obtain the maximal orderAn integral basis is required first.
- Build the latticeUse the T2 form — the sum of squared absolute values of conjugates — as the quadratic form.
- ReduceApply LLL to the basis.
- Test generatorsFor each short element, compute its characteristic polynomial and check it is irreducible of full degree.
- SelectKeep the candidate with the smallest coefficients or smallest discriminant.
The chicken-and-egg problem
Canonical forms
Reduction does not by itself give a canonical polynomial: several short elements may give equally small polynomials. Imposing a tie-breaking order on the candidates produces a canonical choice, which is what makes field identification by polynomial possible in tables — see constructing tables.
Isomorphism testing
Two fields given by different polynomials are isomorphic exactly when one polynomial has a root in the other field. Reducing both to canonical form first makes the common case — identical canonical polynomials — immediate. See field isomorphism.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 4.4.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.