Fast unimodular reduction: planar integer lattices
Chee Keng Yap · 1992
The author shows that a shortest basis for the 2-dimensional lattice Lambda (u, v) generated by an input pair u, v in Z/sup 2/ can be computed in O(M(n) log n) where n is the bit-size of the input numbers and M(n) is the complexity of multiplying two n-bit integers. This generalizes Schonhage's technique (1971) for fast integer GCD to a higher dimension.>