Newton-Hensel interpolation lifting (Q2433155)

Lifting theorems and algorithms are of great importance in computer algebra. The best known solution methods for a considerable class of problems, e.g., factorization of polynomials, depend on lifting. The basic idea consists in determining a problem modulo a prime, and then successively improving the solution so that it holds for ever higher powers of this prime, ultimately leading to a solution in the integers. This paper makes an important contribution. It introduces so-called Newton-Hensel lifting, which is a simultaneous lifting of coefficients and terms of the solution polynomials. The methods depends on a certain determinant condition generalizing the well-known Jacobi condition for Hensel lifting. The authors provide possible sets of good starting points for the interpolation. These starting sets are independent of the particular coefficients of the polynomials, so they work for every polynomial of a fixed set of terms. Finally, the results are applied to sparse polynomial interpolation over the integers.