a sieve algorithm for the shortest lattice vector problem
We present a randomized 2^{ O(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 2^{ O(n \log 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.
algorithm lattice vectorization randomization timing computation log polynomial approximation factor