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² q time to factor polynomials of degree n over the finite field F_q with q elements. A significant open problem is if the 3/2 exponent can be improved. We study a collection of algebraic problems and establish a web of reductions between them. A consequence is that an algorithm for any one of these problems with exponent better than 3/2 would yield an algorithm for polynomial factorization with exponent better than 3/2. ; © 2016 Zeyu Guo, Anand Kumar Narayanan and Chris Umans; licensed under Creative Commons License CC-BY. The authors were supported by NSF grant CCF 1423544 and a Simons Foundation Investigator grant. ; Published - LIPIcs-MFCS-2016-47.pdf Submitted - 1606.04592.pdf