Algebraic Problems Equivalent to Beating Exponent 3/2 for Polynomial Factorization over Finite Fields

摘要

The fastest known algorithm for factoring univariate polynomials over finite fields is the Kedlaya-Umans (fast modular composition) implementation of the Kaltofen-Shoup algorithm. It is randomized and takes ~O(n^{3/2}*log(q)+n*log^2(q)) time to factor pol