Answers are grounded in this paper and cite their sources.
Let f∈ Z[x] be a polynomial of degree n with integer coefficients of absolute value less than 2ᵇ. Using Pan's approximate factorization theorem, we give a deterministic algorithm that finds all distinct integer roots of f in 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 O(nb+min(n,b)³b²), which is O(nb) whenever b≤ n1/4. This answers a question of Harvey and Hittmeir (2022), who asked whether integer roots can be found deterministically in quasilinear time, conditionally on Pan's theorem, and unconditionally for b≤ n1/4. The fastest previous deterministic algorithm, due to Nir, takes O(n3/2b) bit operations and works only for square-free polynomials. Instead of p-adic lifting, we combine approximate complex root finding with exact polynomial evaluation. We first approximate the complex roots of the polynomial formed by the top min(n,b)+1 coefficients of f. Every integer root r of f with |r|≥ 2 lies within distance $2$ of some complex root of this truncated polynomial. Rounding the real parts of the approximate roots therefore gives a list of O(min(n,b)) candidate integers that is guaranteed to contain all integer roots of f. Although a single candidate can have up to b bits, a bound via the Mahler measure shows that the bit lengths of all candidates sum to $O(b)$. This allows us to test all candidates by exact multipoint evaluation in O(nb) bit operations.
No takes yet. Share an insight, caveat, or question.
Feng et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: