Solving multivariate diophantine equations and their role in multivariate polynomial factorization

Multivariate polynomial factorization over integers via multivariate Hensel lifting (MHL) is one of the central areas of research in computer algebra. Most computer algebra platforms, such as Maple, Magma and Singular, implement Wang's incremental design of MHL which lifts the factors one variable at a time and one degree at a time. At each step MHL must solve a multivariate diophantine problem (MDP) which Wang solves using the same idea; lifting the solutions one variable and one degree at a time. Although this performs well when the evaluation points are mostly zero, it performs poorly when there are many non-zero evaluation points as the number of MDP problems to be solved can be exponential in the number of variables. In this thesis we introduce a new non-recursive solution to the MDP which explicitly exploits the sparsity of the solutions to the MDP. We use sparse interpolation techniques and exploit the fact that at each step of MHL, the solutions to MDP's are structurally related. We design a probabilistic sparse Hensel lifting algorithm (MTSHL) and give a complete average case complexity analysis for it. We describe a series of experiments based on our implementation of MTSHL, compare its efficiency with Wang's algorithm, and show that MTSHL performs better for many practical applications. We also show that previous probabilistic approaches proposed for MHL as an alternative to Wang's algorithm are not practical whereas MTSHL is practical and the running time is predictable.