We give a random class of n dimensional lattices so that, ifthere is a probabilistic polynomial time algorithm which finds a shortvector in a random lattice with a probability of at least 1/2then there is also a probabilistic polynomial time algorithm whichsolves the following three lattice problems in every n dimensionallattice with a probability exponentially close to one. (1) Find thelength of a shortest nonzero vector in an n-dimensional lattice,approximately, up to a polynomial factor. (2) Find the shortest nonzerovector in an n-dimensional lattice L where the shortest vectoris unique in the sense that any other vector whose length is onlya polynomial times longer, is parallel to it. (3) Find a basis in thelattice L whose length is the smallest possible up to a polynomialfactor, where the length of a basis is the maximum of the lengthsof its elements.
展开▼
