A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic
Victor Shoup · 1991
We present a new algorithm for factoring polynomials over finite fields. Our algorithm is deterministic, and its running time is "almost" quadratic when the characteristic is a small fixed prime. As such, our algorithm is asymptotically faster than previously known deterministic algorithms for factoring polynomials over finite fields of small characteristic. Appeared in Proc. 1991 International Symposium on Symbolic and Algebraic Computation (ISSAC), pp. 14--21, 1991. 1. Introduction Consider the problem of factoring a univariate polynomial f of degree n over the finite field F q , where q = p k and p is a small, fixed prime. We assume that F q is represented as F p (`), where ` is the root of an irreducible polynomial over F p of degree k. We present a new deterministic algorithm for this problem whose asymptotic complexity is less than that of previous deterministic algorithms. In discussing running times of algorithms, for expositional purposes we treat p as a constant in Sec...