A fast variant of the Gaussian reduction algorithm
- We propose a fast variant of the Gaussian algorithm for the reduction of two dimensional lattices for the l1-, l2- and l-infinite- norm. The algorithm runs in at most O(nM(B) logB) bit operations for the l-infinite- norm and in O(n log n M(B) logB) bit operations for the l1 and l2 norm on input vectors a, b 2 ZZn with norm at most 2B where M(B) is a time bound for B-bit integer multiplication. This generalizes Schönhages monotone Algorithm [Sch91] to the centered case and to various norms.
| Author: | Michael Kaib |
|---|---|
| URN: | urn:nbn:de:hebis:30-12447 |
| URL: | http://www.mi.informatik.uni-frankfurt.de/research/papers.html |
| Document Type: | Preprint |
| Language: | English |
| Date of Publication (online): | 2005/07/18 |
| Year of first Publication: | 1994 |
| Publishing Institution: | Universitätsbibliothek Johann Christian Senckenberg |
| Release Date: | 2005/07/18 |
| Note: | Preprint, später in: International Symposium on Algorithmic Number Theory, 1994 |
| Source: | International Symposium on Algorithmic Number Theory, 1994 , http://www.mi.informatik.uni-frankfurt.de/research/papers.html |
| HeBIS-PPN: | 22471273X |
| Institutes: | Informatik und Mathematik / Mathematik |
| Dewey Decimal Classification: | 5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik |
| Licence (German): |  Deutsches Urheberrecht |
