Block Korkin–Zolotarev bases and successive minima
- 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.
Author: | Claus Peter SchnorrGND |
---|---|
URN: | urn:nbn:de:hebis:30-12230 |
DOI: | https://doi.org/10.1017/S0963548300001371 |
ISSN: | 1469-2163 |
ISSN: | 0963-5483 |
Document Type: | Article |
Language: | English |
Year of Completion: | 1996 |
Year of first Publication: | 1994 |
Publishing Institution: | Universitätsbibliothek Johann Christian Senckenberg |
Release Date: | 2005/07/11 |
Page Number: | 19 |
First Page: | 1 |
Last Page: | 19 |
Note: | Überarbeitete Fassung 1996, ursprünglich erschienen in: Combinatorics, probability & computing, 3.1994, Nr. 4, S. 507-533, doi:10.1017/S0963548300001371 |
Source: | http://www.mi.informatik.uni-frankfurt.de/research/papers.html |
HeBIS-PPN: | 358645956 |
Institutes: | Informatik und Mathematik / Mathematik |
Informatik und Mathematik / Informatik | |
Dewey Decimal Classification: | 5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik |
Licence (German): | Deutsches Urheberrecht |