A verified factorization algorithm for integer polynomials with polynomial complexity. 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.
Keywords for this software
References in zbMATH (referenced in 2 articles )
Showing results 1 to 2 of 2.
- Thiemann, René; Bottesch, Ralph; Divasón, Jose; Haslbeck, Max W.; Joosten, Sebastiaan J. C.; Yamada, Akihisa: Formalizing the LLL basis reduction algorithm and the LLL factorization algorithm in Isabelle/HOL (2020)
- Divasón, Jose; Joosten, Sebastiaan; Thiemann, René; Yamada, Akihisa: A formalization of the LLL basis reduction algorithm (2018)