Abstract
Short vectors in lattices and factors of integer polynomials are
related. Each factor of an integer polynomial belongs to a certain
lattice. When factoring polynomials, the condition that we are looking
for an irreducible polynomial means that we must look for a small
element in a lattice, which can be done by a basis reduction
algorithm. In this development we formalize this connection and
thereby one main application of the LLL basis reduction algorithm: an
algorithm to factor square-free integer polynomials which runs in
polynomial time. The work is based on our previous
Berlekamp–Zassenhaus development, where the exponential reconstruction
phase has been replaced by the polynomial-time basis reduction
algorithm. Thanks to this formalization we found a serious flaw in a
textbook.
BSD LicenseTopics
Theories of LLL_Factorization
- Factor_Bound_2
- Missing_Dvd_Int_Poly
- LLL_Factorization_Impl
- LLL_Factorization
- Sub_Sums
- Factorization_Algorithm_16_22
- Modern_Computer_Algebra_Problem