Fast polynomial factorization and modular composition in small characteristic

We obtain randomized algorithms for factoring degree n univariate polynomials over F_q that use O(n 1.5 + o(1) + n 1 + o(1) log q) field operations, when the characteristic is at most n o(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.

Authors

• Chris Umans

Keywords

• polynomial factorization
• modular composition
• multipoint evaluation