Segment and strong segment LLL-reduction of lattice bases

  • 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Author:Henrik Koy, Claus Peter SchnorrGND
Document Type:Report
Date of Publication (online):2005/07/14
Year of first Publication:2002
Publishing Institution:Universitätsbibliothek Johann Christian Senckenberg
Release Date:2005/07/14
Tag:LLL-reduction; iterated subsegments; local LLL-reduction; local coordinates; segments; shortest lattice vector
Source:Abbreviated Title: Segment and Strong Segment LLL ,
Institutes:Informatik und Mathematik / Mathematik
Informatik und Mathematik / Informatik
Dewey Decimal Classification:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
Licence (German):License LogoDeutsches Urheberrecht