Finding short lattice vectors within Mordell’s inequality. (English) Zbl 1230.11153

Gama, Nicolas; Nguyen, Phong Q.

STOC’08. Proceedings of the 40th annual ACM symposium on theory of computing 2008, Victoria, Canada, May 17–20, 2008. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-047-0). 207-216 (2008).

MSC:

11Y16	Number-theoretic algorithms; complexity
11H06	Lattices and convex bodies (number-theoretic aspects)
68W30	Symbolic computation and algebraic computation

Keywords:

polynomial time blockwise reduction algorithm; algorithmic version of Mordell’s inequality on Hermite’s constant; approximation factor for shortest vector problem