Fast algorithms find common factors in multivariable polynomials
Sparse Polynomial GCD Algorithms Asymptotically Linear in All Fundamental Parameters
Data Structures and Algorithms
Summary
Finding the greatest common divisor of polynomials with many variables and terms is important but computationally hard. This paper presents a method that speeds up this process by carefully using derivatives and a special lifting technique, reducing the number of steps needed. The authors achieve a running time that scales linearly with key polynomial properties, making it efficient even for large inputs. Their approach works for polynomials with integer coefficients as well as those over fields, offering improvements over older algorithms that were slower or less sensitive to output size.
greatest common divisor (GCD)multivariate polynomialbit complexitysparse polynomialHensel liftingderivativemodular reductionrational reconstructioncoefficient sizetotal degree
Authors
Qiao-Long Huang, Xiao-Shan Gao
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.