Engineering / Mathematics — Finite Fields
Square-Free Decomposition of Polynomials
Removing repeated factors using gcds with the derivative, and the characteristic p complication.
Executive summary
Squarefree decomposition splits a polynomial into parts with no repeated factors, recording the multiplicities. It uses gcds with the formal derivative and is deterministic.
In characteristic p the derivative can vanish on a non-constant polynomial, which requires a separate branch.
Learning objectives
- State the derivative-based method.
- Handle the vanishing derivative case.
- Explain why it precedes the other factorisation stages.
01The derivative criterion
Repeated factors and the derivative
An irreducible g divides gcd(f, f') to one power less than it divides f. In particular f is squarefree if and only if gcd(f, f') = 1, provided no factor has vanishing derivative.
The mechanism is the product rule: if f = g^k h then f' = k g^{k−1} g' h + g^k h', so g^{k−1} divides the derivative but g^k generally does not.
Squarefree decomposition, characteristic 0 or p not dividing exponents
monic f over a fieldsquarefree parts with their multiplicities- Compute g = gcd(f, f').
- Set w = f/g, the product of the distinct irreducible factors.
- For i = 1, 2, ...:
- Compute y = gcd(w, g), and record w/y as the product of factors of multiplicity exactly i.
- Set w = y and g = g/y.
- Continue until g is constant.
O(n²) field operations02The characteristic p complication
Vanishing derivative
Over F_q of characteristic p, f' = 0 if and only if f(X) = g(X^p) for some polynomial g.
In that case every exponent is a multiple of p, and because Frobenius is surjective on a finite field, f is a perfect p-th power: taking p-th roots of the coefficients gives f = h^p.
Detect the vanishing derivative
Check whether f' is the zero polynomial.
Extract the p-th root
Take the p-th root of each coefficient — possible because Frobenius is surjective — and divide exponents by p.
Recurse
Decompose the root, then raise every multiplicity by a factor of p.
03Why it comes first
The later stages assume a squarefree input and misbehave otherwise.
| Stage | Requires squarefree? | Failure if not |
|---|---|---|
| Distinct degree | Yes | Gcd degrees are wrong; separation unreliable |
| Equal degree | Yes | Quotient algebra has nilpotents; not a product of fields |
| Berlekamp | Yes | Kernel dimension no longer counts distinct factors |
The structural reason is uniform. A repeated factor makes the quotient algebra non-reduced, introducing nilpotent elements, so it is no longer a product of fields — and every later stage relies on that product structure.
Squarefree decomposition is cheap relative to the stages that follow, so running it unconditionally costs little and removes an entire class of failure.
04Frequently asked questions
Is squarefree the same as having distinct roots?
Over a perfect field, yes — squarefree means no repeated irreducible factor, which for a finite field means no repeated root in the algebraic closure. Over imperfect fields the notions can separate.
Why can a p-th root always be extracted over a finite field?
Because Frobenius is surjective there, so every coefficient has a unique p-th root. Over an infinite field of characteristic p this fails and the decomposition needs more care.
Does the algorithm find the multiplicities?
Yes, that is its output: each squarefree part is tagged with the multiplicity at which its factors occur, so the original polynomial is the product of the parts raised to those powers.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 475-477.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.