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

Low-Dimensional Lattice Reduction Revisited (Extended Abstract)

Phong Q. Nguyen Damien Stehlé 1
1 SPACES - Solving problems through algebraic computation and efficient software
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Most of the interesting algorithmic problems in the geometry of numbers are NP-hard as the lattice dimension increases. This article deals with the low-dimensional case. We study a greedy lattice basis reduction algorithm for the Euclidean norm, which generalizes in a natural way the well-known two-dimensional Gaussian algorithm and a recent three-dimensional algorithm by Semaev. Using this algorithm, we show that up to dimension four, one can compute a Minkowski-reduced basis, a Korkine-Zolotarev-reduced basis, and a closest vector in quadratic time without fast integer arithmetic: all other algorithms known in dimension four have a bit-complexity which is at least cubic. Our analysis, based on geometric properties of low-dimensional lattices and in particular Voronoï cells, arguably simplifies Semaev's analysis in dimension three, but breaks down in dimension five. More precisely, in dimension five or higher, the core algorithm does not necessarily output a Minkowski-reduced basis, and it is unknown whether or not the algorithm is still polynomial.
Document type :
Conference papers
Complete list of metadata

Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 10:15:09 AM
Last modification on : Friday, February 4, 2022 - 3:30:15 AM


  • HAL Id : inria-00100176, version 1



Phong Q. Nguyen, Damien Stehlé. Low-Dimensional Lattice Reduction Revisited (Extended Abstract). 6th International Symposium on Algorithmic Number Theory - ANTS VI, 2004, Burligton, United States. pp.338--357. ⟨inria-00100176⟩



Record views