I'll describe a new algorithm for univariate polynomial factorization over F_q that uses roughly O(n^{1.5} + nlog q) field operations, when the characteristic is at most n^{o(1)}. This (asymptotically) beats all previous algorithms when log q < n and matches them when log q >= n.
The improvement comes from a new algorithm for "modular composition," which is the bottleneck in modern polynomial factorization algorithms. Modular composition is the problem: given degree n polynomials f(x), g(x), h(x), compute f(g(x)) mod h(x). It is a very natural operation on polynomials, which lies at the core of algorithms for basic algebraic problems like irreducibility testing, manipulating normal bases, constructing minimal polynomials, and others.
The only nontrivial algorithm for modular composition (Brent & Kung 1978) has a running time that is far from optimal. I'll describe a new algorithm whose running time is optimal up to lower order terms, and which uses completely different ideas (inspired by recent work in coding theory). This in turn leads to the improved algorithm for polynomial factorization. I'll also highlight a self-contained open problem whose resolution would lead to nearly-linear time algorithms for polynomial factorization.