文章基本信息

标题：On the decomposition of lattices
本地全文：下载
作者：Boris Hemkemeier ; Frank Vallentin
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1998
卷号：1998
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：A lattice in euclidean space which is an orthogonal sum of nontrivial sublattices is called decomposable. We present an algorithm to construct a lattice's decomposition into indecomposable sublattices. Similar methods are used to prove a covering theorem for generating systems of lattices and to speed up variations of the LLL algorithm for the computation of lattice bases from large generating systems. We prove an upper bound for this which is asymptotically better than the known bound for a standard algorithm (variation of the LLL algorithm due to Buchmann, Pohst). Experimental results show that our algorithm is faster than Pohst's MLLL algorithm in particular if the number of generators is large.
关键词：Large generating systems, lattices, LLL algorithm, Successive Minima