TY  - RPRT
A1  - Schnorr, Claus Peter
T1  - New practical algorithms for the approximate shortest lattice vector
N2  - 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].
Y1  - 2005
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/4291
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30-12018
UR  - http://www.mi.informatik.uni-frankfurt.de/research/papers.html
IS  - Preliminary Report
CY  - Frankfurt am Main
ER  -