Refine
Year of publication
- 2001 (1) (remove)
Document Type
- Report (1) (remove)
Language
- English (1) (remove)
Has Fulltext
- yes (1)
Is part of the Bibliography
- no (1)
Institute
- Mathematik (1) (remove)
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].