How to factor a multivariate polynomial.

Michael Monagan, Department of Mathematics, Simon Fraser University

Tuesday 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 Schwartz-Zippel Lemma
and the classical Sylvester Resultant.

This is joint work with Baris Tuncer.