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.
Volltext Dateien herunterladen
Weitere Dienste
| Verfasserangaben: | Henrik Koy, Claus Peter SchnorrGND |
|---|---|
| URN: | urn:nbn:de:hebis:30-12421 |
| URL: | http://www.mi.informatik.uni-frankfurt.de/research/papers.html |
| Dokumentart: | Bericht |
| Sprache: | Englisch |
| Datum der Veröffentlichung (online): | 14.07.2005 |
| Jahr der Erstveröffentlichung: | 2002 |
| Veröffentlichende Institution: | Universitätsbibliothek Johann Christian Senckenberg |
| Datum der Freischaltung: | 14.07.2005 |
| Freies Schlagwort / Tag: | LLL-reduction; iterated subsegments; local LLL-reduction; local coordinates; segments; shortest lattice vector |
| Quelle: | Abbreviated Title: Segment and Strong Segment LLL , http://www.mi.informatik.uni-frankfurt.de/research/papers.html |
| HeBIS-PPN: | 185558976 |
| Institute: | Informatik und Mathematik / Mathematik |
| Informatik und Mathematik / Informatik | |
| DDC-Klassifikation: | 5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik |
| Lizenz (Deutsch): |  Deutsches Urheberrecht |
