From: Mark van Hoeij 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