Opened 10 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:

Status badges

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 jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:2 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:3 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:4 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:5 Changed 7 years ago by mmarco

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".

Note: See TracTickets for help on using tickets.