Sagemath FPYLLL Runtime Error

[Xavier Wong]

When I utilise the BKZ algorithm on a basis as shown in the code below, I will receive a runtime error "terminate called recursively". After running the code again, I got another error that states "infinite loop in babai". This made me confused as to what the issue is. I do not know if this is the right place to ask, but does anyone have any advice on how to fix this issue?

Platform: intel i7

OS: windows 11

Sage version: 10.4

Code

from fpylll import BKZ, IntegerMatrix
import numpy as np

def small_poly_vector(size, high=2, low=-1):

    v = [R(list(np.random.randint(low, high, N)))

    for _ in range(size)] if size==1:

        return v[0]

    return vector(v)

Q = 3329

N = 64

k = 2

eta1 = 2

eta2 = 2

HALF_Q = int((Q + 1) / 2)

PR.<x> = PolynomialRing(GF(Q))

R.<z> = PR.quotient_ring(x^N + 1)

A = random_matrix(R, k, k)

s = small_poly_vector(k, eta1)

e = small_poly_vector(k, eta2)

t = A*s+e

A_t = matrix(QQ, 2*N+1, 2*N)

A_t[:N,:N] = A[0][0].matrix()

A_t[N:2*N,:N] = A[0][1].matrix()

A_t[:N,N:] = A[1][0].matrix()

A_t[N:2*N,N:] = A[1][1].matrix()

A_t[2*N] = [int(i) for i in t[0]]+[int(i) for i in t[1]]

lattice_size = 4*N+1

B = matrix(QQ, lattice_size, lattice_size)

B[:2*N,:2*N] = Q * identity_matrix(QQ, 2*N, 2*N)

B[2*N:,:2*N] = A_t

B[2*N:,2*N:] = identity_matrix(QQ, 2*N+1, 2*N+1)

B = IntegerMatrix.from_matrix([[int(entry) for entry in row] for row in B])

BKZ.reduction(B, o=BKZ.Param(block_size=20))

reduced_matrix = [[B[i, j] for j in range(B.ncols)] for i in range(B.nrows)]

shortest_vector = reduced_matrix[0]

[Dima Pasechnik]

On Thu, Dec 12, 2024 at 10:27 AM Xavier Wong <zywong...@gmail.com> wrote:
>
> When I utilise the BKZ algorithm on a basis as shown in the code below, I will receive a runtime error "terminate called recursively". After running the code again, I got another error that states "infinite loop in babai". This made me confused as to what the issue is. I do not know if this is the right place to ask, but does anyone have any advice on how to fix this issue?

It might be insufficient precision of floats used by default. Cf.

sage: BKZ.reduction(B, o=BKZ.Param(block_size=10),float_type="mpfr",
precision=53)
terminate called recursively

- which is the error you get, but

sage: BKZ.reduction(B, o=BKZ.Param(block_size=10),float_type="mpfr",
precision=70)

doesn't terminate quickly (I didn't wait for it to finish)

fpylll's GitHub might be a better place to report this, and it seems
you apparently did this already
https://github.com/fplll/fpylll/issues/287

HTH
Dima

> --
> You received this message because you are subscribed to the Google Groups "sage-support" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-support...@googlegroups.com.
> To view this discussion visit https://groups.google.com/d/msgid/sage-support/c7235777-3eb1-4492-b736-675b8ab5d6cen%40googlegroups.com.