LLL on the average
Identifieur interne : 004332 ( Hal/Checkpoint ); précédent : 004331; suivant : 004333LLL on the average
Auteurs : Phong Nguyen [France] ; Damien Stehle [France]Source :
Abstract
Despite their popularity, lattice reduction algorithms remain mysterious in many ways. It has been widely reported that they behave much more nicely than what was expected from the worst-case proved bounds, both in terms of the running time and the output quality. In this article, we investigate this puzzling statement by trying to model the average case of lattice reduction algorithms, starting with the celebrated Lenstra-Lenstra-Lovász algorithm (L3). We discuss what is meant by lattice reduction on the average, and we present extensive experiments on the average case behavior of L3, in order to give a clearer picture of the differences/similarities between the average and worst cases. Our work is intended to clarify the practical behavior of L3 and to raise theoretical questions on its average behavior.
Url:
DOI: 10.1007/11792086_18
Links toward previous steps (curation, corpus...)
Links to Exploration step
Hal:hal-00107309Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">LLL on the average</title><author><name sortKey="Nguyen, Phong" sort="Nguyen, Phong" uniqKey="Nguyen P" first="Phong" last="Nguyen">Phong Nguyen</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-1315" status="VALID"><orgName>Laboratoire d'informatique de l'école normale supérieure</orgName><orgName type="acronym">LIENS</orgName><desc><address><addrLine>45 Rue d'Ulm 75230 PARIS CEDEX 05</addrLine><country key="FR"></country></address><ref type="url">http://www.di.ens.fr</ref></desc><listRelation><relation active="#struct-59704" type="direct"></relation><relation name="UMR8548" active="#struct-441569" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-59704" type="direct"><org type="institution" xml:id="struct-59704" status="VALID"><orgName>École normale supérieure - Paris</orgName><orgName type="acronym">ENS Paris</orgName><desc><address><addrLine>45, Rue d'Ulm - 75230 Paris cedex 05</addrLine><country key="FR"></country></address><ref type="url">http://www.ens.fr</ref></desc></org></tutelle><tutelle name="UMR8548" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country></affiliation></author><author><name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehle">Damien Stehle</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2364" status="OLD"><idno type="RNSR">200221401H</idno><orgName>Solving problems through algebraic computation and efficient software</orgName><orgName type="acronym">SPACES</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/spaces</ref></desc><listRelation><relation active="#struct-160" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-300291" type="indirect"></relation><relation active="#struct-300292" type="indirect"></relation><relation active="#struct-300293" type="indirect"></relation><relation active="#struct-2496" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-300291" type="direct"></relation><relation active="#struct-300292" type="direct"></relation><relation active="#struct-300293" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName><orgName type="acronym">UHP</orgName><date type="end">2011-12-31</date><desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName><date type="end">2011-12-31</date><desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName><orgName type="acronym">INPL</orgName><date type="end">2011-12-31</date><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université Nancy 2</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:hal-00107309</idno><idno type="halId">hal-00107309</idno><idno type="halUri">https://hal.archives-ouvertes.fr/hal-00107309</idno><idno type="url">https://hal.archives-ouvertes.fr/hal-00107309</idno><idno type="doi">10.1007/11792086_18</idno><date when="2006">2006</date><idno type="wicri:Area/Hal/Corpus">002E00</idno><idno type="wicri:Area/Hal/Curation">002E00</idno><idno type="wicri:Area/Hal/Checkpoint">004332</idno><idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">004332</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">LLL on the average</title><author><name sortKey="Nguyen, Phong" sort="Nguyen, Phong" uniqKey="Nguyen P" first="Phong" last="Nguyen">Phong Nguyen</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-1315" status="VALID"><orgName>Laboratoire d'informatique de l'école normale supérieure</orgName><orgName type="acronym">LIENS</orgName><desc><address><addrLine>45 Rue d'Ulm 75230 PARIS CEDEX 05</addrLine><country key="FR"></country></address><ref type="url">http://www.di.ens.fr</ref></desc><listRelation><relation active="#struct-59704" type="direct"></relation><relation name="UMR8548" active="#struct-441569" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-59704" type="direct"><org type="institution" xml:id="struct-59704" status="VALID"><orgName>École normale supérieure - Paris</orgName><orgName type="acronym">ENS Paris</orgName><desc><address><addrLine>45, Rue d'Ulm - 75230 Paris cedex 05</addrLine><country key="FR"></country></address><ref type="url">http://www.ens.fr</ref></desc></org></tutelle><tutelle name="UMR8548" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country></affiliation></author><author><name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehle">Damien Stehle</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2364" status="OLD"><idno type="RNSR">200221401H</idno><orgName>Solving problems through algebraic computation and efficient software</orgName><orgName type="acronym">SPACES</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/spaces</ref></desc><listRelation><relation active="#struct-160" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-300291" type="indirect"></relation><relation active="#struct-300292" type="indirect"></relation><relation active="#struct-300293" type="indirect"></relation><relation active="#struct-2496" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-300291" type="direct"></relation><relation active="#struct-300292" type="direct"></relation><relation active="#struct-300293" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName><orgName type="acronym">UHP</orgName><date type="end">2011-12-31</date><desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName><date type="end">2011-12-31</date><desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName><orgName type="acronym">INPL</orgName><date type="end">2011-12-31</date><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université Nancy 2</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author></analytic><idno type="DOI">10.1007/11792086_18</idno></biblStruct></sourceDesc></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Despite their popularity, lattice reduction algorithms remain mysterious in many ways. It has been widely reported that they behave much more nicely than what was expected from the worst-case proved bounds, both in terms of the running time and the output quality. In this article, we investigate this puzzling statement by trying to model the average case of lattice reduction algorithms, starting with the celebrated Lenstra-Lenstra-Lovász algorithm (L3). We discuss what is meant by lattice reduction on the average, and we present extensive experiments on the average case behavior of L3, in order to give a clearer picture of the differences/similarities between the average and worst cases. Our work is intended to clarify the practical behavior of L3 and to raise theoretical questions on its average behavior.</div></front></TEI><hal api="V3"><titleStmt><title xml:lang="en">LLL on the average</title><author role="aut"><persName><forename type="first">Phong</forename><surname>Nguyen</surname></persName><email></email><idno type="halauthor">138536</idno><affiliation ref="#struct-1315"></affiliation></author><author role="aut"><persName><forename type="first">Damien</forename><surname>Stehle</surname></persName><email>stehle@loria.fr</email><idno type="halauthor">138537</idno><affiliation ref="#struct-2364"></affiliation></author><editor role="depositor"><persName><forename>Damien</forename><surname>Stehle</surname></persName><email>stehle@loria.fr</email></editor></titleStmt><editionStmt><edition n="v1" type="current"><date type="whenSubmitted">2006-10-18 09:19:53</date><date type="whenModified">2016-05-19 01:09:10</date><date type="whenReleased">2006-10-18 09:19:53</date><date type="whenProduced">2006</date></edition><respStmt><resp>contributor</resp><name key="103321"><persName><forename>Damien</forename><surname>Stehle</surname></persName><email>stehle@loria.fr</email></name></respStmt></editionStmt><publicationStmt><distributor>CCSD</distributor><idno type="halId">hal-00107309</idno><idno type="halUri">https://hal.archives-ouvertes.fr/hal-00107309</idno><idno type="halBibtex">nguyen:hal-00107309</idno><idno type="halRefHtml">Proceedings of the 7th International Symposium on Algorithmic Number Theory, ANTS-VII., 2006, Berlin, Germany. Springer Verlag, pp.238-256, 2006, Lecture Notes in Computer Science Vol. 4076. <10.1007/11792086_18></idno><idno type="halRef">Proceedings of the 7th International Symposium on Algorithmic Number Theory, ANTS-VII., 2006, Berlin, Germany. Springer Verlag, pp.238-256, 2006, Lecture Notes in Computer Science Vol. 4076. <10.1007/11792086_18></idno></publicationStmt><seriesStmt><idno type="stamp" n="INRIA">INRIA - Institut National de Recherche en Informatique et en Automatique</idno><idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno><idno type="stamp" n="ENS-PARIS">Ecole Normale Supérieure de Paris</idno><idno type="stamp" n="INPL">Institut National Polytechnique de Lorraine</idno><idno type="stamp" n="INSMI">CNRS-INSMI - INstitut des Sciences Mathématiques et de leurs Interactions</idno><idno type="stamp" n="LORIA2">Publications du LORIA</idno><idno type="stamp" n="LORIA">LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications</idno><idno type="stamp" n="INRIA-NANCY-GRAND-EST">INRIA Nancy - Grand Est</idno><idno type="stamp" n="UNIV-LORRAINE">Université de Lorraine</idno><idno type="stamp" n="INRIA-LORRAINE">INRIA Nancy - Grand Est</idno><idno type="stamp" n="LABO-LORIA-SET" p="LORIA">LABO-LORIA-SET</idno></seriesStmt><notesStmt><note type="audience" n="0">Not set</note><note type="invited" n="0">No</note><note type="popular" n="0">No</note><note type="peer" n="1">Yes</note><note type="proceedings" n="0">No</note></notesStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">LLL on the average</title><author role="aut"><persName><forename type="first">Phong</forename><surname>Nguyen</surname></persName><idno type="halAuthorId">138536</idno><affiliation ref="#struct-1315"></affiliation></author><author role="aut"><persName><forename type="first">Damien</forename><surname>Stehle</surname></persName><email>stehle@loria.fr</email><idno type="halAuthorId">138537</idno><affiliation ref="#struct-2364"></affiliation></author></analytic><monogr><meeting><title>Proceedings of the 7th International Symposium on Algorithmic Number Theory, ANTS-VII.</title><date type="start">2006</date><settlement>Berlin</settlement><country key="DE">Germany</country></meeting><imprint><publisher>Springer Verlag</publisher><biblScope unit="serie">Lecture Notes in Computer Science Vol. 4076</biblScope><biblScope unit="pp">238-256</biblScope><date type="datePub">2006</date></imprint></monogr><idno type="doi">10.1007/11792086_18</idno></biblStruct></sourceDesc><profileDesc><langUsage><language ident="en">English</language></langUsage><textClass><classCode scheme="halDomain" n="info.info-sc">Computer Science [cs]/Symbolic Computation [cs.SC]</classCode><classCode scheme="halDomain" n="math.math-nt">Mathematics [math]/Number Theory [math.NT]</classCode><classCode scheme="halTypology" n="COMM">Conference papers</classCode></textClass><abstract xml:lang="en">Despite their popularity, lattice reduction algorithms remain mysterious in many ways. It has been widely reported that they behave much more nicely than what was expected from the worst-case proved bounds, both in terms of the running time and the output quality. In this article, we investigate this puzzling statement by trying to model the average case of lattice reduction algorithms, starting with the celebrated Lenstra-Lenstra-Lovász algorithm (L3). We discuss what is meant by lattice reduction on the average, and we present extensive experiments on the average case behavior of L3, in order to give a clearer picture of the differences/similarities between the average and worst cases. Our work is intended to clarify the practical behavior of L3 and to raise theoretical questions on its average behavior.</abstract></profileDesc></hal></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Hal/Checkpoint
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 004332 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Hal/Checkpoint/biblio.hfd -nk 004332 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Hal
|étape= Checkpoint
|type= RBID
|clé= Hal:hal-00107309
|texte= LLL on the average
}}
| This area was generated with Dilib version V0.6.33. |  |