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 v iewed as the first successful adaptation of the sparse polynomial interpola tion 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 t ime efficient algorithm (time and processor efficient parallel algorithm) f or the problem when the finite field is large. As applications, we obtain M onte Carlo-randomized parallel algorithms for sparse multivariate polynomia l factorization and GCD over finite fields. The efficiency of these algorit hms improves upon that of the previously known algorithms for the respectiv e problems. (C) 1999 Academic Press.