A New Sparse Algorithm for Polynomial GCD over Integers
Abstract
We describe a new greatest common divisor (GCD) algorithm for polynomials with integer coefficients. The bit complexity of the new algorithm is polynomial in the input and output sizes and the individual degree bounds.Our algorithm follows the standard approach by reducing multivariate polynomial GCD to univariate polynomial GCD. Our algorithm reduces a multivariate polynomial GCD to a single univariate polynomial GCD. The main idea of our algorithm is a new variable substitution which reduces a multivariate polynomial to a separated one, that is, the coefficients in a main variable are all monomials. The explicit bit complexity is analyzed and we have implemented our algorithm in Maple. It is shown that our algorithm is efficient for polynomials with high degree, large number of variables, but small number of terms in GCD.
Related
- Wallis-type products with polynomial exponents and the Dirichlet beta function at negative integers
- Ten unknowns for Hilbert's tenth problem over the integers
- Wild frieze patterns over the integers
- The zeroth stable homotopy groups of motivic spheres over the integers
- Extension of solvable coverings across horizontal divisors over the integers
BibTeX
@misc{huang2026sparse,
title = {{A New Sparse Algorithm for Polynomial GCD over Integers}},
author = {Qiao-Long Huang and Michael Monagan},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.10626},
eprint = {2609.10626},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.10626},
}
RIS
TY - UNPB
TI - A New Sparse Algorithm for Polynomial GCD over Integers
AU - Qiao-Long Huang
AU - Michael Monagan
PY - 2026
DA - 2026/09/09
PB - arXiv
DO - 10.48550/arxiv.2609.10626
UR - https://arxiv.org/abs/2609.10626
AB - We describe a new greatest common divisor (GCD) algorithm for polynomials with integer coefficients. The bit complexity of the new algorithm is polynomial in the input and output sizes and the individual degree bounds.Our algorithm follows the standard approach by reducing multivariate polynomial GCD to univariate polynomial GCD. Our algorithm reduces a multivariate polynomial GCD to a single univariate polynomial GCD. The main idea of our algorithm is a new variable substitution which reduces a multivariate polynomial to a separated one, that is, the coefficients in a main variable are all monomials. The explicit bit complexity is analyzed and we have implemented our algorithm in Maple. It is shown that our algorithm is efficient for polynomials with high degree, large number of variables, but small number of terms in GCD.
ER -