Factoring polynomials with rational coefficients

From MaRDI portal





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.




Cited in
(only showing first 100 items - show all)








This page was built for publication: Factoring polynomials with rational coefficients

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1165896)