Filtern
Erscheinungsjahr
- 2002 (1)
Dokumenttyp
- Bericht (1) (entfernen)
Sprache
- Englisch (1) (entfernen)
Volltext vorhanden
- ja (1)
Gehört zur Bibliographie
- nein (1) (entfernen)
Schlagworte
- local LLL-reduction (1) (entfernen)
Institut
- Informatik (1)
- Mathematik (1)
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.