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 <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="bold upper Z Superscript m"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="bold">Z</mml:mi> </mml:mrow> </mml:mrow> <mml:mi>m</mml:mi> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">{{\mathbf {Z}}^m}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> in a suitable box. However, it suffices to consider those <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="bold x element-of bold upper Z Superscript m"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="bold">x</mml:mi> </mml:mrow> </mml:mrow> <mml:mo>∈</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="bold">Z</mml:mi> </mml:mrow> </mml:mrow> <mml:mi>m</mml:mi> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">{\mathbf {x}} \in {{\mathbf {Z}}^m}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> 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.