Daniel Panario, University of Toronto

Factoring polynomials over finite fields

In this talk, we survey known algorithms for the factorization of univariate polynomials over finite fields. First, we present the main ideas behind Berlekamp's algorithm. Then, we give a general factoring algorithm composed by three stages (squarefree, distinct-degree and equal-degree factorization) which provides a framework to several other algorithms. We discuss best known asymptotical time algorithms, current bottlenecks and recent results.