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
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.
show moreshow less

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

    Share in Twitter Search Google Scholar
Metadaten
Author:Michael Kaib
URN:urn:nbn:de:hebis:30-12447
Document Type:Article
Language:English
Date of Publication (online):2005/07/18
Year of first Publication:1994
Publishing Institution:Univ.-Bibliothek Frankfurt am Main
Release Date:2005/07/18
Source:International Symposium on Algorithmic Number Theory, 1994 , http://www.mi.informatik.uni-frankfurt.de/research/papers.html
HeBIS PPN:22471273X
Institutes:Mathematik
Dewey Decimal Classification:510 Mathematik
Sammlungen:Universitätspublikationen
Licence (German):License Logo Veröffentlichungsvertrag für Publikationen

$Rev: 11761 $