Finding the closest lattice vector when it's unusually close
| Author(s) : | Philip Klein, |
| Publisher : | N/A |
| Publication Date : | 2000 |
| ISSN : | N/A |
| Abstract : | We show how randomized rounding can be applied to nding the closest lattice vector. Given the basis of a lattice, and given a vector x not in the lattice, the heuristic will with high probability nd the vector in the lattice that is closest to x (according to Euclidean norm). The catch is that the time required by the heuristic depends on (1) the distance between x and the closest lattice vector and on (2) the quality of the basis supplied., |