TY - INPR
A1 - Kaib, Michael
T1 - A fast variant of the Gaussian reduction algorithm
N2 - 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.
Y1 - 2005
UR - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/4235
UR - https://nbn-resolving.org/urn:nbn:de:hebis:30-12447
UR - http://www.mi.informatik.uni-frankfurt.de/research/papers.html
N1 - Preprint, später in: International Symposium on Algorithmic Number Theory, 1994
ER -