# Sagemath: Closest_vector not working on mxn matrix when m!=n?

This post is a wiki. Anyone with karma >750 is welcome to improve it.

I want to solve the following closest vector problem: Given an mxn matrix A where A \in Z_q^n and a vector u, find the closest vector to u in the q-ary lattice spanned by A, that is in the lattice that contains all points y=(Az mod q) for some z \in Z_q^n. Do to do this, I implemented the following sage code.

import random
from sage.modules.free_module_integer import IntegerLattice
Q = 7
B = [[1,2],[4,5],[3,6],[5,2]]
R = Integers(Q)
MS = MatrixSpace(R, 4, 2)
A= MS(B)
N = A.change_ring(ZZ)
N = N.augment(Q * identity_matrix(4)) # To enforce calculation modulo q
L = IntegerLattice(N)
u = [1,2,3,4]
print(L.closest_vector(u))


From my understanding, this should work even though m!=n, because the vectors in the lattice spanned by the Basis N are still 4-dimensional. However, I am getting the following error:

TypeError: unsupported operand parent(s) for *: 'Full MatrixSpace of 6 by 6 dense matrices over Rational Field' and 'Ambient free module of rank 4 over the principal ideal domain Integer Ring'


What am I doing wrong?

edit retag close merge delete

Sort by » oldest newest most voted

In order to get the bug in some code, a good way to proceed is to reproduce the error using alternative, explicit, minimal code. This also applies for a question, written to go to the point without contorsions, and if the answer does not show after the own try to find it - which is the best way to improve the own path through structure and coding - , it will pop up in a second on this site (or elsewhere in a similar situation).

(There is no need to import the random package, there is no need to use a matrix space in between, then lift a matrix from characteristic seven, masked by Q = 7, then extend this matrix by seven times the identity matrix. You certainly had that matrix in your hand, so print it and use it as it is.)

I did the following to reproduce the error:

from sage.modules.free_module_integer import IntegerLattice

A = matrix(ZZ, [[1, 2], [4, 5], [3, 6], [5, 2]])
C = A.augment(7 * identity_matrix(4))
L = IntegerLattice(C)
print(L)


The print shows the following object, and shortly after the print i also wanted to see the basis, to confirm my suspicion:

Free module of degree 6 and rank 4 over Integer Ring
User basis matrix:
[1 2 7 0 0 0]
[5 2 0 0 0 7]
[4 5 0 7 0 0]
[3 6 0 0 7 0]
sage: L.basis()
[
(1, 2, 7, 0, 0, 0),
(5, 2, 0, 0, 0, 7),
(4, 5, 0, 7, 0, 0),
(3, 6, 0, 0, 7, 0)
]


So we do not have an object of vectors inside $\Bbb Z^4$, but rather inside $\Bbb Z^6$, and some vector with four components will be incompatible to this. Instead, let us try the transposed of the above $C$:

from sage.modules.free_module_integer import IntegerLattice

A = matrix(ZZ, [[1, 2], [4, 5], [3, 6], [5, 2]])
C = A.augment(7 * identity_matrix(4))
L = IntegerLattice(C.transpose())

u = [1, 2, 3, 4]
print(L.closest_vector(u))


This gives:

(1, 1, 3, 4)

more