Lattice reduction by random sampling and birthday methods
- We present a novel practical algorithm that given a lattice basis b1, ..., bn finds in O(n exp 2 *(k/6) exp (k/4)) average time a shorter vector than b1 provided that b1 is (k/6) exp (n/(2k)) times longer than the length of the shortest, nonzero lattice vector. We assume that the given basis b1, ..., bn has an orthogonal basis that is typical for worst case lattice bases. The new reduction method samples short lattice vectors in high dimensional sublattices, it advances in sporadic big jumps. It decreases the approximation factor achievable in a given time by known methods to less than its fourth-th root. We further speed up the new method by the simple and the general birthday method. n2
| Author: | Claus Peter SchnorrGND |
|---|---|
| URN: | urn:nbn:de:hebis:30-12094 |
| ISBN: | 978-3-540-00623-7 |
| ISBN: | 978-3-540-36494-8 |
| Publisher: | Springer |
| Place of publication: | Berlin [u.a.] |
| Document Type: | Conference Proceeding |
| Language: | English |
| Date of Publication (online): | 2005/07/04 |
| Year of first Publication: | 2003 |
| Publishing Institution: | Universitätsbibliothek Johann Christian Senckenberg |
| Release Date: | 2005/07/04 |
| Page Number: | 12 |
| First Page: | 145 |
| Last Page: | 156 |
| Note: | Postprint, zuerst in: Proceedings STACS 2003, LNCS 2607, Berlin: Springer, 2003, S. 145–156 |
| Source: | Lecture notes in computer science, Vol. 2607 |
| HeBIS-PPN: | 358649234 |
| Institutes: | Informatik und Mathematik / Mathematik |
| Informatik und Mathematik / Informatik | |
| Dewey Decimal Classification: | 5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik |
| Licence (German): |  Deutsches Urheberrecht |
