From: Mark van Hoeij <hoeij@sci.kun.nl>
Date: Mon, 24 Apr 1995 23:35:24 +0200
To: rusin@math.niu.edu
Subject: Re: L3 code part of any popular package?

> I guess I usually try to factor the (integer) values of a polynomial at
Factorization of integers is much harder than factorization of polynomials.

Do you know the Berlekamp algorithm for factorization in finite fields?
This has a polynomial time complexity. Using this algorithm a polynomial
f in Z[x] can be factored in Z/pZ [x]. Then one can lift this to
a factorization in Z/p^2Z [x], then mod p^3, mod p^4 etcetera, up to
some bound. Then you take some of the mod p^n factors, multiply them, and
hope to get a factor in Z[x]. This is exponential time in theory, because
you can have an exponential number of combinations to check.
But what often happens in practise is that the number of factors in
Z/pZ [x] is not much larger than the number of factors in Z[x]. Then not
many combinations need to be checked to get a factorization.
So in theory the complexity is exponential, but in practise it is often
quite good.
Bad examples are obtained by taking an irreducible polynomial f in Z[x]
which has many different factors modulo every p.
For example: take r = sqrt(-1) + sqrt(2) + sqrt(3) + sqrt(5) + sqrt(7)
+ sqrt(11). Let f be the minimal polynomial of r over Z. Obviously f is
irreducible. But modulo p the factors of f have degree <=2, hence there are
a lot of factors. So this is an example where the traditional method,
using the Hensel lifting mod p^1, mod p^2, .. and combining the factors, 
that this method takes a long time.
On the other hand, the polynomial time LLL based method will take lots of
time as well since the degree of f is large, and the complexity, though
polynomial time, is actually pretty bad.

Mark van Hoeij