Algorithms to construct Minkowski reduced and Hermite reduced lattice bases (Q1081304)

In 1983, Kannan presented an algorithm to construct a Hermite reduced basis of a lattice \(L=\sum^{n}_{i=1}b_ i {\mathbb{Z}}\) in \({\mathbb{R}}^ d\) \((b_ i\) linear independent vectors of \({\mathbb{R}}^ d)\). In this paper, which is an outgrow of the author's Ph. D. thesis under the guidance of C. P. Schnorr, an idea of C. P. Schnorr is used to reduce the complexity from \((4n)^{1.5n+O(1)}\) to \(n^{0.5n+O(n)}\). Using the fact that a basis \((b_ 1,...,b_{i-1})\) is Hermite reduced if \((b_ 1,...,b_ n)\) is, the author also improves Kannan's recursion algorithm to solve the closest lattice point problem.