Sparse Polynomial GCD Algorithms Asymptotically Linear in All Fundamental Parameters
Abstract
Let A, B ∈ ℤ[x1, …, xn] be multivariate polynomials with integer coefficients and let G = gcd(A, B). We present an algorithm for computing G whose expected bit complexity is asymptotically linear in all fundamental parameters: the number of variables n, the term count T = max{|A|0, |B|0, |G|0}, the total degree D, and the logarithmic coefficient sizes logHi and logHo, where Hi bounds the coefficients of the inputs and Ho bounds those of the GCD. The bit complexity is characterized by the clean bound Õ( n · T · D · logHi · logHo ). To our knowledge, this is the first sparse GCD algorithm over the integers that achieves linear complexity in all these parameters simultaneously. The integer algorithm is built upon a new field GCD algorithm. For A, B ∈ K[x1, …, xn] over a field K with char(K) = 0 or char(K) > °G, we give the first algorithm that computes G = gcd(A,B) with expected Õ( n · T · D ) field operations, which is both input- and output-sensitive. The key technical contribution behind both algorithms is a derivative-aided separated Hensel lifting technique introduced in this paper. By introducing an auxiliary variable and leveraging derivative information, our scheme extracts all partial exponents via a single z2-lift per variable, achieving constant sequential depth O(1). This stands in sharp contrast to classical Hensel lifting, which requires O(D) sequential lifting steps and suffers from representation densification in the sparse setting. The field algorithm is then extended to the integer case through modular reduction and rational reconstruction.
Related
- Polynomial-Time Constructions of Asymptotically Good Random Access Codes from Linear Codes
- Scaled-Gradient Hard Thresholding Algorithms for Sparse Signal Recovery
- A note on the convergence guarantees of RLT-based algorithms for polynomial optimization
- ParaDeAl: Parallel Descent Algorithms for Sparse Statistics
- Sparse Dictionary Learning for Measure-Valued Data via Linearized Optimal Transport: Efficient Algorithms and Sample Complexity
BibTeX
@misc{huang2026sparse,
title = {{Sparse Polynomial GCD Algorithms Asymptotically Linear in All Fundamental Parameters}},
author = {Qiao-Long Huang and Xiao-Shan Gao},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.08074},
eprint = {2609.08074},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.08074},
}
RIS
TY - UNPB
TI - Sparse Polynomial GCD Algorithms Asymptotically Linear in All Fundamental Parameters
AU - Qiao-Long Huang
AU - Xiao-Shan Gao
PY - 2026
DA - 2026/09/08
PB - arXiv
DO - 10.48550/arxiv.2609.08074
UR - https://arxiv.org/abs/2609.08074
AB - Let A, B ∈ ℤ[x_1, …, x_n] be multivariate polynomials with integer coefficients and let G = gcd(A, B). We present an algorithm for computing G whose expected bit complexity is asymptotically linear in all fundamental parameters: the number of variables n, the term count T = max{|A|_0, |B|_0, |G|_0}, the total degree D, and the logarithmic coefficient sizes logHi and logHo, where Hi bounds the coefficients of the inputs and Ho bounds those of the GCD. The bit complexity is characterized by the clean bound Õ( n · T · D · logHi · logHo ). To our knowledge, this is the first sparse GCD algorithm over the integers that achieves linear complexity in all these parameters simultaneously. The integer algorithm is built upon a new field GCD algorithm. For A, B ∈ K[x_1, …, x_n] over a field K with char(K) = 0 or char(K) > °G, we give the first algorithm that computes G = gcd(A,B) with expected Õ( n · T · D ) field operations, which is both input- and output-sensitive. The key technical contribution behind both algorithms is a derivative-aided separated Hensel lifting technique introduced in this paper. By introducing an auxiliary variable and leveraging derivative information, our scheme extracts all partial exponents via a single z^2-lift per variable, achieving constant sequential depth O(1). This stands in sharp contrast to classical Hensel lifting, which requires O(D) sequential lifting steps and suffers from representation densification in the sparse setting. The field algorithm is then extended to the integer case through modular reduction and rational reconstruction.
ER -