Polynomial Factorisation
Squarefree Factorisation of Polynomials
Separating repeated factors using the derivative, and the modification required in positive characteristic.
Engineering / MathematicsPolynomial Factorisation2 min readKV-MATH-0563
A polynomial is squarefree when no irreducible factor appears more than once. Separating the repeated factors is the cheapest stage of factorisation and the one that every later stage assumes has run.
The characteristic zero case
A repeated factor of a polynomial also divides its derivative. The GCD of the polynomial with its derivative therefore collects exactly the repeated part.
Squarefree decomposition
- DifferentiateCompute the formal derivative.
- Take the GCDThe GCD collects each repeated factor with multiplicity one less than in f.
- DivideThe quotient is the product of the distinct irreducible factors.
- RecurseRepeating on the GCD separates factors by their exact multiplicity.
The characteristic p complication
The repair uses the fact that a polynomial with zero derivative is a p-th power in disguise: every exponent is divisible by p, so the polynomial equals the p-th power of the polynomial obtained by dividing exponents by p and taking p-th roots of coefficients.
Squarefree factorisation in characteristic p
- DetectIf the derivative is zero, the polynomial is a p-th power.
- Take the p-th rootDivide exponents by p; take p-th roots of coefficients, which over a finite field is the inverse Frobenius.
- RecurseFactor the root and raise multiplicities by p.
- Handle partial casesA factor may be a p-th power while the whole polynomial is not; handle the two parts separately.
Cost
Other uses
Squarefree decomposition also extracts the minimal polynomial from a characteristic polynomial — see the Hessenberg method — and is used in prime decomposition to detect ramification.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 3.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.