How to use Maple's LLL Function to Break a Merkle-Hellman Knapsack

Question

This question probably isn't as hard as the title might imply. I'm working on my crypto final project and have decided to use Shamir's method (using the LLL algorithm) to break knapsack using Maple.

I'm trying run Maple's LLL algorithm on the following matrix from this paper by Mark Stamp.

Here is a picture of the matrix, which they call M:

And here is my Maple code which (appears to) construct precisely that matrix:

n := 491
m := 41
c := 548
identity := Matrix(IdentityMatrix(8))
k_pub := Matrix(`<|>`(`mod`(m*k_prv[1], n), `mod`(m*k_prv[2], n), `mod`(m*k_prv[3], n), `mod`(m*k_prv[4], n), `mod`(m*k_prv[5], n), `mod`(m*k_prv[6], n), `mod`(m*k_prv[7], n), `mod`(m*k_prv[8], n), -c))
zero_vector := Matrix(8, 1)
M := Matrix(`<|>`(identity, zero_vector))
M := Matrix(`<,>`(M, k_pub))

This appears to reconstruct the exact example from the paper mentioned above, but when I run the LLL algorithm as the paper suggests, I get:

with(IntegerRelations, LLL);
LLL(Matrix(M), 'integer');

This is wrong according to the paper, so I think my Maple is somehow wrong. Maybe I'm not creating a Matrix object correctly?

Thank you very much, in advance, for your time and help!

Answer 1

I believe you want to apply LLL to the transpose of that Matrix (and then transpose the result). LLL on a Matrix looks at its row vectors, and here you want to apply LLL to the columns of $M$.