TY  - RPRT
A1  - Koy, Henrik
A1  - Schnorr, Claus Peter
T1  - Segment and strong segment LLL-reduction of lattice bases
N2  - We present an efficient variant of LLL-reduction of lattice bases in the sense of Lenstra, Lenstra, Lov´asz [LLL82]. We organize LLL-reduction in segments of size k. Local LLL-reduction of segments is done using local coordinates of dimension 2k. Strong segment LLL-reduction yields bases of the same quality as LLL-reduction but the reduction is n-times faster for lattices of dimension n. We extend segment LLL-reduction to iterated subsegments. The resulting reduction algorithm runs in O(n3 log n) arithmetic steps for integer lattices of dimension n with basis vectors of length 2O(n), compared to O(n5) steps for LLL-reduction.
KW  - LLL-reduction
KW  - shortest lattice vector
KW  - segments
KW  - iterated subsegments
KW  - local coordinates
KW  - local LLL-reduction
Y1  - 2005
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/4246
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30-12421
UR  - http://www.mi.informatik.uni-frankfurt.de/research/papers.html
ER  -