id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
12388 add a function to solve CVP zimmerma jason was "currently Sage can solve SVP (Shortest Vector Problem) through fplll
but not CVP (Closest Vector Problem).
However fplll also provides CVP:
{{{
barbecue% echo ""[[0 0 40][0 20 0][10 0 0]] [101 79 79]"" | /usr/local/sage-4.8-linux-64bit-ubuntu_10.04.3_lts-x86_64-Linux/local/bin/fplll -a cvp
[10 4 2]
}}}
with some shortcomings explained by Xavier Pujol, one of the fplll developers: (1) if several lattice points are at (almost) the same distance from the target, the wrong one might be returned; (2) the algorithm used starts removing something from the target; if after this, the target norm is still much larger than the smallest lattice
vector, we can have a bad behaviour (in some cases, an infinite loop).
Despite those shortcomings, it would be nice to have CVP inside Sage." enhancement new major sage-6.4 linear algebra lattice reduction, CVP N/A