Günter Rote:

Finding a shortest vector in a two-dimensional lattice modulo m

Theoretical Computer Science 172 (1997), 303–308. doi:10.1016/S0304-3975(96)00185-5


We find the shortest non-zero vector in the lattice of all integer multiples of the vector (a,b) modulo m, for given integers 0<a,b<m. We reduce the problem to the computation of a Minkowski-reduced basis for a planar lattice and thereby show that the problem can be solved in O(log m (log log m)2) bit operations.
  PostScript file (gzipped)   pdf file TeX .dvi file (gzipped)
other papers about this subject
Last update: October 26, 2001.