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,,,,,