The problem of factoring multivariate polynomials can be distinguished as rational factorization and absolute factorization. The first is over the ground field while the latter over the algebraic closure. In this paper, we give a new method based on partial differential equations for both rational and absolute factorization. This method is in some sense a parallel theory for bivariate polynomials to those of Berlekamp and Niederreiter for univariate polynomials. Such a method had been sought after ever since Niederreiter discovered his method using ordinary differential equations. For both rational and absolute factorization, our method has a near quadratic time complexity.

Effective Hilbert irreducibility theorems in most number theory and algebraic geometry books are not effective. Explicit bounds are desirable in practical computation. Our PDE method gives a simple bound on the probability that an irreducible multivariate polynomials remains irreducible under a random linear substitution in two variables (so the resulted polynomial is bivariate). Our bound significantly improves previous bounds.

Ostrowski established in 1919 that an absolutely irreducible integral polynomial remains absolutely irreducible modulo all sufficiently large prime numbers. In this paper, we give an explicit bound for such primes in term of the coefficient size and the Newton polytope of the polynomial. This the first result that is able to exploit the possible sparseness of the polynomial, and it significantly improves previous estimates for sparse polynomials..

It is well known that the Hensel lifting technique provides practical methods for factoring polynomials over various fields. Such methods are known to run in exponential time in the worst case, but seem fast for most polynomials. The latter phenomenon has not been fully understood and calls for an average running time analysis. The only analysis we know of is that of Collins (1979) for univariate integral polynomials (factoring over the rational numbers). He shows, under some reasonable number theoretic conjectures, that the average running time is indeed polynomial. In this paper, we present a rigorous analysis for bivariate polynomials over finite fields. We show that the average running time is almost linear in the input size. This explains for the first time why the Hensel lifting technique is fast in practice for bivariate polynomials over finite fields.

In this paper, we introduce the concept of integral indecomposability of polytopes and obtain a simple but extremely useful irreducibility criterion for polynomials. We give two general constructions of indecomposable polytopes which allows explicit constructions of many families of absolutely irreducible polynomials. These constructions include the well-known criteria of Eisenstein (1850), Dumas (1906) and Stepanov-Schmidt (1976) as special cases.

In this paper, we discuss the computational complexity of decomposing polytopes and its implications in factoring polynomials. We prove that the problem of deciding decomposability of integral polytopes in $R^n$ is NP-complete. The result remains true even in dimension 2 (i.e. $n=2$). Here the input size is the binary representations of the coordinates of the vertices of the polytopes. This corresponds to sparse representation of polynomials. We give a deterministic algorithm for decomposing polygons, with running time almost linear in the areas of the polygons, so a quasi-polynomial time algorithm. For higher dimensions, we use a projection lemma of ours to design an efficient probabilistic algorithm for testing indecomposability of Newton polytopes, so an algorithm for testing absolute irreducibility of multivariate polynomials.

We present an algorithm to factor multivariate polynomial via polytope decomposition. This method generalizes the classical Hensel lifting and it is able to exploit to some extent the sparsity of polynomials. Similar to Hensel lifting, our algorithm has exponential time complexity but is practical for a large class of polynomials. Our implementation can factor randomly chosen sparse bivariate polynomials of high degrees (2000, say) over the binary field.

We present a deterministic polynomial time algorithm for finding the distinct-degree factorization of multivariate polynomials over finite fields. As a consequence, one can count the number of irreducible factors of polynomials over finite fields in deterministic polynomial time, thus resolving an open problem of Kaltofen from 1987.