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.