{"id":"arxiv/2608.00668","url":"https://arxiv.org/abs/2608.00668","tags":["math.NT","cs.DS","cs.SC"],"score":0,"title":"Faster Deterministic Integer Root Finding for Integer Polynomials","domain":"math.NT","source":"arxiv","authors":["Itamar Nir"],"reviews":0,"subject":"math.NT","summary":"We give a deterministic algorithm for finding all integer roots of a square-free polynomial $f\\in\\mathbb Z[x]$ of degree $n$ with $\\lVert f\\rVert_\\infty<2^b$. The running time is $$ \\tilde{O}(n^{3/2}b), $$ improving the $\\tilde{O}(n^2b)$ bound of Harvey and Hittmeir (Research in Number Theory, 2022). The algorithm follows the classical $p$-adic framework: find roots modulo a prime $p$, lift them modulo a high power of $p$, and verify the lifted candidates. The main new idea is to avoid searching for a prime for which $f\\bmod p$ is square-free. Instead, we find a prime for which the total…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-01","reactions":{}}