
How to factor a multivariate polynomial.Michael Monagan, Department of Mathematics, Simon Fraser UniversityTuesday December 3rd, 1:30pm in K9509.
Abstract Our computer algebra systems, Magma, Maple, Mathematica, Maxima, Sage and Singular, all use Paul Wang's organization of multivariate Hensel lifting (MHL) to factor a multivariate polynomial. In MHL one solves a sequence of multivariate polynomial Diophantine equations. Wang's algorithm for solving these can be exponential in the number of variables. We have found a new way to solve these equations in polynomial time, that, unlike the previous approaches of Zippel and Kaltofen, is very practical. It reduces solving multivariate polynomial Diophantine equations to evaluating multivariate polynomials at many points and solving Vandermonde linear systems. Our approach is based on an observation that holds with high probability. In the talk I will give an overview of multivariate Hensel lifting and show two tools that we use to bound the probability of failure of our algorithm. The two tools are the SchwartzZippel Lemma and the classical Sylvester Resultant. This is joint work with Baris Tuncer. 