Using Sparse Interpolation in Hensel Lifting.

Baris Tuncer, CECM

4:30pm Wednesday September 8th in K9509.

Abstract
The standard approach for factoring multivariate polynomials in
Z[x1,x2,...,xn] is to factor a univariate image in Z[x1] then lift the
factors of the image one variable at a time using Hensel lifting to
recover the multivariate factors. At each step one must solve a multivariate
polynomial Diophantine equation. For polynomials in many variables
with many terms we find that the time solving these multivariate Diophantine
equations dominates the factorization time. In this talk we explore the use
of sparse interpolation methods, originally introduced by Zippel, to speed
this up.  We present experimental results in Maple showing that we are able
to dramatically speed this up and thereby achieve a good improvement
for multivariate polynomial factorization.