Sparse Polynomial GCD Algorithms Asymptotically Linear in All Fundamental Parameters

Abstract

Let $A, B \in \mathbb{Z}[x_1, \dots, 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 $\log\Hi$ and $\log\Ho$, where $\Hi$ bounds the coefficients of the inputs and $\Ho$ bounds those of the GCD. The bit complexity is characterized by the clean bound \[ \widetilde{O}\bigl( n \cdot T \cdot D \cdot \log\Hi \cdot \log\Ho \bigr). \] 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 \in \K[x_1, \dots, x_n]$ over a field $\K$ with $\operatorname{char}(\K) = 0$ or $\operatorname{char}(\K) > °G$, we give the first algorithm that computes $G = \gcd(A,B)$ with expected \[ \widetilde{O}\bigl( n \cdot T \cdot D \bigr) \] 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.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Commutative Algebra

• arXiv preprint · 19 October 2026

  Degree Bounds for Separating Polynomial and Neural Invariants for Point Clouds

  Snir Hordan, Harm Derksen, Mircea Petrache and 1 other
• arXiv preprint · 5 November 2026

  Common zeros of homogeneous polynomials and the weight hierarchy of projective Reed-Muller codes

  Rodrigo San-José
• arXiv preprint · 9 September 2026

  Streaming Algorithms for Gaussian Kernel Density Statistics

  Qin Zhang
• arXiv preprint · 8 September 2026

  Beyond Cut Balance: Spectral Sparsification of the Nonlinear Directed Laplacian

  Yuichi Yoshida
• arXiv preprint · 9 September 2026

  Scalable Composition of Byzantine Agreements under Reorder Attacks

  Jing Chen, Jin Dong, Jichen Li and 2 others

All new papers in Commutative Algebra