Faster Deterministic Integer Root Finding for Integer Polynomials

Abstract

We give a deterministic algorithm for finding all integer roots of a square-free polynomial f∈ℤ[x] of degree n with lVert frVert_∞<2^b. The running time is Õ(n^3/2b), improving the Õ(n²b) 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 fbmod p is square-free. Instead, we find a prime for which the total multiplicity of repeated roots modulo p is small. This requires lifting repeated roots, which we handle using a weighted lifting tree. We also give a faster deterministic candidate-verification algorithm: given n candidate integers smaller in absolute value than 2^b, we decide which are roots of f in Õ(nb+min(n²,nb²)) bit operations. Together, these ingredients give the first deterministic subquadratic-in-n improvement for integer root finding in the square-free case.

Finding Integer Roots of Polynomials in Nearly Optimal Time
Yansong Feng, Itamar Nir
arXiv3 Nov 2026PreprintarXiv licenceFull textAlgebra & number theoryarXiv
Undirected Network Coding and Faster External-Memory Integer Sorting
Baochun Li, Zongpeng Li, Sirui Liu
arXiv17 Oct 2026PreprintarXiv licenceFull textGeneral mathematicsarXiv
On the Krull dimensions of rings of integer-valued polynomials and polynomial rings
Viet-Hoang Tran, Tan M. Nguyen
arXiv1 Oct 2026PreprintCC BY 4.0Full textAlgebra & number theoryarXiv
On the probability that the integer parts of polynomials are coprime
Philippa Holdridge
arXiv1 Nov 2026PreprintCC BY-NC-ND 4.0Full textAlgebra & number theoryarXiv
Non-convex integer programming: a deterministic solution method of the large block sale problem
David Nizard, Dominique Quadri
arXiv10 Oct 2026PreprintCC BY-NC-SA 4.0Full textOptimisation & controlarXiv

Cite

BibTeX RIS

BibTeX

@misc{nir2026faster,
  title = {{Faster Deterministic Integer Root Finding for Integer Polynomials}},
  author = {Itamar Nir},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2608.00668},
  eprint = {2608.00668},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.00668},
}

RIS

TY  - UNPB
TI  - Faster Deterministic Integer Root Finding for Integer Polynomials
AU  - Itamar Nir
PY  - 2026
DA  - 2026/10/16
PB  - arXiv
DO  - 10.48550/arxiv.2608.00668
UR  - https://arxiv.org/abs/2608.00668
AB  - We give a deterministic algorithm for finding all integer roots of a square-free polynomial f∈ℤ[x] of degree n with lVert frVert_∞<2^b. The running time is Õ(n^3/2b), improving the 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 fbmod p is square-free. Instead, we find a prime for which the total multiplicity of repeated roots modulo p is small. This requires lifting repeated roots, which we handle using a weighted lifting tree. We also give a faster deterministic candidate-verification algorithm: given n candidate integers smaller in absolute value than 2^b, we decide which are roots of f in Õ(nb+min(n^2,nb^2)) bit operations. Together, these ingredients give the first deterministic subquadratic-in-n improvement for integer root finding in the square-free case.
ER  -

Abstract

Related

Cite