A sieve algorithm for the shortest lattice vector problem

We present a randomized 2O(n) time algorithm to compute a shortest non-zero vector in an n-dimensional rational lattice. The best known time upper bound for this problem was 2O(nlog n) first given by Kannan [7] in 1983. We obtain several consequences of this algorithm for related problems on lattices and codes, including an improvement for polynomial time approximations to the shortest vector problem. In this improvement we gain a factor of log log n in the exponent of the approximating factor.