Block Reduced Lattice Bases and Successive Minima

Publisher Website
Google Scholar
Abstract
A lattice basis bi,…,bm is called block reduced with block size β if for every β consecutive vectors bi,…,bi+β−1, the orthogonal projections of bi,…,bi+β−1 in span(bi,…,bi−1)⊥ are reduced in the sense of Hermite and Korkin–Zolotarev. Let λi denote the successive minima of lattice L, and let b1,…,bm be a basis of L that is block reduced with block size β. We prove that for i = 1,…, m where γβ is the Hermite constant for dimension β. For block size β = 3 and odd rank m ≥ 3, we show that where the maximum is taken over all block reduced bases of all lattices L. We present critical block reduced bases achieving this maximum. Using block reduced bases, we improve Babai's construction of a nearby lattice point. Given a block reduced basis with block size β of the lattice L, and given a point x in the span of L, a lattice point υ can be found in time βO(β) satisfying These results also give improvements on the method of solving integer programming problems via basis reduction.

This publication has 11 references indexed in Scilit: