Sparse Polynomial GCD Algorithms Asymptotically Linear in All Fundamental Parameters

Qiao-Long Huang, Xiao-Shan Gao

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…