Sampling methods for shortest vectors, closest vectors and successive minima
We study four problems from the geometry of numbers, the shortest vector problem (SVP), the closest vector problem (CVP), the successive minima problem (SMP), and the shortest independent vectors problem (SIVP). Extending and generalizing results of Ajtai, Kumar, and Sivakumar we present probabilistic single exponential time algorithms for all four problems for all l(p) norms. The results on SMP and SIVP are new for all norms. The results on SVP and CVP generalize previous results of Ajtai et al. for the Euclidean l(2) norm to arbitrary l(p) norms. We achieve our results by introducing a new lattice problem, the generalized shortest vector problem (GSVP).(1) We describe a single exponential time algorithm for GSVP. We also describe polynomial time reductions from SVP, CVP. SMP. and SIVP to GSVP, establishing single exponential time algorithms for the four classical lattice problems. This approach leads to a unified algorithmic treatment of the lattice problems SVP, CVP, SMP. and SIVP. (c) 2009 Elsevier B.V. All rights reserved.
shortest vectors geometry of numbers lattices