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
Abstract
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.
Last update: October 26, 2001.