TY - GEN

T1 - Fast unimodular reduction

T2 - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992

AU - Yap, Chee K.

N1 - Publisher Copyright:
© 1992 IEEE.

PY - 1992

Y1 - 1992

N2 - The author shows that a shortest basis for the 2-dimensional lattice Lambda (u, v) generated by an input pair u, v in Z2 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.

AB - The author shows that a shortest basis for the 2-dimensional lattice Lambda (u, v) generated by an input pair u, v in Z2 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.

UR - http://www.scopus.com/inward/record.url?scp=0004802167&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0004802167&partnerID=8YFLogxK

U2 - 10.1109/SFCS.1992.267808

DO - 10.1109/SFCS.1992.267808

M3 - Conference contribution

AN - SCOPUS:0004802167

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 437

EP - 446

BT - Proceedings - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992

PB - IEEE Computer Society

Y2 - 24 October 1992 through 27 October 1992

ER -