Fast LLL-type lattice reduction
- 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.
Weitere Dienste
| Verfasserangaben: | Claus Peter SchnorrGND |
|---|---|
| URN: | urn:nbn:de:hebis:30-12071 |
| URL: | http://www.mi.informatik.uni-frankfurt.de/research/papers.html |
| Dokumentart: | Bericht |
| Sprache: | Englisch |
| Jahr der Fertigstellung: | 2004 |
| Jahr der Erstveröffentlichung: | 2004 |
| Veröffentlichende Institution: | Universitätsbibliothek Johann Christian Senckenberg |
| Datum der Freischaltung: | 04.07.2005 |
| Freies Schlagwort / Tag: | Householder reflection; LLL-reduction; SLLL-reduction; error bounds; floating point errors; length defect; local LLLreduction; segments |
| HeBIS-PPN: | 191533750 |
| Institute: | Informatik und Mathematik / Mathematik |
| Informatik und Mathematik / Informatik | |
| DDC-Klassifikation: | 5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik |
| Lizenz (Deutsch): |  Deutsches Urheberrecht |
