On Factorization of Multivariate Polynomials over Algebraic Number and Function Fields.

Mahdi Javadi, Computing Science, SFU.

Wednesday March 11th, 3:30pm, in K9509.


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.