AN LLL ALGORITHM WITH QUADRATIC COMPLEXITY
Identifieur interne : 007A69 ( Main/Exploration ); précédent : 007A68; suivant : 007A70AN 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...)
- to stream PascalFrancis, to step Corpus: 002615
- to stream PascalFrancis, to step Curation: 003971
- to stream PascalFrancis, to step Checkpoint: 002643
- to stream Main, to step Merge: 008111
- to stream Main, to step Curation: 007A69
Le 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>
<idno type="wicri:doubleKey">0097-5397:2010:Nguyen P:an:lll:algorithm</idno>
<idno type="wicri:Area/Main/Merge">008111</idno>
<idno type="wicri:Area/Main/Curation">007A69</idno>
<idno type="wicri:Area/Main/Exploration">007A69</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>
<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/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 007A69 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 007A69 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Asie |area= AustralieFrV1 |flux= Main |étape= Exploration |type= RBID |clé= Pascal:10-0286974 |texte= AN LLL ALGORITHM WITH QUADRATIC COMPLEXITY }}
This area was generated with Dilib version V0.6.33. |