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.