{"id":"arxiv/2609.10626","url":"https://arxiv.org/abs/2609.10626","tags":["math.NT","math.AC"],"score":0,"title":"A New Sparse Algorithm for Polynomial GCD over Integers","domain":"math.NT","source":"arxiv","authors":["Qiao-Long Huang","Michael Monagan"],"reviews":0,"subject":"math.NT","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-09","reactions":{}}