Abstract:We introduce lattices and survey the main provable algorithms
for solving the shortest vector problem (SVP), either exactly or approximately.
In doing so, we emphasize a surprising connection between lattice algorithms
and the historical problem of bounding a well-known constant introduced by Hermite in 1850,
which is related to sphere packings. For instance, we present LLL as an (efficient) algorithmic
version of Hermite's inequality on Hermite's constant. Similarly, we present blockwise generalizations
of LLL as (more or less tight) algorithmic versions of Mordell's inequality.
Bibtex:
@inbook{Ng09,
author={P. Q. Nguyen},
booktitle={The LLL Algorithm:
Survey and Applications},
title={Hermite's Constant and Lattice Algorithms},
editor={P. Q. Nguyen and B. Vall\'ee},
series={nformation Security and Cryptography},
publisher={Springer},
year=2009
}