Skip to Main content Skip to Navigation
Conference papers

LLL reducing with the most significant bits

Goel Sarushi 1, 2 Ivan Morel 3, 2 Damien Stehlé 3, 2 Gilles Villard 3, 2 
Abstract : Let B be a basis of a Euclidean lattice, and \tilde{B} an approximation thereof. We give a sufficient condition on the closeness between \tilde{B} and B so that an LLL-reducing transformation U for \tilde{B} remains valid for B. Further, we analyse an efficient reduction algorithm when B is itself a small deformation of an LLL-reduced basis. Applications include speeding-up reduction by keeping only the most significant bits of B, reducing a basis that is only approximately known, and effi- ciently batching LLL reductions for closely related inputs.
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download
Contributor : Gilles Villard Connect in order to contact the contributor
Submitted on : Monday, September 5, 2016 - 8:50:21 AM
Last modification on : Friday, September 30, 2022 - 4:12:13 AM
Long-term archiving on: : Tuesday, December 6, 2016 - 12:59:06 PM


Files produced by the author(s)




Goel Sarushi, Ivan Morel, Damien Stehlé, Gilles Villard. LLL reducing with the most significant bits. 39th International Symposium on Symbolic and Algebraic Computation, Kobe, Japan, July 23-25, 2014, Jul 2014, Kobe, Japan. ⟨10.1145/2608628.2608645⟩. ⟨ensl-00993445⟩



Record views


Files downloads