search

fplll / fpylll

A Python interface for https://github.com/fplll/fplll
GNU General Public License v2.0
119 stars 60 forks source link

replace Sage's closest vector by fpylll's code? #176

Open dimpase opened 4 years ago

dimpase commented 4 years ago

We now have to deal with Sage's IntegerLattice bugs on https://trac.sagemath.org/ticket/29866 - and it appears that for some reason Sage does not use fpylll's code for closest_vector, but does something on its own (and that got broken in Sage 8.5, as it turned out).

On the example showing Sage's bug, fpylll does the job just fine. Would it be beneficial to replace Sage's code with a code that just calls fpylll ?

malb commented 4 years ago

FP(y)LLL only permits integer target vectors, but Sage's current code handles rational target vectors too. This is mostly an interface issue but still.

dimpase commented 4 years ago

Does FP(y)LLL have code to compute the Voronoi cell? Further digging on the Sage ticket points at a mysterious breakage in calculate_voronoi_cell()

malb commented 4 years ago

Nope. Well, a sieving db is an approximate Voronoi cell so G6K could be used, but it would be heuristic and not provable.