Interpolation of Sparse Multivariate Polynomials over Large Finite Fields with Applications

We develop a Las Vegas-randomized algorithm which performs interpolation of sparse multivariate polynomials over finite fields. Our algorithm can be viewed as the first successful adaptation of the sparse polynomial interpolation algorithm for the complex field developed by M. Ben-Or and P. Tiwari (1988, in “Proceedings of the 20th ACM Symposium on the Theory of Computing,” pp. 301–309, Assoc. Comput. Mach., New York) to the case of finite fields. It improves upon a previous result by D. Y. Grigoriev, M. Karpinski, and M. F. Singer (1990, SIAM J. Comput.19, 1059–1063) and is by far the most time efficient algorithm (time and processor efficient parallel algorithm) for the problem when the finite field is large. As applications, we obtain Monte Carlo-randomized parallel algorithms for sparse multivariate polynomial factorization and GCD over finite fields. The efficiency of these algorithms improves upon that of the previously known algorithms for the respective problems.