Ticket #12388 (new enhancement)
Opened 17 months ago
add a function to solve CVP
|Reported by:||zimmerma||Owned by:||jason, was|
|Component:||linear algebra||Keywords:||lattice reduction, CVP|
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.