Sparse Polynomial GCD Algorithms Asymptotically Linear in All Fundamental Parameters

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 \{\mathrm{\parallel }A{\mathrm{\parallel }}_0,\mathrm{\parallel }B{\mathrm{\parallel }}_0,\mathrm{\parallel }G{\mathrm{\parallel }}_0\}$, the total degree $D$, and the logarithmic coefficient sizes $\log \text{Hi}$ and $\log \text{Ho}$, where $\text{Hi}$ bounds the coefficients of the inputs and $\text{Ho}$ bounds those of the GCD. The bit complexity is characterized by the clean bound $$\tilde{O}(n\cdot T\cdot D\cdot \log \text{Hi}\cdot \log \text{Ho})\mathrm{.}$$ 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 \text{K}[x_1,\dots ,x_n]$ over a field $\text{K}$ with $\mathrm{char}(\text{K})=0$ or $\mathrm{char}(\text{K})>\mathrm{°}G$, we give the first algorithm that computes $G=\gcd (A,B)$ with expected $$\tilde{O}(n\cdot T\cdot 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.