New practical algorithms for the approximate shortest lattice vector
- We present a practical algorithm that given an LLL-reduced lattice basis of dimension n, runs in time O(n3(k=6)k=4+n4) and approximates the length of the shortest, non-zero lattice vector to within a factor (k=6)n=(2k). This result is based on reasonable heuristics. Compared to previous practical algorithms the new method reduces the proven approximation factor achievable in a given time to less than its fourthth root. We also present a sieve algorithm inspired by Ajtai, Kumar, Sivakumar [AKS01].
Volltext Dateien herunterladen
Weitere Dienste
| Verfasserangaben: | Claus Peter SchnorrGND |
|---|---|
| URN: | urn:nbn:de:hebis:30-12018 |
| URL: | http://www.mi.informatik.uni-frankfurt.de/research/papers.html |
| Verlagsort: | Frankfurt am Main |
| Dokumentart: | Bericht |
| Sprache: | Englisch |
| Datum der Veröffentlichung (online): | 01.07.2005 |
| Jahr der Erstveröffentlichung: | 2001 |
| Veröffentlichende Institution: | Universitätsbibliothek Johann Christian Senckenberg |
| Datum der Freischaltung: | 01.07.2005 |
| Ausgabe / Heft: | Preliminary Report |
| Seitenzahl: | 16 |
| HeBIS-PPN: | 201416492 |
| Institute: | Informatik und Mathematik / Mathematik |
| Informatik und Mathematik / Informatik | |
| DDC-Klassifikation: | 5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik |
| Lizenz (Deutsch): |  Deutsches Urheberrecht |
