  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 $\widetilde{O}(n^{3/2}\log
q + n \log^2 q)$ time to factor polynomials of degree $n$ over the finite field
$\mathbb{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$.
