Skip to content

CVP takes forever on a small input #235

@maxale

Description

@maxale

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

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions