Factoring polynomials with rational coefficients (Q1165896)

This paper describes a polynomial-time algorithm for the factorization of primitive polynomials \(f\in \mathbb Z[X]\) into irreducible factors. The number of bit operations used by the algorithm is \(O(n^{12} + n^9(\log \vert f\vert)^3)\), where \(n\) is the degree of \(f\) and \(\vert \sum_i a_iX^i \vert = (\sum_i a_i^2)^{1/2})\). The result can be generalized to algebraic number fields and to polynomials in several variables. One of the main ingredients of the algorithm is a new basis reduction algorithm for lattices in \(n\)-dimensional space. This basis reduction algorithm can be used to find short vectors in an \(n\)-dimensional lattice. The paper briefly mentions two applications of this algorithm in diophantine approximation. It is also of importance for problems from operations research and cryptography.