TY  - RPRT
A1  - Schnorr, Claus Peter
T1  - Fast LLL-type lattice reduction
N2  - We modify the concept of LLL-reduction of lattice bases in the sense of Lenstra, Lenstra, Lovasz [LLL82] towards a faster reduction algorithm. We organize LLL-reduction in segments of the basis. Our SLLL-bases approximate the successive minima of the lattice in nearly the same way as LLL-bases. For integer lattices of dimension n given by a basis of length 2exp(O(n)), SLLL-reduction runs in O(n.exp(5+epsilon)) bit operations for every epsilon > 0, compared to O(exp(n7+epsilon)) for the original LLL and to O(exp(n6+epsilon)) for the LLL-algorithms of Schnorr (1988) and Storjohann (1996). We present an even faster algorithm for SLLL-reduction via iterated subsegments running in O(n*exp(3)*log n) arithmetic steps.
KW  - LLL-reduction
KW  - SLLL-reduction
KW  - length defect
KW  - segments
KW  - local LLLreduction
KW  - Householder reflection
KW  - floating point errors
KW  - error bounds
Y1  - 2004
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/4284
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30-12071
UR  - http://www.mi.informatik.uni-frankfurt.de/research/papers.html
ER  -