The complexity of sparse Hensel lifting and sparse polynomial factorization

The standard approach to factor a multivariate polynomial in Z [ x 1 , x 2 , … , x n ] is to factor a univariate image in Z [ x 1 ] then recover the multivariate factors from their univariate images using a process known as multivariate Hensel lifting. Wang's multivariate Hensel lifting recovers the variables one at a time. It is currently implemented in many computer algebra systems, including Maple, Magma and Singular. When the factors are sparse, Wang's approach can be exponential in the number of variables n . To address this, sparse Hensel lifting was introduced by Zippel and then improved by Kaltofen. Recently, Monagan and Tuncer introduced a new approach which uses sparse polynomial interpolation to solve the multivariate polynomial diophantine equations that arise inside Hensel lifting in random polynomial time. This approach is shown to be practical and faster than Zippel's and Kaltofen's algorithms and faster than Wang's algorithm for non-zero evaluation points. In this work we first present a complete description of the sparse interpolation used by Monagan and Tuncer and show that it runs in random polynomial time. Next we study what happens to the sparsity of multivariate polynomials when the variables are successively evaluated at numbers. We determine the expected number of remaining terms. We use this result to revisit and correct the complexity analysis of Zippel's original sparse interpolation. Next we present an average case complexity analysis of our approach. We have implemented our algorithm in Maple with some sub-algorithms implemented in C. We present some experimental data comparing our approach with Wang's method for both sparse and dense factors. The data shows that our method is always competitive with Wang's method and faster when Wang's method is exponential in n .