Algorithms to Construct Minkowski Reduced an Hermite Reduced Lattice Bases
Algorithms to Construct Minkowski Reduced an Hermite Reduced Lattice Bases
复制标题
DOI：
10.1016/0304-3975(85)90067-2
复制
发表时间：
1985-12
期刊：
影响因子：
--
通讯作者：
Bettina Helfrich
中科院分区：
文献类型：
--
作者：
Bettina Helfrich
到目前为止，构造闵可夫斯基简化晶格基的问题只解决了二维和三维的情况。本文提出了一种求解任意维数问题的算法。对于固定维度，运行时间为多项式。该算法借鉴了Lenstra、Lenstra和Lovász（1982）以及Kannan（1983）之前的约简算法。此外，我们将改进Kannan算法来构造Hermite约简格基。
Up to now, the problem of constructing Minkowski reduced lattice bases has been solved only for the two- and three-dimensional case. This paper presents an algorithm to solve the problem for arbitrary dimension. For fixed dimension, the runtime is polynomial. The algorithm hinges on the previous reduction algorithms of Lenstra, Lenstra and Lovász (1982) and Kannan (1983). Moreover, we shall improve Kannan's algorithm to construct Hermite reduced lattice bases.