AustralieFrV1, PascalFrancis, Corpus, bibRecord, 002615

AN LLL ALGORITHM WITH QUADRATIC COMPLEXITY

Identifieur interne : 002615 ( PascalFrancis/Corpus ); précédent : 002614; suivant : 002616

AN LLL ALGORITHM WITH QUADRATIC COMPLEXITY

Auteurs : Phong Q. Nguyen ; Damien Stehle

Source :

SIAM journal on computing : (Print) [ 0097-5397 ] ; 2010.

RBID : Pascal:10-0286974

Descripteurs français

Pascal (Inist)
- Complexité algorithme, Treillis, Informatique, Algorithmique, Réseau arithmétique, Vecteur, Nombre entier, Virgule flottante, Arithmétique, Temps polynomial, Calcul 2 dimensions, 06Bxx, Algorithme réduction, 11Yxx, 68XX, 68Wxx, Pire cas, 65F25, PGCD, Algorithme QR.

English descriptors

KwdEn :
- Algorithm complexity, Algorithmics, Arithmetics, Computer science, Floating point, Integer, Integer lattice, Lattice, OR algorithm, Polynomial time, Two-dimensional calculations, Vector.

Abstract

The Lenstra-Lenstra-Lovàsz lattice basis reduction algorithm (called LLL or L³) 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³ algorithm outputs a reduced basis in O(d³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³ 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³ algorithm is not even guaranteed to terminate, and the output basis may not be L³-reduced at all. In this article, we introduce the L² algorithm, a new and natural floating-point variant of the L³ algorithm which provably outputs L³-reduced bases in polynomial time O(d²n(d+ log B) log B . M(d)). This is the first L³ 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.

Notice en format standard (ISO 2709)

Pour connaître la documentation sur le format Inist Standard.

A01	`01`	`1`		`@0 0097-5397`
A03		`1`		`@0 SIAM j. comput. : (Print)`
A05				`@2 39`
A06				`@2 3`
A08	`01`	`1`	`ENG`	`@1 AN LLL ALGORITHM WITH QUADRATIC COMPLEXITY`
A11	`01`	`1`		`@1 NGUYEN (Phong Q.)`
A11	`02`	`1`		`@1 STEHLE (Damien)`
A14	`01`			`@1 INRIA & Ecole normale supérieure, DI, 45 rue d'Ulm @2 75005 Paris @3 FRA @Z 1 aut.`
A14	`02`			`@1 CNRS & Ecole normale supérieure de Lyon/LIP/INRIA Arenaire/Université de Lyon, 46 allée d'Italie @2 69364 Lyon @3 FRA @Z 2 aut.`
A14	`03`			`@1 ACAC/Department of Computing, Macquarie University @2 Sydney NSW 2109 @3 AUS @Z 2 aut.`
A14	`04`			`@1 Department of Mathematics and Statistics, University of Sydney @2 Sydney NSW 2006 @3 AUS @Z 2 aut.`
A20				`@1 874-903`
A21				`@1 2010`
A23	`01`			`@0 ENG`
A43	`01`			`@1 INIST @2 16063 @5 354000170429390040`
A44				`@0 0000 @1 © 2010 INIST-CNRS. All rights reserved.`
A45				`@0 51 ref.`
A47	`01`	`1`		`@0 10-0286974`
A60				`@1 P`
A61				`@0 A`
A64	`01`	`1`		`@0 SIAM journal on computing : (Print)`
A66	`01`			`@0 USA`
C01	`01`		`ENG`	@0 The Lenstra-Lenstra-Lovàsz lattice basis reduction algorithm (called LLL or L³) 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³ algorithm outputs a reduced basis in O(d³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³ 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³ algorithm is not even guaranteed to terminate, and the output basis may not be L³-reduced at all. In this article, we introduce the L² algorithm, a new and natural floating-point variant of the L³ algorithm which provably outputs L³-reduced bases in polynomial time O(d²n(d+ log B) log B . M(d)). This is the first L³ 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.
C02	`01`	`X`		`@0 001D02A08`
C02	`02`	`X`		`@0 001D02A05`
C02	`03`	`X`		`@0 001A02B02`
C02	`04`	`X`		`@0 001A02C02`
C03	`01`	`X`	`FRE`	`@0 Complexité algorithme @5 17`
C03	`01`	`X`	`ENG`	`@0 Algorithm complexity @5 17`
C03	`01`	`X`	`SPA`	`@0 Complejidad algoritmo @5 17`
C03	`02`	`X`	`FRE`	`@0 Treillis @5 18`
C03	`02`	`X`	`ENG`	`@0 Lattice @5 18`
C03	`02`	`X`	`SPA`	`@0 Enrejado @5 18`
C03	`03`	`X`	`FRE`	`@0 Informatique @5 19`
C03	`03`	`X`	`ENG`	`@0 Computer science @5 19`
C03	`03`	`X`	`SPA`	`@0 Informática @5 19`
C03	`04`	`X`	`FRE`	`@0 Algorithmique @5 20`
C03	`04`	`X`	`ENG`	`@0 Algorithmics @5 20`
C03	`04`	`X`	`SPA`	`@0 Algorítmica @5 20`
C03	`05`	`X`	`FRE`	`@0 Réseau arithmétique @5 21`
C03	`05`	`X`	`ENG`	`@0 Integer lattice @5 21`
C03	`05`	`X`	`SPA`	`@0 Red aritmética @5 21`
C03	`06`	`X`	`FRE`	`@0 Vecteur @5 22`
C03	`06`	`X`	`ENG`	`@0 Vector @5 22`
C03	`06`	`X`	`SPA`	`@0 Vector @5 22`
C03	`07`	`X`	`FRE`	`@0 Nombre entier @5 23`
C03	`07`	`X`	`ENG`	`@0 Integer @5 23`
C03	`07`	`X`	`SPA`	`@0 Entero @5 23`
C03	`08`	`X`	`FRE`	`@0 Virgule flottante @5 24`
C03	`08`	`X`	`ENG`	`@0 Floating point @5 24`
C03	`08`	`X`	`SPA`	`@0 Coma flotante @5 24`
C03	`09`	`X`	`FRE`	`@0 Arithmétique @5 25`
C03	`09`	`X`	`ENG`	`@0 Arithmetics @5 25`
C03	`09`	`X`	`SPA`	`@0 Aritmética @5 25`
C03	`10`	`X`	`FRE`	`@0 Temps polynomial @5 26`
C03	`10`	`X`	`ENG`	`@0 Polynomial time @5 26`
C03	`10`	`X`	`SPA`	`@0 Tiempo polinomial @5 26`
C03	`11`	`3`	`FRE`	`@0 Calcul 2 dimensions @5 27`
C03	`11`	`3`	`ENG`	`@0 Two-dimensional calculations @5 27`
C03	`12`	`X`	`FRE`	`@0 06Bxx @4 INC @5 70`
C03	`13`	`X`	`FRE`	`@0 Algorithme réduction @4 INC @5 71`
C03	`14`	`X`	`FRE`	`@0 11Yxx @4 INC @5 72`
C03	`15`	`X`	`FRE`	`@0 68XX @4 INC @5 73`
C03	`16`	`X`	`FRE`	`@0 68Wxx @4 INC @5 74`
C03	`17`	`X`	`FRE`	`@0 Pire cas @4 INC @5 75`
C03	`18`	`X`	`FRE`	`@0 65F25 @4 INC @5 76`
C03	`19`	`X`	`FRE`	`@0 PGCD @4 INC @5 77`
C03	`20`	`X`	`FRE`	`@0 Algorithme QR @4 CD @5 96`
C03	`20`	`X`	`ENG`	`@0 OR algorithm @4 CD @5 96`
N21				`@1 186`
N44	`01`			`@1 OTO`
N82				`@1 OTO`

Format Inist (serveur)

NO :	PASCAL 10-0286974 INIST
ET :	AN LLL ALGORITHM WITH QUADRATIC COMPLEXITY
AU :	NGUYEN (Phong Q.); STEHLE (Damien)
AF :	INRIA & Ecole normale supérieure, DI, 45 rue d'Ulm/75005 Paris/France (1 aut.); CNRS & Ecole normale supérieure de Lyon/LIP/INRIA Arenaire/Université de Lyon, 46 allée d'Italie/69364 Lyon/France (2 aut.); ACAC/Department of Computing, Macquarie University/Sydney NSW 2109/Australie (2 aut.); Department of Mathematics and Statistics, University of Sydney/Sydney NSW 2006/Australie (2 aut.)
DT :	Publication en série; Niveau analytique
SO :	SIAM journal on computing : (Print); ISSN 0097-5397; Etats-Unis; Da. 2010; Vol. 39; No. 3; Pp. 874-903; Bibl. 51 ref.
LA :	Anglais
EA :	The Lenstra-Lenstra-Lovàsz lattice basis reduction algorithm (called LLL or L³) 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³ algorithm outputs a reduced basis in O(d³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³ 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³ algorithm is not even guaranteed to terminate, and the output basis may not be L³-reduced at all. In this article, we introduce the L² algorithm, a new and natural floating-point variant of the L³ algorithm which provably outputs L³-reduced bases in polynomial time O(d²n(d+ log B) log B . M(d)). This is the first L³ 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.
CC :	001D02A08; 001D02A05; 001A02B02; 001A02C02
FD :	Complexité algorithme; Treillis; Informatique; Algorithmique; Réseau arithmétique; Vecteur; Nombre entier; Virgule flottante; Arithmétique; Temps polynomial; Calcul 2 dimensions; 06Bxx; Algorithme réduction; 11Yxx; 68XX; 68Wxx; Pire cas; 65F25; PGCD; Algorithme QR
ED :	Algorithm complexity; Lattice; Computer science; Algorithmics; Integer lattice; Vector; Integer; Floating point; Arithmetics; Polynomial time; Two-dimensional calculations; OR algorithm
SD :	Complejidad algoritmo; Enrejado; Informática; Algorítmica; Red aritmética; Vector; Entero; Coma flotante; Aritmética; Tiempo polinomial
LO :	INIST-16063.354000170429390040
ID :	10-0286974

Links to Exploration step

Pascal:10-0286974

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><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>
</affiliation>
</author>
<author><name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehle">Damien Stehle</name>
<affiliation><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>
</affiliation>
<affiliation><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>
</affiliation>
<affiliation><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>
</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>
</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><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>
</affiliation>
</author>
<author><name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehle">Damien Stehle</name>
<affiliation><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>
</affiliation>
<affiliation><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>
</affiliation>
<affiliation><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>
</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>
</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>
<server><NO>PASCAL 10-0286974 INIST</NO>
<ET>AN LLL ALGORITHM WITH QUADRATIC COMPLEXITY</ET>
<AU>NGUYEN (Phong Q.); STEHLE (Damien)</AU>
<AF>INRIA & Ecole normale supérieure, DI, 45 rue d'Ulm/75005 Paris/France (1 aut.); CNRS & Ecole normale supérieure de Lyon/LIP/INRIA Arenaire/Université de Lyon, 46 allée d'Italie/69364 Lyon/France (2 aut.); ACAC/Department of Computing, Macquarie University/Sydney NSW 2109/Australie (2 aut.); Department of Mathematics and Statistics, University of Sydney/Sydney NSW 2006/Australie (2 aut.)</AF>
<DT>Publication en série; Niveau analytique</DT>
<SO>SIAM journal on computing : (Print); ISSN 0097-5397; Etats-Unis; Da. 2010; Vol. 39; No. 3; Pp. 874-903; Bibl. 51 ref.</SO>
<LA>Anglais</LA>
<EA>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.</EA>
<CC>001D02A08; 001D02A05; 001A02B02; 001A02C02</CC>
<FD>Complexité algorithme; Treillis; Informatique; Algorithmique; Réseau arithmétique; Vecteur; Nombre entier; Virgule flottante; Arithmétique; Temps polynomial; Calcul 2 dimensions; 06Bxx; Algorithme réduction; 11Yxx; 68XX; 68Wxx; Pire cas; 65F25; PGCD; Algorithme QR</FD>
<ED>Algorithm complexity; Lattice; Computer science; Algorithmics; Integer lattice; Vector; Integer; Floating point; Arithmetics; Polynomial time; Two-dimensional calculations; OR algorithm</ED>
<SD>Complejidad algoritmo; Enrejado; Informática; Algorítmica; Red aritmética; Vector; Entero; Coma flotante; Aritmética; Tiempo polinomial</SD>
<LO>INIST-16063.354000170429390040</LO>
<ID>10-0286974</ID>
</server>
</inist>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Asie/explor/AustralieFrV1/Data/PascalFrancis/Corpus

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002615 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Corpus/biblio.hfd -nk 002615 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Asie
   |area=    AustralieFrV1
   |flux=    PascalFrancis
   |étape=   Corpus
   |type=    RBID
   |clé=     Pascal:10-0286974
   |texte=   AN LLL ALGORITHM WITH QUADRATIC COMPLEXITY
}}

This area was generated with Dilib version V0.6.33.
Data generation: Tue Dec 5 10:43:12 2017. Site generation: Tue Mar 5 14:07:20 2024

	Serveur d'exploration sur les relations entre la France et l'Australie
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur les relations entre la France et l'Australie

AN LLL ALGORITHM WITH QUADRATIC COMPLEXITY

AN LLL ALGORITHM WITH QUADRATIC COMPLEXITY

Source :

Descripteurs français

English descriptors

Abstract

Notice en format standard (ISO 2709)

Format Inist (serveur)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri