Factorization of polynomials over finite fields

Factorization of polynomials over finite fields is the mathematical and algorithmic problem of decomposing a polynomial with coefficients in a finite field into a product of irreducible factors. Such a decomposition is theoretically possible and unique for polynomials over any field, but practical computational algorithms for actually finding the factors have mainly been developed for polynomials over finite fields and over the rational numbers. Most modern approaches proceed in three stages: square free factorization, which uses polynomial derivatives to separate factors that repeat with different multiplicities; distinct degree factorization, which groups together irreducible factors that share the same degree; and equal degree factorization, which splits those same degree groups into their individual irreducible factors. Notable algorithms in this area include Berlekamp's algorithm, historically important but practical mainly for small finite fields, the probabilistic Cantor-Zassenhaus algorithm, and a deterministic variant developed by Victor Shoup. These factorization techniques underpin applications across coding theory, including BCH codes and cyclic redundancy checks, cryptography, including elliptic curve based public key systems, and computational number theory problems such as the discrete logarithm problem, and the same three stage structure carries over to factorization algorithms for multivariate polynomials over the rational numbers.