Skip to Content

Formalizing the LLL Basis Reduction Algorithm and the LLL Factorization Algorithm in Isabelle/HOL

Posted on

Authors:

  • Thiemann, René
  • Bottesch, Ralph
  • Divasón, Jose
  • Haslbeck, Max W.
  • Joosten, Sebastiaan J.
  • Yamada, Akihisa

Published in: Journal of Automated Reasoning pp 827–856

Paper

Abstract:

The LLL basis reduction algorithm was the first polynomial-time algorithm to compute a reduced basis of a given lattice, and hence also a short vector in the lattice. It approximates an NP-hard problem where the approximation quality solely depends on the dimension of the lattice, but not the lattice itself. The algorithm has applications in number theory, computer algebra and cryptography. In this paper, we provide an implementation of the LLL algorithm. Both its soundness and its polynomial running-time have been verified using Isabelle/HOL. Our implementation is nearly as fast as an implementation in a commercial computer algebra system, and its efficiency can be further increased by connecting it with fast untrusted lattice reduction algorithms and certifying their output. We additionally integrate one application of LLL, namely a verified factorization algorithm for univariate integer polynomials which runs in polynomial time.

BibTeX entry:

@article{Thiemann20,
 abstract = {The LLL basis reduction algorithm was the first polynomial-time algorithm to compute a reduced basis of a given lattice, and hence also a short vector in the lattice. It approximates an NP-hard problem where the approximation quality solely depends on the dimension of the lattice, but not the lattice itself. The algorithm has applications in number theory, computer algebra and cryptography. In this paper, we provide an implementation of the LLL algorithm. Both its soundness and its polynomial running-time have been verified using Isabelle/HOL. Our implementation is nearly as fast as an implementation in a commercial computer algebra system, and its efficiency can be further increased by connecting it with fast untrusted lattice reduction algorithms and certifying their output. We additionally integrate one application of LLL, namely a verified factorization algorithm for univariate integer polynomials which runs in polynomial time.},
 author = {Thiemann, Ren{\'e} and Bottesch, Ralph and Divas{\'o}n, Jose and Haslbeck, Max W and Joosten, Sebastiaan JC and Yamada, Akihisa},
 date-added = {2021-09-18 14:47:12 -0400},
 date-modified = {2021-09-18 15:29:49 -0400},
 journal = {Journal of Automated Reasoning},
 month = {Jun},
 number = {5},
 pages = {827--856},
 publisher = {Springer Netherlands},
 title = {Formalizing the LLL Basis Reduction Algorithm and the LLL Factorization Algorithm in Isabelle/HOL},
 volume = {64},
 year = {2020}
}