Factorization of polynomials over finite fields

Summary

Over a finite field every polynomial can be factored into irreducibles by efficient algorithms. The usual methods remove repeated factors, then group the irreducible factors by degree, then split each group. They rest on the fact that $x^{q^d} - x$ is the product of all monic irreducible polynomials over $\F_q$ whose degree divides $d$. These algorithms are also the first step of factoring over $\Z$ and $\Q$, and they are used in coding theory and cryptography.