Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. (English) Zbl 0556.10022

Fincke, U.; Pohst, M.

Math. Comput. 44, 463-471 (1985).

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.

MSC:

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

Keywords:

lattices of higher dimensions; algorithm; reduction theory; Cholesky’s method; complexity analysis; vectors of short length; ellipsoid; numerical examples