Cantor–Zassenhaus algorithm

In computational algebra, the Cantor–Zassenhaus algorithm is a well known method for factorising polynomials over finite fields (also called Galois fields).

The algorithm consists mainly of exponentiation and polynomial GCD computations. It was invented by David G. Cantor and Hans Zassenhaus in 1981.

It is arguably the dominant algorithm for solving the problem, having replaced the earlier Berlekamp's algorithm of 1967. It is currently implemented in many well-known computer algebra systems.

The Cantor–Zassenhaus algorithm takes as input a squarefree polynomial ${\displaystyle f(x)}$ (i.e. one with no repeated factors) of degree n with coefficients in a finite field ${\displaystyle \mathbb {F} _{q}}$ whose irreducible polynomial factors are all of equal degree (algorithms exist for efficiently factorising arbitrary polynomials into a product of polynomials satisfying these conditions, for instance, ${\displaystyle f(x)/Gcd(f(x),f'(x))}$ is a squarefree polynomial with the same factors as ${\displaystyle f(x)}$, so that the Cantor–Zassenhaus algorithm can be used to factorise arbitrary polynomials). It gives as output a polynomial ${\displaystyle g(x)}$ with coefficients in the same field such that ${\displaystyle g(x)}$ divides ${\displaystyle f(x)}$. The algorithm may then be applied recursively to these and subsequent divisors, until we find the decomposition of ${\displaystyle f(x)}$ into powers of irreducible polynomials (recalling that the ring of polynomials over any field is a unique factorisation domain).

...
Wikipedia