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].
Author: | Claus Peter SchnorrGND |
---|---|
URN: | urn:nbn:de:hebis:30-12018 |
URL: | http://www.mi.informatik.uni-frankfurt.de/research/papers.html |
Place of publication: | Frankfurt am Main |
Document Type: | Report |
Language: | English |
Date of Publication (online): | 2005/07/01 |
Year of first Publication: | 2001 |
Publishing Institution: | Universitätsbibliothek Johann Christian Senckenberg |
Release Date: | 2005/07/01 |
Issue: | Preliminary Report |
Page Number: | 16 |
HeBIS-PPN: | 201416492 |
Institutes: | Informatik und Mathematik / Mathematik |
Informatik und Mathematik / Informatik | |
Dewey Decimal Classification: | 5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik |
Licence (German): | Deutsches Urheberrecht |