Math. Ann. 261, 515-534 (1982)
Imam
9 Springer-Verlag 1982
Factoring Polynomials with Rational Coefficients
A. K. Lenstra 1, H. W. Lenstra, Jr. 2, and L. Lovfi~z 3
I
1 Mathematisch Centrum, Kruislaan 413, NL-1098 SJ Amsterdam, The Netherlands
2 Mathematisch Instituut, Universiteit van Amsterdam, Roetersstraat 15, NL-1018 WB Amsterdam,
The Netherlands
3 Bolyai Institute, A. J6zsef University, Aradi v6rtan6k tere 1, H-6720 Szeged, Hungary
In this paper we present a polynomial-time algorithm to solve the following
problem: given a non-zero polynomial fe Q[X] in one variable with rational
coefficients, find the decomposition of f into irreducible factors in Q[X]. It is well
known that this is equivalent to factoring
primitive
polynomials
feZ[X]
into
irreducible factors in Z[X]. Here we call f~ Z[X] primitive if the greatest common
divisor of its coefficients (the
content
of f) is 1.
Our algorithm performs well in practice, cf. [8]. Its running time, measured in
bit operations, is
O(nl2+n9(log[fD3).
Here
f~Tl[X]
is the polynomial to be
factored, n = deg(f) is the degree of f, and
for a polynomial ~ a~ i with real coefficients a i.
i
An outline of the algorithm is as follows. First we find, for a suitable small
prime number p, a p-adic irreducible factor h of f, to a certain precision. This is
done with Berlekamp's algorithm for factoring polynomials over small finite fields,
combined with Hensel's lemma. Next we look for the irreducible factor h o of f in
Z[X] that is divisible by h. The condition that h o is divisible by h means that h o
belongs to a certain lattice, and the condition that h o divides f implies that the
coefficients of h o are relatively small. It follows that we must look for a "small"
element in that lattice, and this is done by means of a basis reduction algorithm. It
turns out that this enables us to determine h 0. The algorithm is repeated until all
irreducible factors of f have been found.
The basis reduction algorithm that we employ is new, and it is described and
analysed in Sect. 1. It improves the algorithm given in a preliminary version of [9,
Sect. 3]. At the end of Sect. 1 we briefly mention two applications of the new
algorithm to diophantine approximation.
The connection between factors of f and reduced bases of a lattice is treated in
detail in Sect. 2. The theory presented here extends a result appearing in [8,
Theorem 2]. It should be remarked that the latter result, which is simpler to prove,
would in principle have sufficed for our purpose.
0025-5831/82/026 l/0S 15/$04.00