Sparse Hensel Lifting Algorithms for Multivariate Polynomial Factorization

Let a be a polynomial in Z[x 1 , ... , x n ] that is represented by a black box. In this thesis, we have designed and implemented a new factorization algorithm that, on input of the black box, outputs the irreducible factors of a in the sparse representation. Our new algorithm based on sparse Hensel lifting applies equally well to general multivariate polynomials, both sparse and dense. We first designed the algorithm for a being monic in x 1 and square-free, then completed the factorization problem by considering a being non-monic, non-square-free, and non-primitive. Our algorithm first finds the factors of the primitive part of a , then the factors of the content of a in the main variable x 1 . We implemented our algorithm in Maple with some subroutines in C. A variety of timing benchmarks are presented. All our timings are much faster than the current best determinant and factorization algorithms in Maple and Magma. We also present a worst-case complexity analysis of our new black box factorization algorithm, along with a failure probability analysis. The case for large integer coefficients has also been considered.