the worst-case behavior of schnorr's algorithm approximating the shortest nonzero vector in a lattice
Schnorr's algorithm for finding an approximation for the shortest nonzero vector in an n dimensional lattice depends on a parameter k. He proved that for a fixed k ? n his algorithm (block 2k-reduction) provides a lattice vector whose length is greater than the length of a shortest nonzero vector in the lattice by at most a factor of (4k 2 ) n/k . (The time required by the algorithm depends on k.) We show that if k=o(n), this bound on the performance of Schnorr's algorithm cannot be improved (apart from a constant factor in the exponent), namely there is a lattice and a basis so that if they are given as an input to the algorithm then the resulting approximating factor of the output is at least k ? n/k . (For larger integers k if Schnorr's algorithm runs in polynomial time then we have already a polynomial time algorithm for finding the shortest nonzero vector.) We also solve an open problem formulated by Schnorr about the the Korkine-Zolotareff lattice constants ? k . We show that his upper bound ? k ? k 1 + ln k is the best possible apart from a constant factor in the exponent. We prove a similar result about his upper bound ? k ? 4k 2 , where ? k is another lattice constant with an important role in Schnorr's analysis of his algorithm.
algorithm lattice basis