On Factorization of Multivariate Polynomials over Algebraic Number and Function Fields.
Mahdi Javadi, Computing Science, SFU.
Abstract: We present an efficient algorithm for factoring a multivariate polynomial over an algebraic function field with several parameters and multiple field extensions. Our algorithm uses Hensel lifting and extends the EEZ algorithm of Wang which is designed for factorization over rationals. We also give a multivariate p-adic lifting algorithm which uses sparse interpolation. This enables us to avoid using poor bounds on the size of the integer coefficients in the factorization when using Hensel lifting. We have implemented our algorithm in Maple 13. We provide timings demonstrating the efficiency of our algorithm compared to Trager's algorithm.