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 -