fpylll icon indicating copy to clipboard operation
fpylll copied to clipboard

CVP takes forever on a small input

Open maxale opened this issue 3 years ago • 0 comments

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) )

maxale avatar Jun 26 '22 22:06 maxale