A hierarchy of polynomial time lattice basis reduction algorithms (Q1101500): Difference between revisions

We present a hierarchy of polynomial time lattice basis reduction algorithms that stretch from Lenstra, Lenstra, Lovász reduction to Korkine-Zolotareff reduction. Let \(\lambda\) (L) be the length of a shortest nonzero element of a lattice L. We present an algorithm which for \(k\in {\mathbb{N}}\) finds a nonzero lattice vector b so that \(| b|^ 2\leq (6k^ 2)^{n/k}\lambda (L)^ 2.\) This algorithm uses \(O(n^ 2(\sqrt{k^{k+o(k)}}+n^ 2)\log B\) arithmetic operations on O(n log B)-bit integers. This holds provided that the given basis vectors \(b_ 1,...,b_ n\in {\mathbb{Z}}^ n\) are integral and have the length bound B. This algorithm successively applies Korkine-Zolotareff reduction to blocks of length k of the lattice basis. We also improve Kannan's algorithm for Korkine-Zolotareff reduction.