Skip to Main content Skip to Navigation
Journal articles

Low-dimensional lattice basis reduction revisited

Phong Q. Nguyen 1, 2 Damien Stehlé 3, 4, *
* Corresponding author
2 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Abstract : Lattice reduction is a geometric generalization of the problem of computing greatest common divisors. Most of the interesting algorithmic problems related to lattice reduction 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 is arguably the most natural lattice basis reduction algorithm, because it is a straightforward generalization of an old two-dimensional algorithm of Lagrange, usually known as Gauss' algorithm, and which is very similar to Euclid's gcd algorithm. Our results are two-fold. From a mathematical point of view, we show that up to dimension four, the output of the greedy algorithm is optimal: the output basis reaches all the successive minima of the lattice. However, as soon as the lattice dimension is strictly higher than four, the output basis may be arbitrarily bad as it may not even reach the first minimum. More importantly, from a computational point of view, we show that up to dimension four, the bit-complexity of the greedy algorithm is quadratic without fast integer arithmetic, just like Euclid's gcd algorithm. This was already proved by Semaev up to dimension three using rather technical means, but it was previously unknown whether or not the algorithm was still polynomial in dimension four. We propose two different analyzes: a global approach based on the geometry of the current basis when the length decrease stalls, and a local approach showing directly that a significant length decrease must occur every O(1) consecutive steps. Our analyzes simplify Semaev's analysis in dimensions two and three, and unify the cases of dimensions two to four. Although the global approach is much simpler, we also present the local approach because it gives further information on the behavior of the algorithm.
Document type :
Journal articles
Complete list of metadata

Cited literature [38 references]  Display  Hide  Download

https://hal.inria.fr/inria-00328629
Contributor : Damien Stehle <>
Submitted on : Monday, February 2, 2009 - 11:47:23 PM
Last modification on : Wednesday, October 14, 2020 - 4:06:01 AM
Long-term archiving on: : Wednesday, September 22, 2010 - 11:23:02 AM

File

journal8.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00328629, version 2

Collections

Citation

Phong Q. Nguyen, Damien Stehlé. Low-dimensional lattice basis reduction revisited. ACM Transactions on Algorithms, Association for Computing Machinery, 2009, To appear, pp.Article 46. ⟨inria-00328629v2⟩

Share

Metrics

Record views

643

Files downloads

1053