{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T06:26:07Z","timestamp":1748413567259},"reference-count":0,"publisher":"EasyChair","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>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 thereby approximately solves an NP-hard problem. The algorithm has several applications in number theory, computer algebra and cryptography.<\/jats:p><jats:p>Recently, the first mechanized soundness proof of the LLL algorithm has been developed in Isabelle\/HOL. However, this proof did not include a formal statement of the algorithm\u2019s complexity. Furthermore, the resulting implementation was inefficient in practice.<\/jats:p><jats:p>We address both of these shortcomings in this paper. First, we prove the correctness of a more efficient implementation of the LLL algorithm that uses only integer computations. Second, we formally prove statements on the polynomial running-time.<\/jats:p>","DOI":"10.29007\/xwwh","type":"proceedings-article","created":{"date-parts":[[2018,10,23]],"date-time":"2018-10-23T16:06:42Z","timestamp":1540310802000},"page":"164-146","source":"Crossref","is-referenced-by-count":3,"title":["A Verified Efficient Implementation of the LLL Basis Reduction Algorithm"],"prefix":"10.29007","volume":"57","author":[{"given":"Ralph","family":"Bottesch","sequence":"first","affiliation":[]},{"given":"Max W.","family":"Haslbeck","sequence":"additional","affiliation":[]},{"given":"Ren\u00e9","family":"Thiemann","sequence":"additional","affiliation":[]}],"member":"11545","event":{"name":"LPAR-22. 22nd International Conference on Logic for Programming, Artificial Intelligence and Reasoning"},"container-title":["EPiC Series in Computing"],"original-title":[],"deposited":{"date-parts":[[2018,10,23]],"date-time":"2018-10-23T16:06:56Z","timestamp":1540310816000},"score":1,"resource":{"primary":{"URL":"https:\/\/easychair.org\/publications\/paper\/spJt"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"references-count":0,"URL":"https:\/\/doi.org\/10.29007\/xwwh","relation":{},"ISSN":["2398-7340"],"issn-type":[{"type":"print","value":"2398-7340"}],"subject":[]}}