Subquadratic-time factoring of polynomials over finite fields

Abstract

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(n1.815). Previous algorithms required time θ(n2+0(1)). The new algorithms rely on fast matrix multiplication techniques. More generally, to factor a polynomial of degree n over the finite field double-struck Fq with q elements, the algorithms use O(n1.815 log q) arithmetic operations in double-struck Fq. 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.