Fast polynomial factorization and modular composition in small characteristic
Christopher Umans · 2008
We obtain randomized algorithms for factoring degree n univariate polynomials over F_q that use O(n1.5 + o(1) + n1 + o(1)log q) field operations, when the characteristic is at most no(1). When log q < n, this is asymptotically faster than the best previous algorithms (von zur Gathen & Shoup (1992) and Kaltofen & Shoup (1998)); for log q ≥ n, it matches the asymptotic running time of the best known algorithms.