Subquadratic-time factoring of polynomials over finite fields

New probabilistic algorithms are presented for factoring univariate polynomials over finite fields. The algorithms factor a polynomial of degree n over a finite field of constant cardinality in time O(n^1.815). Previous algorithms required time θ(n²⁺⁰⁽¹⁾). The new algorithms rely on fast matrix multiplication techniques. More generally, to factor a polynomial of degree n over the finite field double-struck F_q with q elements, the algorithms use O(n^1.815 log q) arithmetic operations in double-struck F_q. The new "baby step/giant step" techniques used in our a gorithms also yield new fast practical algorithms at super-quadratic asymptotic running time, and subquadratic-tirne methods for manipulating normal bases of finite fields.