pith. sign in

arxiv: 2606.12144 · v1 · pith:C7AUGLKAnew · submitted 2026-06-10 · 💻 cs.SC · cs.CC

Output-sensitive Sparse Polynomial GCD over Finite Fields is NP-hard

Ruichen Qiu , Yichuan Cao , Qiao-Long Huang , Ruyong Feng , Xiao-Shan Gao This is my paper

Pith reviewed 2026-06-27 07:38 UTC · model grok-4.3

classification 💻 cs.SC cs.CC
keywords sparse polynomial GCDfinite fieldsNP-hardnessoutput-sensitive algorithmsroots of unity detectionBPP reductionunivariate polynomialsrandomized algorithms
0
0 comments X

The pith

There is no randomized output-sensitive polynomial-time algorithm for sparse polynomial GCD over finite fields unless NP is contained in BPP.

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

The paper proves that computing the GCD of two sparse univariate polynomials over a finite field cannot be done by any randomized algorithm whose running time is polynomial in the sizes of the inputs and the GCD, under the assumption that NP is not contained in BPP. The argument proceeds by constructing a many-one reduction from a known NP-hard problem that preserves the required size measures. The same technique shows that deciding whether a sparse polynomial shares a nontrivial factor with x^n minus one is NP-hard. A sympathetic reader would care because the result rules out efficient output-sensitive methods for this basic operation in the finite-field setting and resolves a listed open challenge.

Core claim

The central claim is that output-sensitive sparse polynomial GCD computation over finite fields is NP-hard under BPP many-one reduction. For two sparse univariate polynomials f and g with finite field coefficients, there exists no randomized algorithm to compute gcd(f,g) that is polynomial-time in the sizes of f, g, and gcd(f,g) under the assumption NP notsubseteq BPP. The paper further shows that the Roots of Unity Detection problem, which asks whether the GCD of a sparse univariate polynomial and x^n minus 1 has nonzero degree, is NP-hard.

What carries the argument

A many-one reduction under BPP from a known NP-hard problem to the output-sensitive sparse GCD problem and to roots-of-unity detection.

If this is right

  • No randomized algorithm for sparse GCD over finite fields can run in time polynomial in the input and output sizes unless NP is contained in BPP.
  • Determining whether a sparse polynomial shares a root of unity with x^n minus 1 cannot be done by a randomized polynomial-time procedure under the same assumption.
  • The listed open challenge on sparsity in the finite-field setting is settled negatively for output-sensitive GCD.
  • Any practical method for this GCD must either accept superpolynomial time in the worst case or rely on a different encoding of the input polynomials.

Where Pith is reading between the lines

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

  • The hardness may extend to other sparse operations such as factorization or resultant computation over finite fields.
  • System designers might shift toward dense representations or modular techniques when GCDs arise in finite-field calculations.
  • Average-case or heuristic algorithms could still be viable even if worst-case output-sensitive methods are ruled out.
  • Similar reductions might apply to sparse polynomial problems over other rings or in the multivariate setting.

Load-bearing premise

The many-one reduction from a known NP-hard problem to the output-sensitive sparse GCD problem is correct and runs in polynomial time under BPP.

What would settle it

A randomized algorithm that computes the GCD of sparse univariate polynomials over finite fields in time polynomial in the sizes of the inputs and the GCD, or a flaw in the reduction that would allow the hardness to be bypassed.

read the original abstract

In this paper, we prove that output-sensitive sparse polynomial GCD computation over finite fields is NP-hard under BPP many-one reduction. More precisely, for two sparse univariate polynomials $f,g$ with finite field coefficients, there exists no randomized algorithm to compute $\mathrm{gcd}(f,g)$, which is polynomial-time in the sizes of $f,g,\gcd(f,g)$ under the standard complexity assumption $\mathrm{NP}\nsubseteq\mathrm{BPP}$. This settles the open problem posed as Challenge 5 in The Sparsity Challenges in the finite field setting. Furthermore, we show that the Roots of Unity Detection problem over finite fields is NP-hard; that is, determining whether the GCD of a sparse univariate polynomial and $x^n - 1$ has nonzero degree is NP-hard.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The manuscript proves that output-sensitive sparse univariate polynomial GCD over finite fields is NP-hard under BPP many-one reductions: there is no randomized algorithm computing gcd(f,g) in time polynomial in the bit sizes of f, g, and gcd(f,g) unless NP ⊆ BPP. It also establishes NP-hardness of the roots-of-unity detection problem (deciding whether deg(gcd(f, x^n−1)) > 0 for sparse f). The result is positioned as resolving Challenge 5 in the sparsity challenges for finite fields.

Significance. If the reduction construction is correct and satisfies the necessary size bounds, the result would be significant because it establishes conditional hardness for an output-sensitive variant of sparse GCD, which is a stronger statement than standard (non-output-sensitive) hardness and directly addresses an open question in computer algebra. The BPP reduction framework is appropriate for randomized algorithms in the area.

major comments (1)
  1. [Roots of Unity Detection reduction] The roots-of-unity detection reduction (and the main GCD reduction) must produce instances in which |gcd(f, x^n−1)| (term count or degree) is bounded by a polynomial in the size of the original NP-hard instance on yes cases; otherwise an algorithm running in time poly(|f| + |g| + |gcd|) need not yield a BPP algorithm for the source problem. The manuscript must explicitly verify and state this polynomial bound in the reduction construction, as it is load-bearing for transferring the hardness to the output-sensitive setting.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and for identifying the need to make the polynomial size bound explicit in our reductions. We address this point below and will revise the manuscript to strengthen the presentation.

read point-by-point responses

  1. Referee: [Roots of Unity Detection reduction] The roots-of-unity detection reduction (and the main GCD reduction) must produce instances in which |gcd(f, x^n−1)| (term count or degree) is bounded by a polynomial in the size of the original NP-hard instance on yes cases; otherwise an algorithm running in time poly(|f| + |g| + |gcd|) need not yield a BPP algorithm for the source problem. The manuscript must explicitly verify and state this polynomial bound in the reduction construction, as it is load-bearing for transferring the hardness to the output-sensitive setting.

    Authors: We agree that this bound is essential for the BPP many-one reduction to correctly establish output-sensitive NP-hardness. In our roots-of-unity detection reduction, yes-instances are constructed so that deg(gcd(f, x^n−1)) equals the number of variables (or a linear function of the 3SAT instance size), which is polynomial in the input size; the same holds for the main GCD reduction. We will add an explicit lemma (or paragraph) immediately after each reduction that states and proves this polynomial bound on the output size for yes-cases. This revision will make the load-bearing property fully transparent. revision: yes

Circularity Check

0 steps flagged

No circularity; standard many-one reduction from external NP-hard problems

full rationale

The paper claims NP-hardness of output-sensitive sparse GCD (and roots-of-unity detection) via BPP many-one reductions from known NP-complete problems. This is a conventional complexity reduction that invokes the external assumption NP ⊈ BPP and does not rely on any self-definitional equations, fitted parameters presented as predictions, load-bearing self-citations, or ansatzes smuggled from prior author work. The derivation chain is therefore independent of the paper's own inputs and receives the default non-circularity finding.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the validity of a BPP many-one reduction and the standard assumption that NP is not contained in BPP; no free parameters or invented entities are introduced.

axioms (1)
  • domain assumption NP is not contained in BPP
    This is the explicit complexity assumption under which the NP-hardness of the GCD problem holds.

pith-pipeline@v0.9.1-grok · 5675 in / 1143 out tokens · 21500 ms · 2026-06-27T07:38:40.882444+00:00 · methodology

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

27 extracted references · 2 canonical work pages

  1. [1]

    Fast constant-time gcd computation and modular inversion.IACR transactions on cryptographic hardware and embedded systems, pp

    Daniel J Bernstein and Bo-Yin Yang. Fast constant-time gcd computation and modular inversion.IACR transactions on cryptographic hardware and embedded systems, pp. 340–398, 2019

    2019

  2. [2]

    Maurice Rojas

    Jingguo Bi, Qi Cheng, and J. Maurice Rojas. Sub-linear root detection, and new hardness results, for sparse polynomials over finite fields. InProceedings of the 38th International Symposium on Symbolic and Algebraic Computation, ISSAC ’13, pp. 61–68, New York, NY, USA, 2013

    2013

  3. [3]

    W. S. Brown. On euclid’s algorithm and the computation of polynomial greatest common divisors. Journal of the ACM, 18(4):478–504, 1971

    1971

  4. [4]

    W. S. Brown and J. F. Traub. On euclid’s algorithm and the theory of subresuhants.Journal of the ACM, 18(4):505–514, 1971

    1971

  5. [5]

    George E. Collins. Subresultants and reduced polynomial remainder sequences.J. ACM, 14(1):128–142, January 1967. ISSN 0004-5411. doi: 10.1145/321371.321381. URLhttps://doi.org/10.1145/321371. 321381

    work page doi:10.1145/321371.321381 1967

  6. [6]

    Stephen A. Cook. The complexity of theorem-proving procedures. InLogic, Automata, and Computa- tional Complexity: The Works of Stephen A. Cook, pp. 143–152, New York, NY, USA, 2023. Association for Computing Machinery

    2023

  7. [7]

    The sparsity challenges

    James Harold Davenport and Jacques Carette. The sparsity challenges. In2009 11th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, pp. 3–7, 2009. doi: 10.1109/ SYNASC.2009.62

    2009

  8. [8]

    Irreducibility and greatest common divisor algorithms for sparse polynomials

    Michael Filaseta, Andrew Granville, and Andrzej Schinzel. Irreducibility and greatest common divisor algorithms for sparse polynomials. In James McKee and ChrisEditors Smyth (eds.),Number Theory and Polynomials, London Mathematical Society Lecture Note Series, pp. 155–176. Cambridge University Press, 2008

    2008

  9. [9]

    Counting curves and their projec- tions

    Joachim von zur Gathen, Marek Karpinski, and Igor Shparlinski. Counting curves and their projec- tions. InProceedings of the twenty-fifth annual ACM symposium on Theory of Computing, STOC’93, pp. 805–812. ACM, 1993

    1993

  10. [10]

    Computing greatest common divisor of several parametric univariate poly- nomials via generalized subresultant polynomials, 2024

    Hoon Hong and Jing Yang. Computing greatest common divisor of several parametric univariate poly- nomials via generalized subresultant polynomials, 2024. URLhttps://arxiv.org/abs/2401.00408

    arXiv 2024

  11. [11]

    A fast parallel sparse polynomial gcd algorithm

    Jiaxiong Hu and Michael Monagan. A fast parallel sparse polynomial gcd algorithm. InProceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation, ISSAC ’16, pp. 271–278, New York, NY, USA, 2016. Association for Computing Machinery. 16 Key Laboratory of Mathematics Mechanization MechMath Agent Team

    2016

  12. [12]

    Bit complexity of polynomial gcd on sparse representation

    Qiao-Long Huang and Xiao-Shan Gao. Bit complexity of polynomial gcd on sparse representation. Mathematics of Computation, 95(357):389–413, 2025

    2025

  13. [13]

    Greatest common divisors of polynomials given by straight-line programs.J

    Erich Kaltofen. Greatest common divisors of polynomials given by straight-line programs.J. ACM, 35 (1):231–264, 1988

    1988

  14. [14]

    On the complexity of factoring bivariate supersparse (lacunary) polynomials

    Erich Kaltofen and Pascal Koiran. On the complexity of factoring bivariate supersparse (lacunary) polynomials. InProceedings of the 2005 International Symposium on Symbolic and Algebraic Computation (ISSAC ’05), pp. 208–215. ACM, 2005

    2005

  15. [15]

    Erich Kaltofen and Barry M. Trager. Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators. Journal of Symbolic Computation, 9(3):301–320, 1990

    1990

  16. [16]

    On the computational hardness of testing square-freeness of sparse polynomials

    Marek Karpinski and Igor Shparlinski. On the computational hardness of testing square-freeness of sparse polynomials. InProc. AAECC-13 (Heidelberg, Germany, 1999), Vol. 1719 of LNCS, pp. 492–497. Springer Verlag, 1999

    1999

  17. [17]

    L. A. Levin. Universal sequential search problems.Probl. Peredachi Inf., 9(3):115–116, 1973. Translation inProblems Inform. Transmission9(3), 265–266 (1973)

    1973

  18. [18]

    Mechmath agent team

    MechMath Team. Mechmath agent team. Academy of Mathematics and Systems Science, Chinese Academy of Sciences, 2026. URLhttps://eonmath.github.io/mechmath

    2026

  19. [19]

    Joel Moses and David Y. Y. Yun. The ez gcd algorithm. InProceedings of the ACM Annual Conference, ACM ’73, pp. 159–166, New York, NY, USA, 1973. Association for Computing Machinery

    1973

  20. [20]

    Plaisted

    David A. Plaisted. New np-hard and np-complete polynomial and integer divisibility problems.The- oretical Computer Science, 31(1):125–138, 1984

    1984

  21. [21]

    Sparse complex polynomials and polynomial reducibility.Journal of Computer and System Sciences, 14(2):210–221, 1977

    David Alan Plaisted. Sparse complex polynomials and polynomial reducibility.Journal of Computer and System Sciences, 14(2):210–221, 1977

    1977

  22. [22]

    Schinzel

    A. Schinzel. On the greatest common divisor of two univariate polynomials, i. In GisbertEditor Wüstholz (ed.),A Panorama of Number Theory or The View from Baker’s Garden, pp. 337–352. Cambridge University Press, 2002

    2002

  23. [23]

    Valiant and V .V

    L.G. Valiant and V .V . Vazirani. Np is as easy as detecting unique solutions. InProceedings of the Seven- teenth Annual ACM Symposium on Theory of Computing, STOC ’85, pp. 458–463, 1985

    1985

  24. [24]

    Optimizing the half-gcd algorithm.Applicable Algebra in Engineering, Communi- cation and Computing, May 2025

    Joris van der Hoeven. Optimizing the half-gcd algorithm.Applicable Algebra in Engineering, Communi- cation and Computing, May 2025. URLhttps://doi.org/10.1007/s00200-025-00690-w

    work page doi:10.1007/s00200-025-00690-w 2025

  25. [25]

    On sparse interpolation of rational functions and gcds

    Joris van der Hoeven and Grégoire Lecerf. On sparse interpolation of rational functions and gcds. ACM Commun. Comput. Algebra, 55(1):1–12, 2021

    2021

  26. [26]

    Cambridge University Press, 2013

    Joachim von zur Gathen and Jürgen Gerhard.Modern Computer Algebra. Cambridge University Press, 2013

    2013

  27. [27]

    Probabilistic algorithms for sparse polynomials

    Richard Zippel. Probabilistic algorithms for sparse polynomials. In Edward W. Ng (ed.),Symbolic and Algebraic Computation, EUROSAM ’79, An International Symposium on Symbolic and Algebraic Computa- tion, volume 72 ofLecture Notes in Computer Science, pp. 216–226. Springer, 1979. 17

    1979