A hierarchy of polynomial time lattice basis reduction algorithms
- We present a hierarchy of polynomial time lattice basis reduction algorithms that stretch from Lenstra, Lenstra, Lovász reduction to Korkine–Zolotareff reduction. Let λ(L) be the length of a shortest nonzero element of a lattice L. We present an algorithm which for k∈N finds a nonzero lattice vector b so that |b|2⩽(6k2)nkλ(L)2. This algorithm uses O(n2(kk+o(k))+n2)log B) arithmetic operations on O(n log B)-bit integers. This holds provided that the given basis vectors b1,…,bn∈Zn 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.
Volltext Dateien herunterladen
Weitere Dienste
| Verfasserangaben: | Claus Peter SchnorrGND |
|---|---|
| URN: | urn:nbn:de:hebis:30:3-758869 |
| DOI: | https://doi.org/10.1016/0304-3975(87)90064-8 |
| ISSN: | 0304-3975 |
| Titel des übergeordneten Werkes (Englisch): | Theoretical Computer Science |
| Verlag: | Elsevier |
| Verlagsort: | Amsterdam [u.a.] |
| Dokumentart: | Wissenschaftlicher Artikel |
| Sprache: | Englisch |
| Datum der Veröffentlichung (online): | 18.09.2023 |
| Jahr der Erstveröffentlichung: | 1987 |
| Veröffentlichende Institution: | Universitätsbibliothek Johann Christian Senckenberg |
| Datum der Freischaltung: | 18.09.2023 |
| Jahrgang: | 53 |
| Ausgabe / Heft: | 2-3 |
| Seitenzahl: | 24 |
| Erste Seite: | 201 |
| Letzte Seite: | 224 |
| HeBIS-PPN: | 51428272X |
| Institute: | Informatik und Mathematik / Informatik |
| DDC-Klassifikation: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik |
| Sammlungen: | Universitätspublikationen |
| Lizenz (Deutsch): |  Creative Commons - CC BY-NC-ND - Namensnennung - Nicht kommerziell - Keine Bearbeitungen 4.0 International |
