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

2026/06/10 by Ruichen Qiu, Yichuan Cao, Qiao-Long Huang +2 · 1 voice
Computer Science · #cs.SC #cs.CC

paper · pdf

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 gcd(f,g), which is polynomial-time in the sizes of f,g,gcd(f,g) under the standard complexity assumption NP\nsubseteqBPP. 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ⁿ - 1 has nonzero degree is NP-hard.

Citations

• Computing greatest common divisor of several parametric univariate polynomials via generalized subresultant polynomials
• Optimizing the half-gcd algorithm
• Bit Complexity of Polynomial GCD on Sparse Representation
• Sub-Linear Root Detection, and New Hardness Results, for Sparse Polynomials Over Finite Fields
• Probabilistic algorithms for sparse polynomials
• The complexity of theorem-proving procedures

Discussions

• Ruichen Qiu, Yichuan Cao, Qiao-Long Huang, Ruyong Feng, Xiao-Shan Gao: Output-sensitive Sparse Polynomial GCD over Finite Fields is NP-hard https://arxiv.org/abs/2606.12144 https://arxiv.org/pdf/2606. [bsky, 0 points, 0 comments]

Related

• Bit Complexity of Polynomial GCD on Sparse Representation
• Sparse Polynomial Divisibility Test over Finite Field is CoNP-hard
• Factoring sparse polynomials fast
• Sub-Linear Root Detection, and New Hardness Results, for Sparse Polynomials Over Finite Fields
• Polynomial evaluation over finite fields: new algorithms and complexity bounds