A New black box GCD algorithm using Hensel lifting

Garrett Paluck, Mathematics, Simon Fraser University

Tuesday July 8th at 9:30am-10:00am in RCB 7105

We present a new black box GCD algorithm for two multivariate polynomials a and b in Z[x1, x2, ... ,xn] where a and b are input as black boxes for their evaluation. Our algorithm computes g = gcd(a,b) in the sparse representation using sparse Hensel lifting from bivariate images of g. More precisely, our algorithm first computes the square-free factorization of the primitive part of g in x1 and then, optionally, computes the content of g in x1 recursively. We have implemented our new algorithm in Maple with parts of it coded in C for increased efficiency. For comparison, we have implemented the Kaltofen-Diaz black box GCD algorithm and also a black box GCD algorithm constructed from the Kaltofen-Yang sparse rational function interpolation algorithm. Our experimental results show that our new algorithm is always competitive with the Kaltofen-Yang and Kaltofen-Diaz algorithms and faster when the square-free factors of g are smaller than g or we do not need the content of g in x1.