Improved methods for calculating vectors of short length in a lattice, including a complexity analysis

Abstract:

The standard methods for calculating vectors of short length in a lattice use a reduction procedure followed by enumerating all vectors of ${{\mathbf {Z}}^m}$ in a suitable box. However, it suffices to consider those ${\mathbf {x}} \in {{\mathbf {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.