Polynomial Factorization

Factor a polynomial into irreducibles. Over a finite field this is polynomial-time; over $\mathbb{Z}$ it reduces to the finite-field case plus lifting.

Over ${\mathbb{F}}_p$ — the three stages

Every practical algorithm runs the same pipeline, each stage stripping away one kind of structure.

1. Square-free factorisation (SFF)

Remove repeated factors using $\gcd (f,f^{\prime })$:

$f={\prod }_i{g}_i^i,g_i\text{ square-free}.$

$O(n^2)$. Watch for $f^{\prime }=0$, which happens when $f$ is a $p$-th power in characteristic $p$ — then take the $p$-th root by dividing every exponent by $p$.

2. Distinct-degree factorisation (DDF)

Separate factors by their degree, using

$x^{q^d}-x=\prod \{\text{all monic irreducibles of degree dividing }d\}.$

So $g_d=\gcd (f,x^{q^d}-x)$ collects exactly the degree-$d$ irreducible factors. Compute $x^{q^d}\mathrm{mod}f$ by repeated squaring: $O(n^2\log q)$ per step.

3. Equal-degree factorisation (EDF)

Now $g$ is a product of $k$ irreducibles all of degree $d$. Split them randomly — see Cantor-Zassenhaus:

For odd $q$, pick a random $h$ and compute $\gcd \left(g,h^{(q^d-1)/2}-1\right)$. In each CRT component this value is $\pm 1$ independently, so the gcd captures a random proper subset with probability $\ge \frac{1}{2}$.

The algorithms

Algorithm	Type	Time	Best for
Berlekamp	deterministic	$O(n^3+q{n}^2)$	small $q$ (e.g. ${\mathbb{F}}_2$)
Cantor-Zassenhaus	randomized	$\tilde{O}(n^2\log q)$	large $q$ — the standard
von zur Gathen-Shoup	randomized	$\tilde{O}(n^{1.5}\log q)$	asymptotically better DDF
Kaltofen-Shoup	randomized	$\tilde{O}(n^{1.815}\log q)$	theoretical

Berlekamp’s advantage is that it reveals the number of factors immediately, as $n-\mathrm{rank}(Q-I)$ where $Q$ is the Frobenius matrix — useful for irreducibility testing without factoring.

The contest use: roots modulo $p$

By far the most common application. To solve $f(x)\equiv 0(\mathrm{mod}p)$:

1. $g=\gcd (f,x^p-x)$ — the product of all linear factors, i.e. exactly the roots.
2. Split $g$ with EDF at $d=1$ until every factor is linear.
3. Read off the roots.

vector<long long> rootsModP(Poly f, long long p) {
    Poly xp = powmodPoly({0,1}, p, f, p);              // x^p mod f
    xp[1] = (xp[1] - 1 + p) % p;                       // x^p - x
    Poly g = polyGcd(f, xp, p);                        // product of linear factors
    vector<long long> res;
    edfSplit(g, 1, p, res);                            // recursively split
    return res;
}

This generalises Tonelli-Shanks (the case $f=x^2-a$) to arbitrary polynomials, and handles degrees in the thousands.

Over the integers

1. Reduce mod a prime $p$ not dividing the leading coefficient or the discriminant.
2. Factor over ${\mathbb{F}}_p$.
3. Hensel lift the factorisation to ${\mathbb{F}}_{p^k}$ with $p^k$ exceeding twice the Mignotte bound on any factor’s coefficients.
4. Recombine — try products of the lifted factors and test whether they divide $f$ over $\mathbb{Z}$.

Step 4 is exponential in the number of factors in the worst case (the “Swinnerton-Dyer” polynomials are the classic bad case). The LLL lattice-reduction algorithm makes the whole thing polynomial-time, which is the celebrated Lenstra-Lenstra-Lovász result.

Irreducibility testing

Cheaper than factoring:

Test	Method
Over ${\mathbb{F}}_p$	$\gcd (f,x^{p^d}-x)=1$ for all $d<n$ dividing $n$
Over ${\mathbb{F}}_p$, via Berlekamp	$\mathrm{rank}(Q-I)=n-1$
Over $\mathbb{Z}$	Eisenstein’s criterion: a prime $p$ divides all coefficients but the leading one, and $p^2\nmid a_0$
Over $\mathbb{Z}$	irreducible mod some prime ⟹ irreducible over $\mathbb{Z}$ (the converse fails)
Cyclotomic polynomials	always irreducible over $\mathbb{Q}$

The “irreducible mod $p$ implies irreducible over $\mathbb{Z}$” direction is a cheap and often sufficient test.

Related computations

Task	Method
Polynomial GCD	Euclidean, $O(n^2)$; half-GCD, $O(n{\log }^{2}n)$
Resultant	via the Euclidean algorithm, or the Sylvester determinant
Discriminant	$\mathrm{Res}(f,f^{\prime })/a_n$
Squarefree test	$\gcd (f,f^{\prime })=1$
Number of irreducible factors	Berlekamp’s rank computation
Number of monic irreducibles of degree $n$ over ${\mathbb{F}}_q$	$\frac{1}{n}{\sum }_{d\mid n}\mu (d)q^{n/d}$ — the same Möbius formula as Lyndon words

See also: Cantor-Zassenhaus · Berlekamp · Hensel Lifting