Polynomial Factorisation
Factoring Polynomials over Algebraic Number Fields
Factoring polynomials whose coefficients lie in a number field, by reduction to the rational case via norms.
Engineering / MathematicsPolynomial Factorisation2 min readKV-MATH-0570
Factoring a polynomial over a number field is required for constructing relative extensions, splitting fields, and subfield computation. The standard method reduces it to factoring over the rationals by taking a norm.
The norm construction
Given a polynomial over a number field, take the product of its conjugates under all embeddings. The result has rational coefficients and its factorisation constrains that of the original.
The algorithm
Factoring over a number field by norms
- Ensure squarefreeOver the number field.
- Shift if necessarySubstitute X plus a multiple of the field generator until the norm is squarefree.
- Compute the normAs a resultant; a polynomial over the rationals.
- Factor the normUsing integer factorisation.
- Recover factorsEach rational factor of the norm gives a factor of the original by a GCD over the number field.
- Undo the shiftSubstitute back.
The shift
Cost
Alternatives
Direct p-adic methods
Factor modulo a prime ideal and lift within the number field. Avoids the degree blow-up of the norm but requires prime decomposition machinery.
Lattice methods
Extend the LLL-based approach to number field coefficients, using the field's own lattice structure.
Applications
Factoring over a number field is how relative extensions are constructed, how subfields are identified, and how splitting fields are built for Galois group computation.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 3.5.6. 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.