HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

LLL reducing with the most significant bits

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 : Monday, May 16, 2022 - 4:58:02 PM
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