Pith. sign in

REVIEW 6 minor 21 references

The paper proves a deterministic algorithm that finds all integer roots of a square-free polynomial of degree n with coefficients below 2^b in Õ(n^{3/2} b) bit operations.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Integer-root finding for square-free polynomials is now deterministic Õ(n^{3/2}b), the first subquadratic-in-n improvement.

T0 review reviewed 2026-08-04 challenge →

load-bearing objection A real, if specialized, breakthrough: deterministic O~(n^{3/2} b) integer root finding, with a proof that looks sound; referee it carefully.

arxiv 2608.00668 v1 pith:VHFSWI5K submitted 2026-08-01 math.NT cs.DScs.SC

Faster Deterministic Integer Root Finding for Integer Polynomials

Itamar Nir This is my paper
classification math.NT cs.DScs.SC MSC 11Y1611Y0568Q25
keywords deterministic algorithminteger rootssquare-free polynomialp-adic liftingHensel liftinglifting treebit complexitymultipoint evaluation
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper establishes a deterministic algorithm for finding all integer roots of a square-free polynomial f ∈ Z[x] of degree n with coefficients bounded by 2^b, running in Õ(n^{3/2} b) bit operations. This improves the previous deterministic bound of Õ(n² b), bringing the problem substantially closer to the Θ(nb) lower bound set by the input size. The key move is to drop the classical requirement that f modulo a prime p be square-free; instead, the paper finds a small prime for which the total multiplicity of repeated roots modulo p is small, and then lifts repeated roots using a new data structure called a weighted lifting tree. A second contribution is a fast deterministic verification procedure that tests n candidate integers in Õ(nb + min(n², nb²)) time. Together these pieces yield the first deterministic subquadratic-in-n root-finding algorithm for square-free integer polynomials.

Core claim

The central claim is Theorem 1.1: for a square-free f ∈ Z[x] with deg f = n and ||f||∞ < 2^b, all integer roots can be found deterministically in Õ(n^{3/2} b) time. The proof builds the p-adic lifting tree not only for simple roots but for repeated roots, and shows how to construct the relevant part of the tree efficiently. The prime p is chosen to satisfy deg(gcd(fp, f'_p)) < t, with t ≈ √n, rather than requiring f_p to be square-free; the resultant res(f, f') bounds the number of primes that violate this condition. The running time of the lifting step is Õ(nbt + (t+√n)√p), and with t = ⌊√n⌋ this yields the main bound. The verification step is handled by two algorithms that filter candidate

What carries the argument

The weighted lifting tree. Nodes are base-p digit strings; a node x in layer m represents a prefix x = δ0 + δ1 p + ... + δ_{m-1} p^{m-1}. For a node x, the branching polynomial is f_x(a) = f(x + p^m a). Dividing by the common p-adic valuation v_p(f_x) and reducing mod p gives the polynomial (f_x)^*_p whose roots are the next digits. The weight w(x) is the multiplicity of the digit that led to x as a root of its parent's normalized polynomial, with w(ε) = deg f_p^*. The crucial bound is Lemma 5.11: v_p(f_x) ≤ v_p(f) + w(x_0) m for a node x in layer m with residue x_0 mod p. This bounds the precision needed at each node and enables a divide-and-conquer construction along a heavy path (spine) a

Load-bearing premise

The algorithm needs the input polynomial to be square-free, and within that setting it rests on the valuation bound of Lemma 5.11 (v_p(f_x) ≤ v_p(f)+w(x_0)m for every tree node x in layer m); if either fails, the resultant-style prime bound or the precision-control argument collapses.

What would settle it

A counterexample to Lemma 5.11: exhibit a square-free f ∈ Z[x], a prime p, and a node x in layer m of the lifting tree for which v_p(f_x) > v_p(f)+w(x_0)m. Even one such instance would invalidate the precision bound and break the algorithm's complexity analysis.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • If the theorem is correct, deterministic integer root finding for square-free polynomials becomes subquadratic in the degree, with running time Õ(n^{3/2} b) versus the previous Õ(n² b).
  • The lifting construction gives a deterministic method to approximate p-adic roots (simple and repeated) to precision p^b in time Õ(nbt + (t+√n)√p), where t bounds the total multiplicity of repeated roots mod p.
  • The candidate-verification procedure decides which of n candidates are roots in Õ(nb + min(n², nb²)) time; this could be reused in other settings where a short list of candidates must be tested.
  • The rational-root case is within reach: the same lifting approach plus rational reconstruction can be adapted, as the paper sketches.
  • The relaxed prime condition (small total multiplicity rather than square-free) means the search over primes is shortened to Õ(nb/t), so the prime-selection bottleneck is reduced.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The t-versus-√n tradeoff suggests a parameterized family of algorithms; if a faster way to find primes with small deg gcd(fp, f'_p) were found, the exponent 3/2 could be pushed lower.
  • The weighted lifting tree may be applicable to other p-adic lifting tasks where repeated roots appear, such as polynomial factorization over local rings or root finding in error-correcting codes.
  • The small-b verification algorithm relies on a lifting-tree argument for the number of divisors of a_0; this connection between candidate filtering and p-adic tree structure is likely to find further uses.
  • Because the entire algorithm is deterministic, it also contributes to derandomizing algorithms that currently depend on random primes for square-freeness.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 6 minor

Summary. The paper presents a deterministic algorithm for finding all integer roots of a square-free polynomial f ∈ Z[x] of degree n with ||f||_∞ < 2^b, running in O~(n^{3/2}b) bit operations. This improves the previous O~(n^2b) bound of Harvey and Hittmeir. The algorithm follows the classical p-adic strategy but relaxes the requirement that f mod p be square-free: it finds a prime p for which the total multiplicity of repeated roots modulo p is small, using a resultant bound to control the search. Repeated roots are lifted using a weighted lifting tree with carefully managed p-adic precision, and the final candidate verification is accelerated by two new deterministic filters. The paper states and proves three standalone results: Theorem 1.2 (p-adic lifting), Theorem 1.3 (candidate verification), and Theorem 1.4 (finding a good prime), which together yield Theorem 1.1.

Significance. If the result is correct, it gives the first deterministic subquadratic-in-n improvement for integer root finding in the square-free case, and the component results are likely to be of independent interest. The proof is detailed and internally coherent: the resultant bound (Lemmas 4.3–4.5), valuation bounds (Lemma 5.11), tree-size control (Lemmas 5.8–5.10), and verification filter (Lemmas 6.4–6.8) form a consistent whole. I specifically checked the stress-test concern about Lemma 5.11: the bound v_p(f_x) ≤ v_p(f)+w(x0)m follows from the coefficient of a^{w(x0)} having valuation exactly m·w(x0), because p ∤ f^{[w(x0)]}(x0). The subsequent precision lemmas (5.12, 5.14) and the divide-and-conquer accounting are consistent with this bound. The paper uses no fitted constants, no circular reasoning, and builds only on standard external tools. I found no load-bearing error, though some passages would benefit from clarification.

minor comments (6)
  1. [Section 5.3, before Lemma 5.15] The sentence “log p = O(log(nbt+(√n+t)√p))” is confusing. It is true only up to a constant factor because log(√p) = (1/2)log p, but the intended point — that log p factors are absorbed by the O~ notation and dominated by the displayed running time — should be stated more explicitly.
  2. [Algorithm 3, lines 5–6] The arrow notation “b−i−1→b, w(x)→W, k−i−1→k” is nonstandard and initially misleading. It would be clearer to say: “recursively call Algorithm 3 with parameters (b−i−1, w(x), k−i−1, f^*_x)”, and then explain that the tree layers for f^*_x are obtained from the already-constructed descendant layers.
  3. [Lemma 5.13, proof] The statement “z = x/p < p^{b−1}, z has b−1 digits” should be phrased as “z has at most b−1 base-p digits; after padding with leading zeros it is a node in layer b−1.” This avoids confusion about integers with fewer digits.
  4. [Lemma 6.5] The proof is by p-adic valuations, but the “integer c” is never explicitly constructed. It would improve readability to state that c = R_{≥k}(lcm(...)) / R_{≥k}((...)) is an integer, and that this is exactly the content of the valuation argument.
  5. [Section 2.2, Item 7] The binary-splitting recurrence T(n)=2T(n/2)+O~(nb) is standard, but the cost of the multiplication x^{⌈n/2⌉}·f1(x) is only O~(nb) under the stated b-bit-coefficient and b-bit-x assumptions. A one-sentence justification of the multiplication cost would help readers not familiar with this particular recurrence.
  6. [Theorem 1.2, statement] The assumption is printed as “||f||_∞ ≤ p bt”; it should be “||f||_∞ ≤ p^{bt}”, with the exponent properly raised.

Circularity Check

0 steps flagged

No significant circularity—the derivation is self-contained and uses standard external facts.

full rationale

The paper's claimed derivation chain does not reduce to its inputs. Theorem 1.4 is an exhaustive search over primes justified by the resultant divisibility bound deg(gcd(f_p,f'_p)) ≤ v_p(res(f,f')) and the standard bound |res(f,f')| ≤ 2^{Õ(nb)} (Lemmas 4.3–4.5), with no fitted parameter. Theorem 1.2 is built from the lifting tree; Lemmas 5.8–5.14 prove the needed weight and precision budgets from the definitions of branching polynomials and weights, without assuming the target running time. Theorem 1.3's verifiers are based on elementary divisibility/lcm arguments, and its use of Lemma 5.13 is cross-proven from the same lifting-tree analysis, not assumed. There are no self-citations, no imported uniqueness theorems, and no prediction that is forced by construction. The load-bearing Lemma 5.11 is proved in the text; its intricate recursive precision accounting may deserve independent checking, but unverified intricacy is a correctness risk, not circularity.

Axiom & Free-Parameter Ledger

1 free parameters · 5 axioms · 1 invented entities

No empirical constants are fitted; the only hand-tuned variable is the algorithmic parameter t. The paper's central claim rests on standard mathematics plus its own proved lemmas.

free parameters (1)
  • t = ⌊√n⌋
    Algorithmic trade-off parameter in Theorems 1.2/1.4; setting t=√n balances prime-search cost Õ(n²b/t) with lifting cost Õ(nbt). It is chosen by hand, not fitted to data.
axioms (5)
  • standard math Prime number theorem: π(u)=Θ(u/log u)
    Used in Section 4.3 to bound the u-th prime and in Lemma 3.1's interval counting.
  • standard math Resultant/Sylvester determinant theory: res(A,B)=0 iff common factor; determinant divisibility lemmas
    Used in Section 4.1 to derive p^d | res(f,f') (Lemma 4.3).
  • standard math Fast arithmetic black boxes: fast polynomial/integer multiplication, gcd, multipoint evaluation, product trees
    Assumed in Section 2.2 and used throughout; costs are taken from von zur Gathen–Gerhard and Cantor–Kaltofen.
  • standard math Hensel lifting and uniqueness of simple-root lifts in Z_p
    Used in Algorithm 5 for simple roots modulo p.
  • domain assumption Input f is square-free and the chosen prime does not divide the leading coefficient
    Stated in Theorem 1.1/1.4; guarantees res(f,f')≠0 and v(f)=0, which the lifting tree requires.
invented entities (1)
  • Weighted lifting tree no independent evidence
    purpose: Represents all p-adic roots of f as digit-prefix paths, including repeated-root branches that ordinary Hensel lifting cannot handle.
    An algorithmic construct introduced by the paper; its correctness and complexity are proven internally (Lemmas 5.8–5.14), so it is not an unsupported physical postulate.

reviewed 2026-08-04 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Faster Deterministic Integer Root Finding for Integer Polynomials." pith.science (2026). https://pith.science/paper/VHFSWI5K

@misc{pith2026260800668,
  author       = {Pith},
  title        = {Pith review of: Faster Deterministic Integer Root Finding for Integer Polynomials},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VHFSWI5K}},
  note         = {Machine review of arXiv:2608.00668}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

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 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 $$ \tilde{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.

Figures

Figures reproduced from arXiv: 2608.00668 by Itamar Nir.

Figure 1
Figure 1. Figure 1: The spine and the light children Lemma 5.16. P x∈A w(x) ≤ W Proof. For 0 ≤ i ≤ s, let Li = {light children of ui} and Si = Xs j=i X x∈Lj w(x). We claim that Si ≤ w(ui). 23 [PITH_FULL_IMAGE:figures/full_fig_p025_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: High-level illustration of the algorithm [PITH_FULL_IMAGE:figures/full_fig_p029_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The finishing step. The roots of fp are found with their multiplicities (Lemma 3.3) and split by multiplicity. A simple root (multiplicity 1) has a unique lift, so all of A is lifted in parallel by Hensel lifting, doubling the p-adic precision over ⌈log b⌉ rounds of multipoint evaluation. A repeated root (multiplicity > 1) branches, so each x ∈ B is lifted by building the first b layers of its lifting tree… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references

  1. [1]

    Linear diophantine equations over polynomials and soft decoding of Reed–Solomon codes.IEEE Transactions on Information Theory, 51(7):2257–2265,

    Michael Alekhnovich. Linear diophantine equations over polynomials and soft decoding of Reed–Solomon codes.IEEE Transactions on Information Theory, 51(7):2257–2265,

  2. [2]

    Polynomial root find- ing over local rings and application to error correcting codes.Applicable Algebra in Engineering, Communication and Computing, 24(6):413–443, 2013

    Jérémy Berthomieu, Grégoire Lecerf, and Guillaume Quintin. Polynomial root find- ing over local rings and application to error correcting codes.Applicable Algebra in Engineering, Communication and Computing, 24(6):413–443, 2013. 8

    2013

  3. [3]

    FactoringN=prqfor larger

    Dan Boneh, Glenn Durfee, and Nick Howgrave-Graham. FactoringN=prqfor larger. InAdvances in Cryptology—CRYPTO ’99, volume 1666 ofLecture Notes in Computer Science, pages 326–337. Springer, 1999. 1

    1999

  4. [4]

    Brent and Paul Zimmermann.Modern Computer Arithmetic

    Richard P. Brent and Paul Zimmermann.Modern Computer Arithmetic. Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press,

  5. [5]

    Cantor and Erich Kaltofen

    David G. Cantor and Erich Kaltofen. On fast multiplication of polynomials over arbi- trary algebras.Acta Informatica, 28(7):693–701, 1991. 9

    1991

  6. [6]

    Small solutions to polynomial equations, and low exponent RSA vulnerabilities.Journal of Cryptology, 10(4):233–260, 1997

    Don Coppersmith. Small solutions to polynomial equations, and low exponent RSA vulnerabilities.Journal of Cryptology, 10(4):233–260, 1997. 1

    1997

  7. [7]

    Springer, 2 edition, 2005

    Richard Crandall and Carl Pomerance.Prime Numbers: A Computational Perspective. Springer, 2 edition, 2005. 9

    2005

  8. [8]

    Deterministic root finding over finite fields using Graeffe transforms.Applicable Algebra in Engineering, Commu- nication and Computing, 27(3):237–257, 2016

    Bruno Grenet, Joris van der Hoeven, and Grégoire Lecerf. Deterministic root finding over finite fields using Graeffe transforms.Applicable Algebra in Engineering, Commu- nication and Computing, 27(3):237–257, 2016. 7

    2016

  9. [9]

    Hart and Andrew Novocin

    William B. Hart and Andrew Novocin. Practical divide-and-conquer algorithms for polynomial arithmetic. InComputer Algebra in Scientific Computing, volume 6885 of Lecture Notes in Computer Science, pages 200–214. Springer, 2011. 9

    2011

  10. [10]

    A deterministic algorithm for findingr-power divisors.Research in Number Theory, 8(4):Paper No

    David Harvey and Markus Hittmeir. A deterministic algorithm for findingr-power divisors.Research in Number Theory, 8(4):Paper No. 94, 2022. 1, 2, 40

    2022

  11. [11]

    Finding small roots of univariate modular equations revisited

    Nick Howgrave-Graham. Finding small roots of univariate modular equations revisited. InCryptography and Coding, volume 1355 ofLecture Notes in Computer Science, pages 131–142. Springer, 1997. 1

    1997

  12. [12]

    Subquadratic-time factoring of polynomials over finite fields.Mathematics of Computation, 67(223):1179–1197, 1998

    Erich Kaltofen and Victor Shoup. Subquadratic-time factoring of polynomials over finite fields.Mathematics of Computation, 67(223):1179–1197, 1998. 7

    1998

  13. [13]

    Lenstra, Hendrik W

    Arjen K. Lenstra, Hendrik W. Lenstra, Jr., and László Lovász. Factoring polynomials with rational coefficients.Mathematische Annalen, 261(4):515–534, 1982. 1

    1982

  14. [14]

    Computing rational zeros of integral polynomials byp-adic expansion

    Rüdiger Loos. Computing rational zeros of integral polynomials byp-adic expansion. SIAM Journal on Computing, 12(2):286–293, 1983. 1 41

    1983

  15. [15]

    Michael B. Monagan. Maximal quotient rational reconstruction: An almost optimal algorithm for rational reconstruction. InProceedings of the 2004 International Sympo- sium on Symbolic and Algebraic Computation, ISSAC ’04, pages 243–249. Association for Computing Machinery, 2004. 40

    2004

  16. [16]

    Fast computation of the roots of polynomials over the ring of power series

    Vincent Neiger, Johan Rosenkilde, and Éric Schost. Fast computation of the roots of polynomials over the ring of power series. InProceedings of the 2017 ACM Interna- tional Symposium on Symbolic and Algebraic Computation, ISSAC ’17, pages 349–356. Association for Computing Machinery, 2017. 8

    2017

  17. [17]

    Local polynomial factorisation: Improving the Montes algorithm

    Adrien Poteaux and Martin Weimann. Local polynomial factorisation: Improving the Montes algorithm. InProceedings of the 2022 International Symposium on Symbolic and Algebraic Computation, ISSAC ’22, pages 149–157. Association for Computing Ma- chinery, 2022. 8

    2022

  18. [18]

    Roth and Gitit Ruckenstein

    Ron M. Roth and Gitit Ruckenstein. Efficient decoding of Reed–Solomon codes beyond half the minimum distance.IEEE Transactions on Information Theory, 46(1):246–257,

  19. [19]

    Cambridge University Press, 3 edition, 2013

    Joachim von zur Gathen and Jürgen Gerhard.Modern Computer Algebra. Cambridge University Press, 3 edition, 2013. 1, 7, 9

    2013

  20. [20]

    Paul S. Wang, M. J. T. Guy, and James H. Davenport.p-adic reconstruction of rational numbers.ACM SIGSAM Bulletin, 16(2):2–3, 1982. 40

    1982

  21. [21]

    On hensel factorization, I.Journal of Number Theory, 1(3):291–311,

    Hans Zassenhaus. On hensel factorization, I.Journal of Number Theory, 1(3):291–311,

This paper was first reviewed by deepseek-v4-flash on August 4, 2026.