Factoring polynomials with rational coefficients-英文文献.pdf

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~z3 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 f e 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 Berlekamps algorithm for factoring polynomials over small finite fields, combined with Hensels lemma. Next we look for the