{"id":"arxiv/2611.04730","url":"https://arxiv.org/abs/2611.04730","tags":["math.NT","cs.DS","cs.SC"],"score":0,"title":"Finding Integer Roots of Polynomials in Nearly Optimal Time","domain":"math.NT","source":"arxiv","authors":["Yansong Feng","Itamar Nir"],"reviews":0,"subject":"math.NT","summary":"Let $f\\in\\mathbb Z[x]$ be a polynomial of degree $n$ with integer coefficients of absolute value less than $2^b$. Using Pan's approximate factorization theorem, we give a deterministic algorithm that finds all distinct integer roots of $f$ in $\\widetilde O(nb)$ bit operations. This matches the bit size of the input up to logarithmic factors and does not require $f$ to be square-free. Since we were unable to verify parts of the running time analysis of Pan's theorem, we also give a self-contained deterministic algorithm with running time $\\widetilde O(nb+\\min(n,b)^3b^2)$, which is $\\widetilde…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-03","reactions":{}}