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.
Download full text files
Additional Services
| 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 |
