Low-dimensional lattice basis reduction revisited

Phong Q. Nguyen 1, 2 Damien Stehlé 3, 4, *
* Auteur correspondant
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.
Type de document :
Article dans une revue
ACM Transactions on Algorithms, Association for Computing Machinery, 2009, To appear, pp.Article 46
Liste complète des métadonnées

Littérature citée [38 références]  Voir  Masquer  Télécharger

Contributeur : Damien Stehle <>
Soumis le : lundi 2 février 2009 - 23:47:23
Dernière modification le : vendredi 28 septembre 2018 - 04:28:03
Document(s) archivé(s) le : mercredi 22 septembre 2010 - 11:23:02


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00328629, version 2



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〉



Consultations de la notice


Téléchargements de fichiers