资源描述:
《A generalization of the LLL-algorithm over euclidean rings.pdf》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、JOURNALDETHÉORIEDESNOMBRESDEBORDEAUXHUGUETTENAPIASAgeneralizationoftheLLL-algorithmovereuclideanringsorordersJournaldeThéoriedesNombresdeBordeaux,tome8,no2(1996),p.387-396.©UniversitéBordeaux1,1996,tousdroitsréser
2、vés.L’accèsauxarchivesdelarevue«JournaldeThéoriedesNombresdeBordeaux»(http://jtnb.cedram.org/)impliquel’accordaveclescondi-tionsgénéralesd’utilisation(http://www.numdam.org/legal.php).Touteuti-lisationcommercialeouimpressionsystématiqueestconstitutived’uneinfractio
3、npénale.Toutecopieouimpressiondecefichierdoitconte-nirlaprésentementiondecopyright.ArticlenumérisédanslecadreduprogrammeNumérisationdedocumentsanciensmathématiqueshttp://www.numdam.org/387-3AgeneralizationoftheLLL-algorithmovereuclideanringsorordersparHUGUETTENAPIAS
4、RÉSUMÉ.Denombreuxréseauxcélèbres(D4,E8,leréseauK12deCoxeter-Todd,leréseaudeBarnes-Wall,leréseau039B24deLeech,lesréseaux2-modulairesdedimension32deQuebbemannetdeBachoc,...)sontmunisdestructuresalgébriquessurdiversanneauxeuclidiens,entiersd’EisensteinouquaternionsdeH
5、urwitz,parexemple.Lesprocédésusuelsderéduction,etenparticulierl’algorithmeLLL,deviennentplusperformantslorsqu’onlesadapteàcesstructures,ABSTRACT.Numerousimportantlattices(D4,E8,theCoxeter-Toddlat-ticeK12,theBarnes-Walllattice039B16,theLeechlattice039B24,aswellasthe
6、2-modular32-dimensionallatticesfoundbyQuebbemannandBachoc)possessalgebraicstructuresovervariousEuclideanrings,e.g.EisensteinintegersorHurwitzquaternions.Oneobtainsefficientalgorithmsbyper-formingwithinthisframetheusualreductionprocedures,includingthewellknownLLL-al
7、gorithm.1.Introduction.TheLLL-algorithmforbasisreduction,oneofthemostimportantandusefulalgorithminthegeometryofnumbers,duetoLenstra,Lenstra,Lovdsz[9]canbegeneralizedtoEuclideanringsororders.Manylatticesbuiltwithcodesoverringsorordershaveanalgebraicandadditivestruc-
8、ture.WepresenthereanewversionoftheLLL-algorithmwhichreducesabasis(orasystemofgeneratorvectors)whilepreservingthealgebraicstructureofthelattice.We