Ticket #12388 (new enhancement)
Opened 17 months ago
add a function to solve CVP
| Reported by: | zimmerma | Owned by: | jason, was |
|---|---|---|---|
| Priority: | major | Milestone: | sage-5.11 |
| Component: | linear algebra | Keywords: | lattice reduction, CVP |
| Cc: | Work issues: | ||
| Report Upstream: | N/A | Reviewers: | |
| Authors: | Merged in: | ||
| Dependencies: | Stopgaps: |
Description
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.
