A number-theoretic conjecture implying faster algorithms for polynomial factorization and integer factorization

Chris Umans, Siki Wang

The fastest known algorithm for factoring a degree $n$ univariate polynomial over a finite field ${\mathbb{F}}_q$ runs in time $O(n^{3/2+o(1)}\text{polylog }q)$, and there is a re…