AN LLL ALGORITHM WITH QUADRATIC COMPLEXITY
Identifieur interne : 002643 ( PascalFrancis/Checkpoint ); précédent : 002642; suivant : 002644AN LLL ALGORITHM WITH QUADRATIC COMPLEXITY
Auteurs : Phong Q. Nguyen [France] ; Damien Stehle [France, Australie]Source :
- SIAM journal on computing : (Print) [ 0097-5397 ] ; 2010.
Descripteurs français
- Pascal (Inist)
- Wicri :
- topic : Informatique.
English descriptors
- KwdEn :
Abstract
The Lenstra-Lenstra-Lovàsz lattice basis reduction algorithm (called LLL or L3) is a fundamental tool in computational number theory and theoretical computer science, which can be viewed as an efficient algorithmic version of Hermite's inequality on Hermite's constant. Given an integer d-dimensional lattice basis with vectors of Euclidean norm less than B in an n-dimensional space, the L3 algorithm outputs a reduced basis in O(d3n log B . M(d log B)) bit operations, where M(k) denotes the time required to multiply k-bit integers. This worst-case complexity is problematic for applications where d or/and log B are often large. As a result, the original L3 algorithm is almost never used in practice, except in tiny dimension. Instead, one applies floating-point variants where the long-integer arithmetic required by Gram-Schmidt orthogonalization is replaced by floating-point arithmetic. Unfortunately, this is known to be unstable in the worst case: the usual floating-point L3 algorithm is not even guaranteed to terminate, and the output basis may not be L3-reduced at all. In this article, we introduce the L2 algorithm, a new and natural floating-point variant of the L3 algorithm which provably outputs L3-reduced bases in polynomial time O(d2n(d+ log B) log B . M(d)). This is the first L3 algorithm whose running time (without fast integer arithmetic) provably grows only quadratically with respect to log B, like Euclid's gcd algorithm and Lagrange's two-dimensional algorithm.
Affiliations:
- Australie, France
- Auvergne-Rhône-Alpes, Nouvelle-Galles du Sud, Rhône-Alpes, Île-de-France
- Lyon, Paris, Sydney
- Université de Sydney
Links toward previous steps (curation, corpus...)
Links to Exploration step
Pascal:10-0286974Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">AN LLL ALGORITHM WITH QUADRATIC COMPLEXITY</title><author><name sortKey="Nguyen, Phong Q" sort="Nguyen, Phong Q" uniqKey="Nguyen P" first="Phong Q." last="Nguyen">Phong Q. Nguyen</name><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>INRIA & Ecole normale supérieure, DI, 45 rue d'Ulm</s1><s2>75005 Paris</s2><s3>FRA</s3><sZ>1 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region" nuts="2">Île-de-France</region><settlement type="city">Paris</settlement></placeName></affiliation></author><author><name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehle">Damien Stehle</name><affiliation wicri:level="3"><inist:fA14 i1="02"><s1>CNRS & Ecole normale supérieure de Lyon/LIP/INRIA Arenaire/Université de Lyon, 46 allée d'Italie</s1><s2>69364 Lyon</s2><s3>FRA</s3><sZ>2 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region" nuts="2">Auvergne-Rhône-Alpes</region><region type="old region" nuts="2">Rhône-Alpes</region><settlement type="city">Lyon</settlement></placeName></affiliation><affiliation wicri:level="1"><inist:fA14 i1="03"><s1>ACAC/Department of Computing, Macquarie University</s1><s2>Sydney NSW 2109</s2><s3>AUS</s3><sZ>2 aut.</sZ></inist:fA14><country>Australie</country><wicri:noRegion>Sydney NSW 2109</wicri:noRegion></affiliation><affiliation wicri:level="4"><inist:fA14 i1="04"><s1>Department of Mathematics and Statistics, University of Sydney</s1><s2>Sydney NSW 2006</s2><s3>AUS</s3><sZ>2 aut.</sZ></inist:fA14><country>Australie</country><placeName><settlement type="city">Sydney</settlement><region type="état">Nouvelle-Galles du Sud</region></placeName><orgName type="university">Université de Sydney</orgName></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">INIST</idno><idno type="inist">10-0286974</idno><date when="2010">2010</date><idno type="stanalyst">PASCAL 10-0286974 INIST</idno><idno type="RBID">Pascal:10-0286974</idno><idno type="wicri:Area/PascalFrancis/Corpus">002615</idno><idno type="wicri:Area/PascalFrancis/Curation">003971</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">002643</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">002643</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">AN LLL ALGORITHM WITH QUADRATIC COMPLEXITY</title><author><name sortKey="Nguyen, Phong Q" sort="Nguyen, Phong Q" uniqKey="Nguyen P" first="Phong Q." last="Nguyen">Phong Q. Nguyen</name><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>INRIA & Ecole normale supérieure, DI, 45 rue d'Ulm</s1><s2>75005 Paris</s2><s3>FRA</s3><sZ>1 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region" nuts="2">Île-de-France</region><settlement type="city">Paris</settlement></placeName></affiliation></author><author><name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehle">Damien Stehle</name><affiliation wicri:level="3"><inist:fA14 i1="02"><s1>CNRS & Ecole normale supérieure de Lyon/LIP/INRIA Arenaire/Université de Lyon, 46 allée d'Italie</s1><s2>69364 Lyon</s2><s3>FRA</s3><sZ>2 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region" nuts="2">Auvergne-Rhône-Alpes</region><region type="old region" nuts="2">Rhône-Alpes</region><settlement type="city">Lyon</settlement></placeName></affiliation><affiliation wicri:level="1"><inist:fA14 i1="03"><s1>ACAC/Department of Computing, Macquarie University</s1><s2>Sydney NSW 2109</s2><s3>AUS</s3><sZ>2 aut.</sZ></inist:fA14><country>Australie</country><wicri:noRegion>Sydney NSW 2109</wicri:noRegion></affiliation><affiliation wicri:level="4"><inist:fA14 i1="04"><s1>Department of Mathematics and Statistics, University of Sydney</s1><s2>Sydney NSW 2006</s2><s3>AUS</s3><sZ>2 aut.</sZ></inist:fA14><country>Australie</country><placeName><settlement type="city">Sydney</settlement><region type="état">Nouvelle-Galles du Sud</region></placeName><orgName type="university">Université de Sydney</orgName></affiliation></author></analytic><series><title level="j" type="main">SIAM journal on computing : (Print)</title><title level="j" type="abbreviated">SIAM j. comput. : (Print)</title><idno type="ISSN">0097-5397</idno><imprint><date when="2010">2010</date></imprint></series></biblStruct></sourceDesc><seriesStmt><title level="j" type="main">SIAM journal on computing : (Print)</title><title level="j" type="abbreviated">SIAM j. comput. : (Print)</title><idno type="ISSN">0097-5397</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm complexity</term><term>Algorithmics</term><term>Arithmetics</term><term>Computer science</term><term>Floating point</term><term>Integer</term><term>Integer lattice</term><term>Lattice</term><term>OR algorithm</term><term>Polynomial time</term><term>Two-dimensional calculations</term><term>Vector</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Complexité algorithme</term><term>Treillis</term><term>Informatique</term><term>Algorithmique</term><term>Réseau arithmétique</term><term>Vecteur</term><term>Nombre entier</term><term>Virgule flottante</term><term>Arithmétique</term><term>Temps polynomial</term><term>Calcul 2 dimensions</term><term>06Bxx</term><term>Algorithme réduction</term><term>11Yxx</term><term>68XX</term><term>68Wxx</term><term>Pire cas</term><term>65F25</term><term>PGCD</term><term>Algorithme QR</term></keywords><keywords scheme="Wicri" type="topic" xml:lang="fr"><term>Informatique</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">The Lenstra-Lenstra-Lovàsz lattice basis reduction algorithm (called LLL or L<sup>3</sup>) is a fundamental tool in computational number theory and theoretical computer science, which can be viewed as an efficient algorithmic version of Hermite's inequality on Hermite's constant. Given an integer d-dimensional lattice basis with vectors of Euclidean norm less than B in an n-dimensional space, the L<sup>3</sup> algorithm outputs a reduced basis in O(d<sup>3</sup>n log B . M(d log B)) bit operations, where M(k) denotes the time required to multiply k-bit integers. This worst-case complexity is problematic for applications where d or/and log B are often large. As a result, the original L<sup>3</sup> algorithm is almost never used in practice, except in tiny dimension. Instead, one applies floating-point variants where the long-integer arithmetic required by Gram-Schmidt orthogonalization is replaced by floating-point arithmetic. Unfortunately, this is known to be unstable in the worst case: the usual floating-point L<sup>3</sup> algorithm is not even guaranteed to terminate, and the output basis may not be L<sup>3</sup>-reduced at all. In this article, we introduce the L<sup>2</sup> algorithm, a new and natural floating-point variant of the L<sup>3</sup> algorithm which provably outputs L<sup>3</sup>-reduced bases in polynomial time O(d<sup>2</sup>n(d+ log B) log B . M(d)). This is the first L<sup>3</sup> algorithm whose running time (without fast integer arithmetic) provably grows only quadratically with respect to log B, like Euclid's gcd algorithm and Lagrange's two-dimensional algorithm.</div></front></TEI><inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0097-5397</s0></fA01><fA03 i2="1"><s0>SIAM j. comput. : (Print)</s0></fA03><fA05><s2>39</s2></fA05><fA06><s2>3</s2></fA06><fA08 i1="01" i2="1" l="ENG"><s1>AN LLL ALGORITHM WITH QUADRATIC COMPLEXITY</s1></fA08><fA11 i1="01" i2="1"><s1>NGUYEN (Phong Q.)</s1></fA11><fA11 i1="02" i2="1"><s1>STEHLE (Damien)</s1></fA11><fA14 i1="01"><s1>INRIA & Ecole normale supérieure, DI, 45 rue d'Ulm</s1><s2>75005 Paris</s2><s3>FRA</s3><sZ>1 aut.</sZ></fA14><fA14 i1="02"><s1>CNRS & Ecole normale supérieure de Lyon/LIP/INRIA Arenaire/Université de Lyon, 46 allée d'Italie</s1><s2>69364 Lyon</s2><s3>FRA</s3><sZ>2 aut.</sZ></fA14><fA14 i1="03"><s1>ACAC/Department of Computing, Macquarie University</s1><s2>Sydney NSW 2109</s2><s3>AUS</s3><sZ>2 aut.</sZ></fA14><fA14 i1="04"><s1>Department of Mathematics and Statistics, University of Sydney</s1><s2>Sydney NSW 2006</s2><s3>AUS</s3><sZ>2 aut.</sZ></fA14><fA20><s1>874-903</s1></fA20><fA21><s1>2010</s1></fA21><fA23 i1="01"><s0>ENG</s0></fA23><fA43 i1="01"><s1>INIST</s1><s2>16063</s2><s5>354000170429390040</s5></fA43><fA44><s0>0000</s0><s1>© 2010 INIST-CNRS. All rights reserved.</s1></fA44><fA45><s0>51 ref.</s0></fA45><fA47 i1="01" i2="1"><s0>10-0286974</s0></fA47><fA60><s1>P</s1></fA60><fA61><s0>A</s0></fA61><fA64 i1="01" i2="1"><s0>SIAM journal on computing : (Print)</s0></fA64><fA66 i1="01"><s0>USA</s0></fA66><fC01 i1="01" l="ENG"><s0>The Lenstra-Lenstra-Lovàsz lattice basis reduction algorithm (called LLL or L<sup>3</sup>) is a fundamental tool in computational number theory and theoretical computer science, which can be viewed as an efficient algorithmic version of Hermite's inequality on Hermite's constant. Given an integer d-dimensional lattice basis with vectors of Euclidean norm less than B in an n-dimensional space, the L<sup>3</sup> algorithm outputs a reduced basis in O(d<sup>3</sup>n log B . M(d log B)) bit operations, where M(k) denotes the time required to multiply k-bit integers. This worst-case complexity is problematic for applications where d or/and log B are often large. As a result, the original L<sup>3</sup> algorithm is almost never used in practice, except in tiny dimension. Instead, one applies floating-point variants where the long-integer arithmetic required by Gram-Schmidt orthogonalization is replaced by floating-point arithmetic. Unfortunately, this is known to be unstable in the worst case: the usual floating-point L<sup>3</sup> algorithm is not even guaranteed to terminate, and the output basis may not be L<sup>3</sup>-reduced at all. In this article, we introduce the L<sup>2</sup> algorithm, a new and natural floating-point variant of the L<sup>3</sup> algorithm which provably outputs L<sup>3</sup>-reduced bases in polynomial time O(d<sup>2</sup>n(d+ log B) log B . M(d)). This is the first L<sup>3</sup> algorithm whose running time (without fast integer arithmetic) provably grows only quadratically with respect to log B, like Euclid's gcd algorithm and Lagrange's two-dimensional algorithm.</s0></fC01><fC02 i1="01" i2="X"><s0>001D02A08</s0></fC02><fC02 i1="02" i2="X"><s0>001D02A05</s0></fC02><fC02 i1="03" i2="X"><s0>001A02B02</s0></fC02><fC02 i1="04" i2="X"><s0>001A02C02</s0></fC02><fC03 i1="01" i2="X" l="FRE"><s0>Complexité algorithme</s0><s5>17</s5></fC03><fC03 i1="01" i2="X" l="ENG"><s0>Algorithm complexity</s0><s5>17</s5></fC03><fC03 i1="01" i2="X" l="SPA"><s0>Complejidad algoritmo</s0><s5>17</s5></fC03><fC03 i1="02" i2="X" l="FRE"><s0>Treillis</s0><s5>18</s5></fC03><fC03 i1="02" i2="X" l="ENG"><s0>Lattice</s0><s5>18</s5></fC03><fC03 i1="02" i2="X" l="SPA"><s0>Enrejado</s0><s5>18</s5></fC03><fC03 i1="03" i2="X" l="FRE"><s0>Informatique</s0><s5>19</s5></fC03><fC03 i1="03" i2="X" l="ENG"><s0>Computer science</s0><s5>19</s5></fC03><fC03 i1="03" i2="X" l="SPA"><s0>Informática</s0><s5>19</s5></fC03><fC03 i1="04" i2="X" l="FRE"><s0>Algorithmique</s0><s5>20</s5></fC03><fC03 i1="04" i2="X" l="ENG"><s0>Algorithmics</s0><s5>20</s5></fC03><fC03 i1="04" i2="X" l="SPA"><s0>Algorítmica</s0><s5>20</s5></fC03><fC03 i1="05" i2="X" l="FRE"><s0>Réseau arithmétique</s0><s5>21</s5></fC03><fC03 i1="05" i2="X" l="ENG"><s0>Integer lattice</s0><s5>21</s5></fC03><fC03 i1="05" i2="X" l="SPA"><s0>Red aritmética</s0><s5>21</s5></fC03><fC03 i1="06" i2="X" l="FRE"><s0>Vecteur</s0><s5>22</s5></fC03><fC03 i1="06" i2="X" l="ENG"><s0>Vector</s0><s5>22</s5></fC03><fC03 i1="06" i2="X" l="SPA"><s0>Vector</s0><s5>22</s5></fC03><fC03 i1="07" i2="X" l="FRE"><s0>Nombre entier</s0><s5>23</s5></fC03><fC03 i1="07" i2="X" l="ENG"><s0>Integer</s0><s5>23</s5></fC03><fC03 i1="07" i2="X" l="SPA"><s0>Entero</s0><s5>23</s5></fC03><fC03 i1="08" i2="X" l="FRE"><s0>Virgule flottante</s0><s5>24</s5></fC03><fC03 i1="08" i2="X" l="ENG"><s0>Floating point</s0><s5>24</s5></fC03><fC03 i1="08" i2="X" l="SPA"><s0>Coma flotante</s0><s5>24</s5></fC03><fC03 i1="09" i2="X" l="FRE"><s0>Arithmétique</s0><s5>25</s5></fC03><fC03 i1="09" i2="X" l="ENG"><s0>Arithmetics</s0><s5>25</s5></fC03><fC03 i1="09" i2="X" l="SPA"><s0>Aritmética</s0><s5>25</s5></fC03><fC03 i1="10" i2="X" l="FRE"><s0>Temps polynomial</s0><s5>26</s5></fC03><fC03 i1="10" i2="X" l="ENG"><s0>Polynomial time</s0><s5>26</s5></fC03><fC03 i1="10" i2="X" l="SPA"><s0>Tiempo polinomial</s0><s5>26</s5></fC03><fC03 i1="11" i2="3" l="FRE"><s0>Calcul 2 dimensions</s0><s5>27</s5></fC03><fC03 i1="11" i2="3" l="ENG"><s0>Two-dimensional calculations</s0><s5>27</s5></fC03><fC03 i1="12" i2="X" l="FRE"><s0>06Bxx</s0><s4>INC</s4><s5>70</s5></fC03><fC03 i1="13" i2="X" l="FRE"><s0>Algorithme réduction</s0><s4>INC</s4><s5>71</s5></fC03><fC03 i1="14" i2="X" l="FRE"><s0>11Yxx</s0><s4>INC</s4><s5>72</s5></fC03><fC03 i1="15" i2="X" l="FRE"><s0>68XX</s0><s4>INC</s4><s5>73</s5></fC03><fC03 i1="16" i2="X" l="FRE"><s0>68Wxx</s0><s4>INC</s4><s5>74</s5></fC03><fC03 i1="17" i2="X" l="FRE"><s0>Pire cas</s0><s4>INC</s4><s5>75</s5></fC03><fC03 i1="18" i2="X" l="FRE"><s0>65F25</s0><s4>INC</s4><s5>76</s5></fC03><fC03 i1="19" i2="X" l="FRE"><s0>PGCD</s0><s4>INC</s4><s5>77</s5></fC03><fC03 i1="20" i2="X" l="FRE"><s0>Algorithme QR</s0><s4>CD</s4><s5>96</s5></fC03><fC03 i1="20" i2="X" l="ENG"><s0>OR algorithm</s0><s4>CD</s4><s5>96</s5></fC03><fN21><s1>186</s1></fN21><fN44 i1="01"><s1>OTO</s1></fN44><fN82><s1>OTO</s1></fN82></pA></standard></inist><affiliations><list><country><li>Australie</li><li>France</li></country><region><li>Auvergne-Rhône-Alpes</li><li>Nouvelle-Galles du Sud</li><li>Rhône-Alpes</li><li>Île-de-France</li></region><settlement><li>Lyon</li><li>Paris</li><li>Sydney</li></settlement><orgName><li>Université de Sydney</li></orgName></list><tree><country name="France"><region name="Île-de-France"><name sortKey="Nguyen, Phong Q" sort="Nguyen, Phong Q" uniqKey="Nguyen P" first="Phong Q." last="Nguyen">Phong Q. Nguyen</name></region><name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehle">Damien Stehle</name></country><country name="Australie"><noRegion><name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehle">Damien Stehle</name></noRegion><name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehle">Damien Stehle</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Asie/explor/AustralieFrV1/Data/PascalFrancis/Checkpoint
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002643 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Checkpoint/biblio.hfd -nk 002643 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Asie
|area= AustralieFrV1
|flux= PascalFrancis
|étape= Checkpoint
|type= RBID
|clé= Pascal:10-0286974
|texte= AN LLL ALGORITHM WITH QUADRATIC COMPLEXITY
}}
| This area was generated with Dilib version V0.6.33. |  |