Engineering / Mathematics — Finite Fields
Faster Square-Free Decomposition
Yun's algorithm and other improvements to squarefree decomposition, and their cost advantages.
Executive summary
The naive squarefree decomposition performs a gcd per multiplicity level. Yun's algorithm restructures the computation so the total work is proportional to a single gcd rather than to the number of levels.
The characteristic p case still requires special handling for vanishing derivatives.
Learning objectives
- State Yun's algorithm and its cost advantage.
- Compare with the naive method.
- Handle the characteristic p branch.
01The naive cost
The straightforward method computes a gcd at each multiplicity level, so a polynomial with factors of high multiplicity requires many gcds even though most of the work is repeated.
Yun's algorithm restructures the recursion so that the polynomials shrink quickly, making the total cost comparable to a single gcd computation on the original.
02Yun's algorithm
Yun's squarefree decomposition
monic f over a field of characteristic 0 or not dividing the multiplicitiessquarefree parts indexed by multiplicity- Compute u = gcd(f, f').
- Set v = f/u and w = f'/u.
- For i = 1, 2, ...:
- Compute h = w − v'.
- Compute g = gcd(v, h); this is the product of factors of multiplicity exactly i.
- Set v = v/g and w = h/g.
- Until v is constant.
O(n²), with the total gcd work comparable to one gcd on fThe improvement comes from maintaining the derivative information incrementally in w rather than recomputing gcds against the original polynomial at each level. The degrees fall quickly, so later iterations are cheap.
- Naive method
One gcd per levelRepeated work on large polynomials - Yun's algorithm
Total comparable to one gcdIncremental derivative tracking - With fast arithmetic
O(n log² n)Using fast gcd
03Characteristic p
Run Yun's algorithm
Handles all multiplicities not divisible by p.
Detect a vanishing derivative
If f' = 0, then f = g(X^p) for some g.
Extract the p-th root
Take p-th roots of coefficients — possible since Frobenius is surjective on a finite field — and divide exponents by p.
Recurse and adjust
Decompose the root and multiply every multiplicity by p.
Combine
Merge the two sets of results.
The branch is unavoidable and is a recurring feature of finite field algorithms: the characteristic interacts with exponents in ways that have no analogue in characteristic zero, and every algorithm relying on derivatives needs the extra case.
04Frequently asked questions
How much faster is Yun's algorithm in practice?
Substantially for polynomials with high multiplicities, and comparable for squarefree inputs where both terminate after one step. The worst case is where it matters most.
Does it work over the integers?
Yes, in characteristic zero it applies without the special branch. Coefficient growth remains a concern and the modular method is used as elsewhere.
Why is squarefree decomposition worth optimising?
Because it runs before every factorisation and on every input. Even a modest constant-factor improvement applies universally, and for high-multiplicity inputs the asymptotic gain is real.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 485-488.
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.