- Shuhong Gao, Factoring multivariate polynomials via partial differential equations,
Mathematics of Computation 72 (2003), 801--822.
PS file (502K)
or PDF file (201K)
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
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.
- Shuhong Gao and Virginia M. Rodrigues, Irreducibility of polynomials
modulo p via Newton Polytopes, Journal of Number Theory 101 (2003), 32-47.
PS file (411K) or
PDF file (142K)
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..
- Shuhong Gao and Alan G.B. Lauder, ``Hensel lifting and
of Computation 71 (2002), 1663-1676. PS
file (396K) or PDF
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.
- Shuhong Gao, ``Absolute irreducibility of polynomials via
Newton polytopes,'' J.
of Algebra 237 (2001), 501-520. gzipped
PS file (502K) or PDF
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.
- Shuhong Gao and Alan G.B. Lauder, ``Decomposition of polytopes
and polynomials,'' Discrete and Computational Geometry 26 (2001), 89-104. PS
file (365K) or PDF
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 is NP-complete.
The result remains true even in dimension 2 (i.e. ).
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.
- Fatima Abu Salem, Shuhong Gao and Alan G.B. Lauder, Factoring polynomials via polytopes,
in Proceedings of the 2004
international symposium on Symbolic and algebraic computation
(ISSAC 2004, July 4-7, 2004, University of Cantabria, Santander,
Spain), pp. 4-11. PSfile
(419K) or PDF
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.
- Shuhong Gao, Erich Kaltofen and Alan G.B. Lauder, ``Deterministic
degree factorization for polynomials over finite fields'', to
appear in Journal of Symbolic
Computation (10 pages). PDF
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.
- Shuhong Gao, ``On the deterministic complexity of polynomial factoring,''
J. Symbolic Computation 31 (2001), 19-36.
gzipped PS file (680k)
or PDF file (238K)
- Shuhong Gao and M. Amin Shokrollahi,
``Computing roots of polynomials over function fields of curves,''
in Coding Theory and Cryptography:
From Enigma and Geheimschreiber to Quantum Theory (D. Joyner, Ed.),
Springer, 2000, 214-228.
PS file (79K) or
- Ian F. Blake, Shuhong Gao and Ronald C. Mullin, ``Normal and
normal bases from factorization of cx q+1+dxq -ax
-b,'' SIAM J. on Discrete
Mathematics 7 (1994), 499-512. PDF
- Ian F. Blake, Shuhong Gao and Ronald C. Mullin,``
Explicit factorization of x2^k +1 over Fp with prime
$p \equiv 3 \bmod 4$,''
Applicable Algebra in
Engineering, Communication and Computation 4 (1993), 89--94.
PDF file (81k)