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.
Type de document :
Communication dans un congrès
Duncan Buell. 6th International Symposium on Algorithmic Number Theory - ANTS VI, 2004, Burligton, United States. Springer, 3076, pp.338--357, 2004, Lecture notes in Computer Science
Liste complète des métadonnées

https://hal.inria.fr/inria-00100176
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 10:15:09
Dernière modification le : jeudi 11 janvier 2018 - 06:20:00

Identifiants

  • HAL Id : inria-00100176, version 1

Collections

Citation

Phong Q. Nguyen, Damien Stehlé. Low-Dimensional Lattice Reduction Revisited (Extended Abstract). Duncan Buell. 6th International Symposium on Algorithmic Number Theory - ANTS VI, 2004, Burligton, United States. Springer, 3076, pp.338--357, 2004, Lecture notes in Computer Science. 〈inria-00100176〉

Partager

Métriques

Consultations de la notice

141