Finding Integer Roots of Polynomials in Nearly Optimal Time
Abstract
Let f∈ℤ[x] be a polynomial of degree n with integer coefficients of absolute value less than 2b. Using Pan's approximate factorization theorem, we give a deterministic algorithm that finds all distinct integer roots of f in Õ(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 Õ(nb+min(n,b)3b2), which is Õ(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 Õ(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 Õ(nb) bit operations.
Related
- Faster Deterministic Integer Root Finding for Integer Polynomials
- The paxotopy method for finding isolated roots of a system of nonlinear equations
- A combinatorial criterion for detecting roots of Bernstein-Sato polynomials
- Convergence for Small-Order Derivatives of Random Polynomials with Independent Roots
- Real-rooted flow polynomials have only integral roots
BibTeX
@misc{feng2026finding,
title = {{Finding Integer Roots of Polynomials in Nearly Optimal Time}},
author = {Yansong Feng and Itamar Nir},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.04730},
eprint = {2611.04730},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.04730},
}
RIS
TY - UNPB
TI - Finding Integer Roots of Polynomials in Nearly Optimal Time
AU - Yansong Feng
AU - Itamar Nir
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.04730
UR - https://arxiv.org/abs/2611.04730
AB - Let f∈ℤ[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 Õ(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 Õ(nb+min(n,b)^3b^2), which is Õ(nb) whenever b≤ n^1/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≤ n^1/4. The fastest previous deterministic algorithm, due to Nir, takes Õ(n^3/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 Õ(nb) bit operations.
ER -