{"ID":2842516,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.10851","arxiv_id":"2511.10851","title":"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^β$, consisting of positive integers of magnitude at most $\\exp(n^α)$, such that every integer $i \\in [n]$ divides $s-t$ for some $s \\in S, t \\in T$. Achieving $α+ β\\le 1 + o(1)$ is trivial; we show that achieving $α, β\u003c 1/2$ (together with an assumption that $S, T$ are structured) implies an improvement to the exponent 3/2 for univariate polynomial factorization. Achieving $α= β= 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$.","short_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 strat...","url_abs":"https://arxiv.org/abs/2511.10851","url_pdf":"https://arxiv.org/pdf/2511.10851v1","authors":"[\"Chris Umans\",\"Siki Wang\"]","published":"2025-11-13T23:23:54Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CC\",\"math.NT\"]","methods":"[]","has_code":false}