search

fplll / fpylll

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

CVP takes forever on a small input #235

Open maxale opened 2 years ago

maxale commented 2 years ago

I've seen this issue first in Sage: https://trac.sagemath.org/ticket/34091 and decided to give fpylll a try as well. It neither ever finishes the job but at least prints a bunch of warnings: warning: possible infinite loop in Babai's algorithm How to overcome this issue?

from fpylll import CVP, IntegerMatrix
A = IntegerMatrix.from_matrix( [ (2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, -1, 0, 1, -1, -1, 0, 1, 0, 1, 0, 0, 0, 0, 1, -1),
 (0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0),
 (1, -1, -1, 0, 0, -1, 0, 1, 0, 0, -1, 1, 0, 0, 0, -1),
 (1, -1, -1, 0, 0, -1, 0, 1, 0, 0, 1, -1, 0, 0, 0, -1),
 (-1, 1, 1, 0, 0, 1, 0, -1, 0, 0, 1, 1, 0, 0, 0, 1),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0),
 (0, 1, -1, 0, 1, 0, 0, -1, -1, 0, 0, 1, 0, 1, -1, 0),
 (0, 1, -1, 0, 1, 0, 0, -1, 1, 0, 0, 1, 0, 1, -1, 0),
 (-1, 0, 1, 0, -1, 0, 1, 1, 0, 0, -1, 0, 1, -1, 0, 0),
 (1, 0, -1, 0, 1, 0, 1, -1, 0, 0, 1, 0, -1, 1, 0, 0)
 ] )
CVP.closest_vector( A, (1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0) )