Refine
Year of publication
- 1994 (1)
Document Type
- Preprint (1) (remove)
Language
- English (1)
Has Fulltext
- yes (1)
Is part of the Bibliography
- no (1)
Institute
- Mathematik (1)
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.