Mathematik
Refine
Year of publication
- 2004 (2) (remove)
Document Type
- Conference Proceeding (1)
- Report (1)
Has Fulltext
- yes (2)
Is part of the Bibliography
- no (2)
Keywords
- Householder reflection (1)
- LLL-reduction (1)
- SLLL-reduction (1)
- error bounds (1)
- floating point errors (1)
- length defect (1)
- local LLLreduction (1)
- segments (1)
Institute
- Informatik (2) (remove)
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.