#12388: add a function to solve CVP
------------------------------+---------------------------------------------
Reporter: zimmerma | Owner: jason, was
Type: enhancement | Status: new
Priority: major | Milestone: sage-5.0
Component: linear algebra | Keywords: lattice reduction, CVP
Work_issues: | Upstream: N/A
Reviewer: | Author:
Merged: | Dependencies:
------------------------------+---------------------------------------------
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.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12388>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
