Factoring polynomials with rational coeficients
Hendrik W. Lenstra, Arjen K. Lenstra, L. Lovfiasz · Leiden Repository (Leiden University) · 1982
In this paper we present a polynomial-time algonthm to solve the following problem given a non-zero polynomial /eQ[X] m one variable with rational coefficients, find the decomposition of / into irreducible factors m Q[X] It is well known that this is eqmvalent to factormg primitive polynomials /eZ[X] into irreducible factors m TL\X~\ Here we call /eZrjf] primitive if the greatest common divisor of its coefficients (the content of /) is l Our algonthm performs well m practice, cf [8] Its running time, measured m bit operations, is 0(« 12 4 n 9 (log|/|) 3 ) Here /e2£pf] is the polynomial to be factored, n = deg(/) is the degree of /, andfor a polynomial £ α,Κ 1 with real coefficients a, I