ok, this is an ad-hoc argument does not work in general. The specific implementation of M-V in sage does not seem to solve (fast) CVP even for dimensions n>=8. Of course this is not a problem of SAGE (since the algorithm is deterministic and of exponential time). I'm wondering if the experimental algorithm of fplll it does solve (fast) cvp at least for low dimensions say n<=40 ( using enum which is better in practice than M-V). Also the simple Babai algorithm in dimensions say n<=20 is polynomial and gives very often the right vector. thank you
On Monday, May 26, 2014 10:58:32 PM UTC+3, Martin Albrecht wrote: > > the fpLLL docs state that CVP support is experimental and shouldn't be > used > yet. If your CVP instance is BDD (i.e. you know a bound) you could reduce > it > to uSVP e.g. like this: http://eprint.iacr.org/2013/602.pdf > > On Monday 26 May 2014 12:45:55 J.A. Ketch wrote: > > for CVP the only function is L.closest_vector(t) which uses > > Miccianchio-Voulgaris algorithm. Is there also another algorithm from > > fplll? > > thanks > > > > On Tuesday, May 13, 2014 8:37:25 PM UTC+3, Martin Albrecht wrote: > > > On Tuesday 13 May 2014 09:51:27 J.A. Ketch wrote: > > > > are the following algorithms implemented in sage? > > > > enum algorithm (for svp and cvp) > > > > > > fpLLL has enumeration for finding the shortest vector (the code for > CVP is > > > experimental according to the docs). There's a ticket on trac > implementing > > > an > > > interface > > > > > > http://trac.sagemath.org/ticket/15976 > > > > > > > > miccianchio-voulgaris algorithm(for svp and cvp) > > > > > > The same ticket also contains code for CVP computation using Voronoi > cell > > > computation (which was actually written ages ago, but never merged) > > > > > > > thank you > > > > > > Cheers, > > > Martin -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.
