1

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:

enter image description here

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');

enter image description here

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!

jkovba
  • 113

1 Answers1

6

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$.

Robert Israel
  • 448,999
  • I performed the LLL on the Transpose(M), then transposed the result, and it matched the Lattice Reduction paper identically. Perhaps of note, I got a slightly wrong answer when I used the 'integer' flag as a parameter to the LLL call in Maple. Without it, it worked perfectly! Thank you so much Robert! – jkovba Apr 23 '15 at 22:20