Opened 11 years ago

Last modified 8 years ago

## #12388 new enhancement

# add a function to solve CVP

Reported by: | Paul Zimmermann | 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 9 years ago by

Milestone: | sage-5.11 → sage-5.12 |
---|

### comment:2 Changed 9 years ago by

Milestone: | sage-6.1 → sage-6.2 |
---|

### comment:3 Changed 9 years ago by

Milestone: | sage-6.2 → sage-6.3 |
---|

### comment:4 Changed 8 years ago by

Milestone: | sage-6.3 → sage-6.4 |
---|

### comment:5 Changed 8 years ago by

**Note:**See TracTickets for help on using tickets.

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