zbMATH — the first resource for mathematics

Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. (English) Zbl 0556.10022
The standard methods for calculating vectors of short length in a lattice use a reduction procedure followed by enumerating all vectors of \({\mathbb{Z}}^ m\) in a suitable box. However, it suffices to consider those \({\mathfrak x}\in {\mathbb{Z}}^ m\) which lie in a suitable ellipsoid having a much smaller volume than the box. We show in this paper that searching through that ellipsoid is in many cases much more efficient. If combined with an appropriate reduction procedure our method allows to do computations in lattices of much higher dimensions. Several randomly constructed numerical examples illustrate the superiority of our new method over the known ones.

11H50 Minima of forms
11H55 Quadratic forms (reduction theory, extreme forms, etc.)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI