Interpolation of sparse multivariate polynomials over large finite fields with applications
Ming-Deh A. Huang, Ashwin J. Rao · Symposium on Discrete Algorithms · 1996
We develop a randomized parallel algorithm which performs interpolation of sparse multivariate polynomials over finite fields. Our algorithm can be viewed as the first successful adaptation of the sparse interpolation algorithm for the complex field developed by Ben-Or and Tiwari to the case of finite fields. It improves a previous result of Grigoriev et al. and is by far the most time and space efficient algorithm for the problem when the finite field is large. As applications, we obtain efficient parallel algorithms for sparse multivariate polynomial factorization and GCD over finite fields. The efficiency of these algorithms improves that of the previous known algorithms for the problems.