A fast parallel sparse polynomial GCD algorithm

摘要

We present a parallel GCD algorithm for sparse multivariate polynomials with integer coefficients. The algorithm combines a Kronecker substitution with a Ben-Or/Tiwari sparse interpolation modulo a smooth prime to determine the support of the GCD. We have implemented our algorithm in C for primes of various sizes and have parallelized it using Cilk C. We compare our implementation with Maple and Magma's serial implementations of Zippel's GCD algorithm. (C) 2020 Elsevier Ltd. All rights reserved.