TY  - JOUR
A1  - Schnorr, Claus Peter
T1  - Block Korkin–Zolotarev bases and successive minima
N2  - Let b1, . . . , bm 2 IRn be an arbitrary basis of lattice L that is a block Korkin Zolotarev basis with block size ¯ and let ¸i(L) denote the successive minima of lattice L. We prove that for i = 1, . . . ,m 4 i + 3 ° 2 i 1 ¯ 1 ¯ · kbik2/¸i(L)2 · ° 2m i ¯ 1 ¯ i + 3 4 where °¯ is the Hermite constant. For ¯ = 3 we establish the optimal upper bound kb1k2/¸1(L)2 · µ3 2¶m 1 2 1 and we present block Korkin Zolotarev lattice bases for which this bound is tight. We improve the Nearest Plane Algorithm of Babai (1986) using block Korkin Zolotarev bases. Given a block Korkin Zolotarev basis b1, . . . , bm with block size ¯ and x 2 L(b1, . . . , bm) a lattice point v can be found in time ¯O(¯) satisfying kx vk2 · m° 2m ¯ 1 ¯ minu2L kx uk2.
Y1  - 1996
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/4254
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30-12230
SN  - 1469-2163
SN  - 0963-5483
N1  - Überarbeitete Fassung 1996, ursprünglich erschienen in: Combinatorics, probability & computing, 3.1994, Nr. 4, S. 507-533, doi:10.1017/S0963548300001371
SP  - 1
EP  - 19
ER  -