On Thu, Dec 12, 2024 at 10:27 AM Xavier Wong <zywongxav...@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 > > 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] > > -- > 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+unsubscr...@googlegroups.com. > To view this discussion visit > https://groups.google.com/d/msgid/sage-support/c7235777-3eb1-4492-b736-675b8ab5d6cen%40googlegroups.com. -- 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+unsubscr...@googlegroups.com. To view this discussion visit https://groups.google.com/d/msgid/sage-support/CAAWYfq1XVRbVS7n%2B8WFQJps4OeKxi0V4EytcKZ-MSRs3%3DLUgSQ%40mail.gmail.com.
