Low-dimensional lattice basis reduction revisited
Identifieur interne :
000668 ( PascalFrancis/Corpus );
précédent :
000667;
suivant :
000669
Low-dimensional lattice basis reduction revisited
Auteurs : Phong Q. Nguyen ;
Damien StehleSource :
-
Lecture notes in computer science [ 0302-9743 ] ; 2004.
RBID : Pascal:04-0301103
Descripteurs français
- Pascal (Inist)
- Treillis,
Géométrie algorithmique,
Problème NP difficile,
Algorithme glouton,
Théorie euclidienne,
Modèle 2 dimensions,
Processus Gauss,
Algorithme optimal,
Complexité algorithme,
Algorithme rapide,
Arithmétique,
Métrique Minkowski,
Modèle 3 dimensions,
Méthode polynomiale,
Diagramme Voronoï,
Cubique.
English descriptors
- KwdEn :
- Algorithm complexity,
Arithmetics,
Computational geometry,
Cubics,
Euclidean theory,
Fast algorithm,
Gaussian process,
Greedy algorithm,
Lattice,
Minkowski metric,
NP hard problem,
Optimal algorithm,
Polynomial method,
Three dimensional model,
Two dimensional model,
Voronoï diagram.
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 is arguably the most natural lattice basis reduction algorithm, because it is a straightforward generalization of the well-known two-dimensional Gaussian 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 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: this allows to compute various lattice problems (e.g. computing a Minkowski-reduced basis and a closest vector) in quadratic time, without fast integer arithmetic, up to dimension four, while all other algorithms known for such problems have a bit-complexity which is at least cubic. 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. Our analysis, based on geometric properties of low-dimensional lattices and in particular Voronoï cells, arguably simplifies Semaev's analysis in dimensions two and three, unifies the cases of dimensions two, three and four, but breaks down in dimension five.
Notice en format standard (ISO 2709)
Pour connaître la documentation sur le format Inist Standard.
| pA |
| A01 | 01 | 1 | | @0 0302-9743 |
|---|
| A05 | | | | @2 3076 |
|---|
| A08 | 01 | 1 | ENG | @1 Low-dimensional lattice basis reduction revisited |
|---|
| A09 | 01 | 1 | ENG | @1 ANTS - VI : algorithmic number theory : Burlington VT, 13-18 June 2004 |
|---|
| A11 | 01 | 1 | | @1 NGUYEN (Phong Q.) |
|---|
| A11 | 02 | 1 | | @1 STEHLE (Damien) |
|---|
| A12 | 01 | 1 | | @1 BUELL (Duncan) @9 ed. |
|---|
| A14 | 01 | | | @1 CNRS/École normale supérieure, Département d'informatique, 45 rue d'Ulm @2 75230 Paris @3 FRA @Z 1 aut. |
|---|
| A14 | 02 | | | @1 LORIA/INRIA Lorraine, 615 rue du J. botanique @2 54602 Villers-lès-Nancy @3 FRA @Z 2 aut. |
|---|
| A20 | | | | @1 338-357 |
|---|
| A21 | | | | @1 2004 |
|---|
| A23 | 01 | | | @0 ENG |
|---|
| A26 | 01 | | | @0 3-540-22156-5 |
|---|
| A43 | 01 | | | @1 INIST @2 16343 @5 354000117887920260 |
|---|
| A44 | | | | @0 0000 @1 © 2004 INIST-CNRS. All rights reserved. |
|---|
| A45 | | | | @0 30 ref. |
|---|
| A47 | 01 | 1 | | @0 04-0301103 |
|---|
| A60 | | | | @1 P @2 C |
|---|
| A61 | | | | @0 A |
|---|
| A64 | 01 | 1 | | @0 Lecture notes in computer science |
|---|
| A66 | 01 | | | @0 DEU |
|---|
| C01 | 01 | | ENG | @0 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 is arguably the most natural lattice basis reduction algorithm, because it is a straightforward generalization of the well-known two-dimensional Gaussian 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 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: this allows to compute various lattice problems (e.g. computing a Minkowski-reduced basis and a closest vector) in quadratic time, without fast integer arithmetic, up to dimension four, while all other algorithms known for such problems have a bit-complexity which is at least cubic. 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. Our analysis, based on geometric properties of low-dimensional lattices and in particular Voronoï cells, arguably simplifies Semaev's analysis in dimensions two and three, unifies the cases of dimensions two, three and four, but breaks down in dimension five. |
|---|
| C02 | 01 | X | | @0 001A02C02 |
|---|
| C02 | 02 | X | | @0 001D04A04E |
|---|
| C02 | 03 | X | | @0 001D02B07C |
|---|
| C03 | 01 | X | FRE | @0 Treillis @5 09 |
|---|
| C03 | 01 | X | ENG | @0 Lattice @5 09 |
|---|
| C03 | 01 | X | SPA | @0 Enrejado @5 09 |
|---|
| C03 | 02 | X | FRE | @0 Géométrie algorithmique @5 10 |
|---|
| C03 | 02 | X | ENG | @0 Computational geometry @5 10 |
|---|
| C03 | 02 | X | SPA | @0 Geometría computacional @5 10 |
|---|
| C03 | 03 | X | FRE | @0 Problème NP difficile @5 23 |
|---|
| C03 | 03 | X | ENG | @0 NP hard problem @5 23 |
|---|
| C03 | 03 | X | SPA | @0 Problema NP duro @5 23 |
|---|
| C03 | 04 | X | FRE | @0 Algorithme glouton @5 24 |
|---|
| C03 | 04 | X | ENG | @0 Greedy algorithm @5 24 |
|---|
| C03 | 04 | X | SPA | @0 Algoritmo glotón @5 24 |
|---|
| C03 | 05 | X | FRE | @0 Théorie euclidienne @5 25 |
|---|
| C03 | 05 | X | ENG | @0 Euclidean theory @5 25 |
|---|
| C03 | 05 | X | SPA | @0 Teoría euclidiana @5 25 |
|---|
| C03 | 06 | X | FRE | @0 Modèle 2 dimensions @5 26 |
|---|
| C03 | 06 | X | ENG | @0 Two dimensional model @5 26 |
|---|
| C03 | 06 | X | SPA | @0 Modelo 2 dimensiones @5 26 |
|---|
| C03 | 07 | X | FRE | @0 Processus Gauss @5 27 |
|---|
| C03 | 07 | X | ENG | @0 Gaussian process @5 27 |
|---|
| C03 | 07 | X | SPA | @0 Proceso Gauss @5 27 |
|---|
| C03 | 08 | X | FRE | @0 Algorithme optimal @5 28 |
|---|
| C03 | 08 | X | ENG | @0 Optimal algorithm @5 28 |
|---|
| C03 | 08 | X | SPA | @0 Algoritmo óptimo @5 28 |
|---|
| C03 | 09 | X | FRE | @0 Complexité algorithme @5 29 |
|---|
| C03 | 09 | X | ENG | @0 Algorithm complexity @5 29 |
|---|
| C03 | 09 | X | SPA | @0 Complejidad algoritmo @5 29 |
|---|
| C03 | 10 | X | FRE | @0 Algorithme rapide @5 32 |
|---|
| C03 | 10 | X | ENG | @0 Fast algorithm @5 32 |
|---|
| C03 | 10 | X | SPA | @0 Algoritmo rápido @5 32 |
|---|
| C03 | 11 | X | FRE | @0 Arithmétique @5 33 |
|---|
| C03 | 11 | X | ENG | @0 Arithmetics @5 33 |
|---|
| C03 | 11 | X | SPA | @0 Aritmética @5 33 |
|---|
| C03 | 12 | X | FRE | @0 Métrique Minkowski @5 34 |
|---|
| C03 | 12 | X | ENG | @0 Minkowski metric @5 34 |
|---|
| C03 | 12 | X | SPA | @0 Métrico Minkowski @5 34 |
|---|
| C03 | 13 | X | FRE | @0 Modèle 3 dimensions @5 35 |
|---|
| C03 | 13 | X | ENG | @0 Three dimensional model @5 35 |
|---|
| C03 | 13 | X | SPA | @0 Modelo 3 dimensiones @5 35 |
|---|
| C03 | 14 | X | FRE | @0 Méthode polynomiale @5 36 |
|---|
| C03 | 14 | X | ENG | @0 Polynomial method @5 36 |
|---|
| C03 | 14 | X | SPA | @0 Método polinomial @5 36 |
|---|
| C03 | 15 | X | FRE | @0 Diagramme Voronoï @5 37 |
|---|
| C03 | 15 | X | ENG | @0 Voronoï diagram @5 37 |
|---|
| C03 | 15 | X | SPA | @0 Diagrama Voronoi @5 37 |
|---|
| C03 | 16 | X | FRE | @0 Cubique @4 CD @5 96 |
|---|
| C03 | 16 | X | ENG | @0 Cubics @4 CD @5 96 |
|---|
| C03 | 16 | X | SPA | @0 Cúbico @4 CD @5 96 |
|---|
| N21 | | | | @1 180 |
|---|
| N44 | 01 | | | @1 OTO |
|---|
| N82 | | | | @1 OTO |
|---|
|
|---|
| pR |
| A30 | 01 | 1 | ENG | @1 Algorithmic number theory. International symposium @2 6 @3 Burlington VT USA @4 2004-06-13 |
|---|
|
|---|
Format Inist (serveur)
| NO : | PASCAL 04-0301103 INIST |
|---|
| ET : | Low-dimensional lattice basis reduction revisited |
|---|
| AU : | NGUYEN (Phong Q.); STEHLE (Damien); BUELL (Duncan) |
|---|
| AF : | CNRS/École normale supérieure, Département d'informatique, 45 rue d'Ulm/75230 Paris/France (1 aut.); LORIA/INRIA Lorraine, 615 rue du J. botanique/54602 Villers-lès-Nancy/France (2 aut.) |
|---|
| DT : | Publication en série; Congrès; Niveau analytique |
|---|
| SO : | Lecture notes in computer science; ISSN 0302-9743; Allemagne; Da. 2004; Vol. 3076; Pp. 338-357; Bibl. 30 ref. |
|---|
| LA : | Anglais |
|---|
| EA : | 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 is arguably the most natural lattice basis reduction algorithm, because it is a straightforward generalization of the well-known two-dimensional Gaussian 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 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: this allows to compute various lattice problems (e.g. computing a Minkowski-reduced basis and a closest vector) in quadratic time, without fast integer arithmetic, up to dimension four, while all other algorithms known for such problems have a bit-complexity which is at least cubic. 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. Our analysis, based on geometric properties of low-dimensional lattices and in particular Voronoï cells, arguably simplifies Semaev's analysis in dimensions two and three, unifies the cases of dimensions two, three and four, but breaks down in dimension five. |
|---|
| CC : | 001A02C02; 001D04A04E; 001D02B07C |
|---|
| FD : | Treillis; Géométrie algorithmique; Problème NP difficile; Algorithme glouton; Théorie euclidienne; Modèle 2 dimensions; Processus Gauss; Algorithme optimal; Complexité algorithme; Algorithme rapide; Arithmétique; Métrique Minkowski; Modèle 3 dimensions; Méthode polynomiale; Diagramme Voronoï; Cubique |
|---|
| ED : | Lattice; Computational geometry; NP hard problem; Greedy algorithm; Euclidean theory; Two dimensional model; Gaussian process; Optimal algorithm; Algorithm complexity; Fast algorithm; Arithmetics; Minkowski metric; Three dimensional model; Polynomial method; Voronoï diagram; Cubics |
|---|
| SD : | Enrejado; Geometría computacional; Problema NP duro; Algoritmo glotón; Teoría euclidiana; Modelo 2 dimensiones; Proceso Gauss; Algoritmo óptimo; Complejidad algoritmo; Algoritmo rápido; Aritmética; Métrico Minkowski; Modelo 3 dimensiones; Método polinomial; Diagrama Voronoi; Cúbico |
|---|
| LO : | INIST-16343.354000117887920260 |
|---|
| ID : | 04-0301103 |
|---|
Links to Exploration step
Pascal:04-0301103
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Low-dimensional lattice basis reduction revisited</title>
<author><name sortKey="Nguyen, Phong Q" sort="Nguyen, Phong Q" uniqKey="Nguyen P" first="Phong Q." last="Nguyen">Phong Q. Nguyen</name>
<affiliation><inist:fA14 i1="01"><s1>CNRS/École normale supérieure, Département d'informatique, 45 rue d'Ulm</s1>
<s2>75230 Paris</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14><author><name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehle">Damien Stehle</name>
<affiliation><inist:fA14 i1="02"><s1>LORIA/INRIA Lorraine, 615 rue du J. botanique</s1>
<s2>54602 Villers-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</inist:fA14><publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">04-0301103</idno>
<date when="2004">2004</date>
<idno type="stanalyst">PASCAL 04-0301103 INIST</idno>
<idno type="RBID">Pascal:04-0301103</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000668</idno>
</publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Low-dimensional lattice basis reduction revisited</title>
<author><name sortKey="Nguyen, Phong Q" sort="Nguyen, Phong Q" uniqKey="Nguyen P" first="Phong Q." last="Nguyen">Phong Q. Nguyen</name>
<affiliation><inist:fA14 i1="01"><s1>CNRS/École normale supérieure, Département d'informatique, 45 rue d'Ulm</s1>
<s2>75230 Paris</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14><author><name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehle">Damien Stehle</name>
<affiliation><inist:fA14 i1="02"><s1>LORIA/INRIA Lorraine, 615 rue du J. botanique</s1>
<s2>54602 Villers-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</inist:fA14><series><title level="j" type="main">Lecture notes in computer science</title>
<idno type="ISSN">0302-9743</idno>
<imprint><date when="2004">2004</date>
</imprint><seriesStmt><title level="j" type="main">Lecture notes in computer science</title>
<idno type="ISSN">0302-9743</idno>
</seriesStmt><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm complexity</term>
<term>Arithmetics</term>
<term>Computational geometry</term>
<term>Cubics</term>
<term>Euclidean theory</term>
<term>Fast algorithm</term>
<term>Gaussian process</term>
<term>Greedy algorithm</term>
<term>Lattice</term>
<term>Minkowski metric</term>
<term>NP hard problem</term>
<term>Optimal algorithm</term>
<term>Polynomial method</term>
<term>Three dimensional model</term>
<term>Two dimensional model</term>
<term>Voronoï diagram</term>
</keywords><keywords scheme="Pascal" xml:lang="fr"><term>Treillis</term>
<term>Géométrie algorithmique</term>
<term>Problème NP difficile</term>
<term>Algorithme glouton</term>
<term>Théorie euclidienne</term>
<term>Modèle 2 dimensions</term>
<term>Processus Gauss</term>
<term>Algorithme optimal</term>
<term>Complexité algorithme</term>
<term>Algorithme rapide</term>
<term>Arithmétique</term>
<term>Métrique Minkowski</term>
<term>Modèle 3 dimensions</term>
<term>Méthode polynomiale</term>
<term>Diagramme Voronoï</term>
<term>Cubique</term>
</keywords><front><div type="abstract" xml:lang="en">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 is arguably the most natural lattice basis reduction algorithm, because it is a straightforward generalization of the well-known two-dimensional Gaussian 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 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: this allows to compute various lattice problems (e.g. computing a Minkowski-reduced basis and a closest vector) in quadratic time, without fast integer arithmetic, up to dimension four, while all other algorithms known for such problems have a bit-complexity which is at least cubic. 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. Our analysis, based on geometric properties of low-dimensional lattices and in particular Voronoï cells, arguably simplifies Semaev's analysis in dimensions two and three, unifies the cases of dimensions two, three and four, but breaks down in dimension five.</div>
</front><inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0302-9743</s0>
</fA01><fA05><s2>3076</s2>
</fA05><fA08 i1="01" i2="1" l="ENG"><s1>Low-dimensional lattice basis reduction revisited</s1>
</fA08><fA09 i1="01" i2="1" l="ENG"><s1>ANTS - VI : algorithmic number theory : Burlington VT, 13-18 June 2004</s1>
</fA09><fA11 i1="01" i2="1"><s1>NGUYEN (Phong Q.)</s1>
</fA11><fA11 i1="02" i2="1"><s1>STEHLE (Damien)</s1>
</fA11><fA12 i1="01" i2="1"><s1>BUELL (Duncan)</s1>
<s9>ed.</s9>
</fA12><fA14 i1="01"><s1>CNRS/École normale supérieure, Département d'informatique, 45 rue d'Ulm</s1>
<s2>75230 Paris</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</fA14><fA14 i1="02"><s1>LORIA/INRIA Lorraine, 615 rue du J. botanique</s1>
<s2>54602 Villers-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</fA14><fA20><s1>338-357</s1>
</fA20><fA21><s1>2004</s1>
</fA21><fA23 i1="01"><s0>ENG</s0>
</fA23><fA26 i1="01"><s0>3-540-22156-5</s0>
</fA26><fA43 i1="01"><s1>INIST</s1>
<s2>16343</s2>
<s5>354000117887920260</s5>
</fA43><fA44><s0>0000</s0>
<s1>© 2004 INIST-CNRS. All rights reserved.</s1>
</fA44><fA45><s0>30 ref.</s0>
</fA45><fA47 i1="01" i2="1"><s0>04-0301103</s0>
</fA47><fA60><s1>P</s1>
<s2>C</s2>
</fA60><fA64 i1="01" i2="1"><s0>Lecture notes in computer science</s0>
</fA64><fA66 i1="01"><s0>DEU</s0>
</fA66><fC01 i1="01" l="ENG"><s0>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 is arguably the most natural lattice basis reduction algorithm, because it is a straightforward generalization of the well-known two-dimensional Gaussian 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 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: this allows to compute various lattice problems (e.g. computing a Minkowski-reduced basis and a closest vector) in quadratic time, without fast integer arithmetic, up to dimension four, while all other algorithms known for such problems have a bit-complexity which is at least cubic. 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. Our analysis, based on geometric properties of low-dimensional lattices and in particular Voronoï cells, arguably simplifies Semaev's analysis in dimensions two and three, unifies the cases of dimensions two, three and four, but breaks down in dimension five.</s0>
</fC01><fC02 i1="01" i2="X"><s0>001A02C02</s0>
</fC02><fC02 i1="02" i2="X"><s0>001D04A04E</s0>
</fC02><fC02 i1="03" i2="X"><s0>001D02B07C</s0>
</fC02><fC03 i1="01" i2="X" l="FRE"><s0>Treillis</s0>
<s5>09</s5>
</fC03><fC03 i1="01" i2="X" l="ENG"><s0>Lattice</s0>
<s5>09</s5>
</fC03><fC03 i1="01" i2="X" l="SPA"><s0>Enrejado</s0>
<s5>09</s5>
</fC03><fC03 i1="02" i2="X" l="FRE"><s0>Géométrie algorithmique</s0>
<s5>10</s5>
</fC03><fC03 i1="02" i2="X" l="ENG"><s0>Computational geometry</s0>
<s5>10</s5>
</fC03><fC03 i1="02" i2="X" l="SPA"><s0>Geometría computacional</s0>
<s5>10</s5>
</fC03><fC03 i1="03" i2="X" l="FRE"><s0>Problème NP difficile</s0>
<s5>23</s5>
</fC03><fC03 i1="03" i2="X" l="ENG"><s0>NP hard problem</s0>
<s5>23</s5>
</fC03><fC03 i1="03" i2="X" l="SPA"><s0>Problema NP duro</s0>
<s5>23</s5>
</fC03><fC03 i1="04" i2="X" l="FRE"><s0>Algorithme glouton</s0>
<s5>24</s5>
</fC03><fC03 i1="04" i2="X" l="ENG"><s0>Greedy algorithm</s0>
<s5>24</s5>
</fC03><fC03 i1="04" i2="X" l="SPA"><s0>Algoritmo glotón</s0>
<s5>24</s5>
</fC03><fC03 i1="05" i2="X" l="FRE"><s0>Théorie euclidienne</s0>
<s5>25</s5>
</fC03><fC03 i1="05" i2="X" l="ENG"><s0>Euclidean theory</s0>
<s5>25</s5>
</fC03><fC03 i1="05" i2="X" l="SPA"><s0>Teoría euclidiana</s0>
<s5>25</s5>
</fC03><fC03 i1="06" i2="X" l="FRE"><s0>Modèle 2 dimensions</s0>
<s5>26</s5>
</fC03><fC03 i1="06" i2="X" l="ENG"><s0>Two dimensional model</s0>
<s5>26</s5>
</fC03><fC03 i1="06" i2="X" l="SPA"><s0>Modelo 2 dimensiones</s0>
<s5>26</s5>
</fC03><fC03 i1="07" i2="X" l="FRE"><s0>Processus Gauss</s0>
<s5>27</s5>
</fC03><fC03 i1="07" i2="X" l="ENG"><s0>Gaussian process</s0>
<s5>27</s5>
</fC03><fC03 i1="07" i2="X" l="SPA"><s0>Proceso Gauss</s0>
<s5>27</s5>
</fC03><fC03 i1="08" i2="X" l="FRE"><s0>Algorithme optimal</s0>
<s5>28</s5>
</fC03><fC03 i1="08" i2="X" l="ENG"><s0>Optimal algorithm</s0>
<s5>28</s5>
</fC03><fC03 i1="08" i2="X" l="SPA"><s0>Algoritmo óptimo</s0>
<s5>28</s5>
</fC03><fC03 i1="09" i2="X" l="FRE"><s0>Complexité algorithme</s0>
<s5>29</s5>
</fC03><fC03 i1="09" i2="X" l="ENG"><s0>Algorithm complexity</s0>
<s5>29</s5>
</fC03><fC03 i1="09" i2="X" l="SPA"><s0>Complejidad algoritmo</s0>
<s5>29</s5>
</fC03><fC03 i1="10" i2="X" l="FRE"><s0>Algorithme rapide</s0>
<s5>32</s5>
</fC03><fC03 i1="10" i2="X" l="ENG"><s0>Fast algorithm</s0>
<s5>32</s5>
</fC03><fC03 i1="10" i2="X" l="SPA"><s0>Algoritmo rápido</s0>
<s5>32</s5>
</fC03><fC03 i1="11" i2="X" l="FRE"><s0>Arithmétique</s0>
<s5>33</s5>
</fC03><fC03 i1="11" i2="X" l="ENG"><s0>Arithmetics</s0>
<s5>33</s5>
</fC03><fC03 i1="11" i2="X" l="SPA"><s0>Aritmética</s0>
<s5>33</s5>
</fC03><fC03 i1="12" i2="X" l="FRE"><s0>Métrique Minkowski</s0>
<s5>34</s5>
</fC03><fC03 i1="12" i2="X" l="ENG"><s0>Minkowski metric</s0>
<s5>34</s5>
</fC03><fC03 i1="12" i2="X" l="SPA"><s0>Métrico Minkowski</s0>
<s5>34</s5>
</fC03><fC03 i1="13" i2="X" l="FRE"><s0>Modèle 3 dimensions</s0>
<s5>35</s5>
</fC03><fC03 i1="13" i2="X" l="ENG"><s0>Three dimensional model</s0>
<s5>35</s5>
</fC03><fC03 i1="13" i2="X" l="SPA"><s0>Modelo 3 dimensiones</s0>
<s5>35</s5>
</fC03><fC03 i1="14" i2="X" l="FRE"><s0>Méthode polynomiale</s0>
<s5>36</s5>
</fC03><fC03 i1="14" i2="X" l="ENG"><s0>Polynomial method</s0>
<s5>36</s5>
</fC03><fC03 i1="14" i2="X" l="SPA"><s0>Método polinomial</s0>
<s5>36</s5>
</fC03><fC03 i1="15" i2="X" l="FRE"><s0>Diagramme Voronoï</s0>
<s5>37</s5>
</fC03><fC03 i1="15" i2="X" l="ENG"><s0>Voronoï diagram</s0>
<s5>37</s5>
</fC03><fC03 i1="15" i2="X" l="SPA"><s0>Diagrama Voronoi</s0>
<s5>37</s5>
</fC03><fC03 i1="16" i2="X" l="FRE"><s0>Cubique</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03><fC03 i1="16" i2="X" l="ENG"><s0>Cubics</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03><fC03 i1="16" i2="X" l="SPA"><s0>Cúbico</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03><fN21><s1>180</s1>
</fN21><fN44 i1="01"><s1>OTO</s1>
</fN44><fN82><s1>OTO</s1>
</fN82><pR><fA30 i1="01" i2="1" l="ENG"><s1>Algorithmic number theory. International symposium</s1>
<s2>6</s2>
<s3>Burlington VT USA</s3>
<s4>2004-06-13</s4>
</fA30><server><NO>PASCAL 04-0301103 INIST</NO>
<ET>Low-dimensional lattice basis reduction revisited</ET>
<AU>NGUYEN (Phong Q.); STEHLE (Damien); BUELL (Duncan)</AU>
<AF>CNRS/École normale supérieure, Département d'informatique, 45 rue d'Ulm/75230 Paris/France (1 aut.); LORIA/INRIA Lorraine, 615 rue du J. botanique/54602 Villers-lès-Nancy/France (2 aut.)</AF>
<DT>Publication en série; Congrès; Niveau analytique</DT>
<SO>Lecture notes in computer science; ISSN 0302-9743; Allemagne; Da. 2004; Vol. 3076; Pp. 338-357; Bibl. 30 ref.</SO>
<LA>Anglais</LA>
<EA>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 is arguably the most natural lattice basis reduction algorithm, because it is a straightforward generalization of the well-known two-dimensional Gaussian 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 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: this allows to compute various lattice problems (e.g. computing a Minkowski-reduced basis and a closest vector) in quadratic time, without fast integer arithmetic, up to dimension four, while all other algorithms known for such problems have a bit-complexity which is at least cubic. 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. Our analysis, based on geometric properties of low-dimensional lattices and in particular Voronoï cells, arguably simplifies Semaev's analysis in dimensions two and three, unifies the cases of dimensions two, three and four, but breaks down in dimension five.</EA>
<CC>001A02C02; 001D04A04E; 001D02B07C</CC>
<FD>Treillis; Géométrie algorithmique; Problème NP difficile; Algorithme glouton; Théorie euclidienne; Modèle 2 dimensions; Processus Gauss; Algorithme optimal; Complexité algorithme; Algorithme rapide; Arithmétique; Métrique Minkowski; Modèle 3 dimensions; Méthode polynomiale; Diagramme Voronoï; Cubique</FD>
<ED>Lattice; Computational geometry; NP hard problem; Greedy algorithm; Euclidean theory; Two dimensional model; Gaussian process; Optimal algorithm; Algorithm complexity; Fast algorithm; Arithmetics; Minkowski metric; Three dimensional model; Polynomial method; Voronoï diagram; Cubics</ED>
<SD>Enrejado; Geometría computacional; Problema NP duro; Algoritmo glotón; Teoría euclidiana; Modelo 2 dimensiones; Proceso Gauss; Algoritmo óptimo; Complejidad algoritmo; Algoritmo rápido; Aritmética; Métrico Minkowski; Modelo 3 dimensiones; Método polinomial; Diagrama Voronoi; Cúbico</SD>
<LO>INIST-16343.354000117887920260</LO>
<ID>04-0301103</ID>
</server>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/PascalFrancis/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000668 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Corpus/biblio.hfd -nk 000668 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= PascalFrancis
|étape= Corpus
|type= RBID
|clé= Pascal:04-0301103
|texte= Low-dimensional lattice basis reduction revisited
}}
| This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022 |  |
