Generating hard instances of lattice problems. (Extended abstract). (English) Zbl 0921.11071

Ajtai, M.

Proceedings of the 28th annual ACM symposium on the theory of computing (STOC). Philadelphia, PA, USA, May 22–24, 1996. New York, NY: ACM, 99-108 (1996).

MSC:

11Y16	Number-theoretic algorithms; complexity
68Q25	Analysis of algorithms and problem complexity
11H55	Quadratic forms (reduction theory, extreme forms, etc.)

Keywords:

shortest vector; lattices; probabilistic polynomial time algorithm; basis; randomized subset sum problem