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.

Authors

• Miklós Ajtai
• Ravi Kumar 0001
• D. Sivakumar 0001

Keywords

No keywords are indexed for this paper.