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.

Note: See TracTickets for help on using tickets.