A New Modular Interpolation Algorithm for Factoring Multivariate Polynomials
Rubinfeld, Ronitt; Zippel, Richard
In this paper, we present a technique that uses a new interpolation scheme to reconstruct a multivariate polynomial factorization from a number of univariate factorizations. Whereas other interpolation algorithms for polynomial factorization depend on various extensions of the Hilbert irreducibility theorem, our approach is the first to depend only upon the classical formulation. The key to our technique is the interpolation scheme for multivalued black boxes originally developed by Ar et. al. . We feel that this combination of the classical Hilbert irreducibility theorem and multivalued black boxes provides a particularly simple and intuitive approach to polynomial factorization.
computer science; technical report
Previously Published As