API functions for CVP heuristics

[sfilip]

Hi,

I've been using fplll in my work during the last few years, mainly to approximately solve CVP problems.

In particular, I've used Babai's nearest plane algorithm and the Kannan embedding technique. I always had to implement these methods myself when calling fplll as a library. This is not very complicated to do, but I'm wondering if it would benefit more people if the fplll API includes an interface for such heuristics.

I'm happy to help if anyone thinks this is worthwhile to include.

Thanks,

Silviu

[lducas]

Hi,

there is a babai function in fpylll, attached to a gso object. Maybe we can pushed it down to c++. I agree this is a basic function that clearly has its place in the library.

As for the Kannan embedding, well, I'm not sure there is a clear standard method for this: there is a parameter to be chosen, right ? It seems to me less relevant to put it in FPLLL, especially considering that it is not so much an algorithm, than the construction of a special purpose lattice.

At last, please note that the enumeration routine also allow for arbitrary centers, so you can natively use it for CVP/BDD types of problems.