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

Abstract

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 reason to believe that the $3/2$ exponent represents a ''barrier'' inherent in algorithms that employ a so-called baby-steps-giant-steps strategy. In this paper, we propose a new strategy with the potential to overcome the $3/2$ barrier. In doing so we are led to a number-theoretic conjecture, one form of which is that there are sets $S,T$ of cardinality $n^2$, consisting of positive integers of magnitude at most $\exp (n^{\hat{I}}\pm )$, such that every integer $i\in [n]$ divides $s-t$ for some $s\in S,t\in T$. Achieving $\hat{I}\pm +{\hat{I}}^2\le 1+o(1)$ is trivial; we show that achieving $\hat{I}\pm ,{\hat{I}}^2<1/2$ (together with an assumption that $S,T$ are structured) implies an improvement to the exponent 3/2 for univariate polynomial factorization. Achieving $\hat{I}\pm ={\hat{I}}^2=1/3$ is best-possible and would imply an exponent 4/3 algorithm for univariate polynomial factorization. Interestingly, a second consequence would be a reduction of the current-best exponent for deterministic (exponential) algorithms for factoring integers, from $1/5$ to $1/6$.