A New Sparse Polynomial GCD by Separating Terms
Michael Monagan, CECM Research Center, Simon Fraser University
Tuesday October 1st, 10:30am-11:20am in AQ 5004
Abstract: We propose a new sparse GCD algorithm for multivariate polynomials over finite fields. Our algorithm uses a new type of substitution to recover the terms of the GCD in batches. We present a detailed complexity analysis and experimental results which show that our algorithm is faster than Zippel’s GCD algorithm and competitive with the Monagan-Hu GCD algorithm.
This is joint work with Qiao-Long Huang of Shandong University, China.