Refine
Year of publication
Document Type
- Article (10)
- Preprint (10)
- Report (8)
- Conference Proceeding (2)
- Part of a Book (1)
Language
- English (31)
Has Fulltext
- yes (31)
Is part of the Bibliography
- no (31) (remove)
Keywords
- LLL-reduction (3)
- computational complexity (2)
- segments (2)
- Block Korkin—Zolotarev reduction (1)
- Dirichlet bound (1)
- Householder reflection (1)
- Knapsack problem (1)
- Kongress (1)
- Korkin—Zolotarev reduction (1)
- Kryptosystem (1)
Institute
- Mathematik (31) (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].