Square-free decomposition

also: yun, musser, squarefree

Splitting a polynomial into pairwise coprime square-free factors with their multiplicities. In characteristic zero, Yun's algorithm gets a whole multiplicity level per GCD because a polynomial and its derivative share exactly the repeated factors; in characteristic p it needs an extra branch, since the derivative of x^p is zero.

Split a polynomial into pairwise coprime square-free factors with their multiplicities:

f = i \geq 1 \prod f_{i}^{i}, g cd (f_{i}, f_{j}) = 1, f_{i} square-free

It is the first thing any factoriser does, because it reduces the general problem to the square-free case, where every irreducible occurs once and the finite-field algorithms apply.

The mechanism in characteristic zero is that a polynomial and its derivative share exactly the repeated factors, each with its multiplicity reduced by one:

g cd (f, f^{'}) = i \geq 2 \prod f_{i}^{i - 1}

Yun's algorithm exploits this to peel off a whole multiplicity level per GCD, rather than one factor at a time.

Verbatim.

> sqfree (x - 1)^2*(x + 2)^3, x
(-1 + x)^2 * (2 + x)^3

In characteristic $p$ the argument breaks: $(x^{p})^{'} = 0$ , so a $p$ -th power is invisible to the derivative and $g cd (f, f^{'}) = f$ . Musser's variant detects that case and takes a $p$ -th root before recursing, which over a prime field only moves exponents, since $a^{p} = a$ for every coefficient.