Sparse polynomial gcd algorithms achieve linear complexity in key parameters
Sparse Polynomial GCD Algorithms Asymptotically Linear in All Fundamental Parameters
Data Structures and Algorithms
Summary
Calculating the greatest common divisor (GCD) of two complicated polynomials with many variables and large coefficients is usually slow and hard. This paper introduces new algorithms that speed up this process, making it roughly proportional to the size and complexity of the polynomials. The authors use a clever method that leverages derivatives and a special lifting technique, reducing what used to take many steps to just a few. This breakthrough works both for polynomials with coefficients in fields and those with integer coefficients.
What this means in practice
- •For computer algebra engineers: Implement faster gcd computations in symbolic algebra software handling sparse polynomials over integers and fields.
- •For cryptography developers: Improve efficiency of polynomial gcd steps in algebraic cryptanalysis or code-based cryptography algorithms that use sparse polynomial representations.
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.