Authors
Citation
G. Rote, FINDING A SHORTEST VECTOR IN A 2-DIMENSIONAL LATTICE MODULE-M, Theoretical computer science, 172(1-2), 1997, pp. 303-308
Citations number
10
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
ISSN journal
03043975
Volume
172
Issue
1-2
Year of publication
1997
Pages
303 - 308
Database
ISI
SICI code
0304-3975(1997)172:1-2<303:FASVIA>2.0.ZU;2-E
Abstract
We find the shortest non-zero vector in the lattice of all integer mul
tiples of the vector (a, b) module 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.