CVP.babai broken?

[MrQubo]

With this example code CVP.babai fails to return vector belonging to the lattice:

from sage.all import *


x = randrange(2**128, 2**129)
y = randrange(2**128, 2**129)
a = randrange(2**512, 2**513)
b = randrange(2**512, 2**513)

z = a*x + b*y

M = matrix(QQ, [[a, 1, 0], [b, 0, 1]])
target = vector(QQ, [z, 2**128, 2**128])
solution = vector(QQ, [z, x, y])
scales = vector(QQ, [2**128, 1/2**128, 1/2**128])

for idx in range(3):
    M[:,idx] *= scales[idx]
    target[idx] *= scales[idx]
    solution[idx] *= scales[idx]
M, S = M._clear_denom()
target *= S
target = target.change_ring(ZZ)
solution *= S
solution = solution.change_ring(ZZ)
scales *= S

Lat = IntegralLattice(identity_matrix(3), basis=M)
assert M[0] in Lat
assert M[1] in Lat
assert solution in Lat

from fpylll import IntegerMatrix
from fpylll import CVP

def vec_cast(v):
    return tuple(map(int, v))
def mat_cast(m):
    return tuple(vec_cast(v) for v in m)

A = IntegerMatrix.from_matrix(mat_cast(M))
sol = CVP.babai(A, vec_cast(target))
assert vector(ZZ, solution) in Lat
assert vector(ZZ, sol) in Lat  # This fails

[malb]

I suspect this is simply a floating point error and thus to be expected. Note that FPyLLL is a low-level library and many functions only provide a "best effort" not a guaranteed solution.

[MrQubo]

But the description of CVP.babai says it should be numerically stable.

[malb]

Technically, it only says "more numerically stable" but your point stands, examining the algorithm it shouldn't return something not in the lattice.