Cantor-Zassenhaus

also: equal degree factorization, distinct degree

The randomized algorithm that splits a product of irreducibles of equal degree over a finite field. For odd p, a random element raised to (p^d - 1)/2 is 1 in some of the factor fields and -1 in others, so a GCD separates the two groups, and each attempt succeeds with probability about one half.

Splits a product of distinct irreducibles that all have the same degree $d$ over ${\mathbb{F}}_p$. By the Chinese remainder theorem the quotient ring factors:

For odd $p$, exactly half the nonzero elements of each ${\mathbb{F}}_{p^d}$ are squares, and raising to $(p^d-1)/2$ sends them to $1$ and the non-squares to $-1$. A random $a$ therefore lands on $1$ in some components and $-1$ in others, and the GCD separates the two groups:

Each attempt splits with probability close to one half, so the expected number of attempts is constant. The exponent needs a bignum: $p^d$ overflows a machine word almost immediately.

> factormod x^4 + 1, 5
1 * (x^2 + 2)^1 * (x^2 + 3)^1

It is preceded by distinct-degree factorization, which separates the factors by degree first, using the identity that $x^{p^d}-x$ is the product of every monic irreducible whose degree divides $d$.

Berlekamp's algorithm · Hensel lifting

Swinnerton-Dyer polynomial

• Building a CAS in OCaml Part 4Factorization over Z by way of a finite field: Cantor-Zassenhaus, Berlekamp, Hensel lifting and subset recombination, then rational functions and partial fractions on top.