Opened 9 years ago
Last modified 7 years ago
#12388 new enhancement
add a function to solve CVP
Reported by: | zimmerma | Owned by: | jason, was |
---|---|---|---|
Priority: | major | Milestone: | sage-6.4 |
Component: | linear algebra | Keywords: | lattice reduction, CVP |
Cc: | Merged in: | ||
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
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.
Change History (5)
comment:1 Changed 8 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:2 Changed 7 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:3 Changed 7 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:4 Changed 7 years ago by
- Milestone changed from sage-6.3 to sage-6.4
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".