add a function to solve CVP

[zimmermann6]

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.

Component: linear algebra

Keywords: lattice reduction, CVP

Issue created by migration from https://trac.sagemath.org/ticket/12388

[miguelmarco]

comment:5

Indeed it works, but it is not documented in fplll. Do you know if it can also works in the fplll library? In the source code (file svpcvp.h), the function closestVector is commented as "experimental, do not use".