Cantor-Zassenhaus Algorithm

Purpose: Factor a polynomial over ${\mathbb{F}}_q$ in expected $O(n^2\log n\log q)$ — the randomized algorithm used by essentially every computer algebra system for large fields.

Three stages

Polynomial factorisation is standardly done in three passes, each stripping away one kind of structure.

1. Square-free factorisation (SFF)

Remove repeated factors. Since $\gcd (f,f^{\prime })$ captures exactly the repeated part,
$f={\prod }_i{g}_i^i$
is recovered by repeated gcds with the derivative. Cost $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.)

2. Distinct-degree factorisation (DDF)

Separate factors by their degree, using the identity

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

So for $d=1,2,3,\dots$:
$g_d=\gcd (f,x^{q^d}-x)$
collects exactly the degree-$d$ irreducible factors. Divide them out and continue. Cost: $O(n^2\log q)$ per step, using repeated squaring to compute $x^{q^d}\mathrm{mod}f$.

3. Equal-degree factorisation (EDF) — the Cantor-Zassenhaus step

Now $g$ is a product of $k$ irreducibles, all of degree $d$. Split them randomly.

For odd $q$: pick a random polynomial $h$ of degree $<\mathrm{deg}g$ and compute

$\gcd \left(g,h^{\frac{q^d-1}{2}}-1\right).$

In each CRT component ${\mathbb{F}}_{q^d}$, the value $h^{(q^d-1)/2}$ is $+1$ or $-1$ according to whether $h$ is a quadratic residue there — and these are independent across components. So the gcd captures a uniformly random non-empty proper subset with probability $\ge 1/2$, and a couple of tries split $g$.

For $q=2^m$: use the trace map $h+h^2+h^4+\cdots +h^{2^{dm-1}}$ instead, which takes values 0 and 1 independently per component.

Code sketch

// split g, a product of k >= 2 irreducibles each of degree d, over F_p (p odd)
poly edf_split(const poly& g, int d, long long p) {
    while (true) {
        poly h = random_poly(deg(g) - 1);
        poly t = powmod_poly(h, (ipow(p, d) - 1) / 2, g);
        poly r = gcd(g, t - 1);
        if (deg(r) > 0 && deg(r) < deg(g)) return r;
    }
}

Complexity

• SFF: $O(n^2)$
• DDF: $O(n^2\log q)$ — usually the bottleneck; can be improved to $\tilde{O}(n^{1.5}\log q)$ with baby-step giant-step (von zur Gathen-Shoup)
• EDF: $O(n^2\log n\log q)$ expected
• Overall: $\tilde{O}(n^2\log q)$

Contest use: roots of a polynomial mod p

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

1. $g=\gcd (f,x^p-x)$ — this is 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 the roots off.

Total $O(\mathrm{deg}f\cdot \log p)$-ish, which handles $\mathrm{deg}f$ in the thousands. It generalises Tonelli-Shanks (which is the $f=x^2-a$ case) to arbitrary polynomials.

Variants / Use Cases

• Berlekamp — the deterministic alternative, better for tiny fields
• Polynomial Factorization — the topic page
• Hensel lifting — to factor over $\mathbb{Z}$ rather than ${\mathbb{F}}_p$
• Discrete roots — solving $x^k\equiv a(\mathrm{mod}p)$