This is an implementation of the LLL-algorithm.

The implementation is taken from "Handbook of applied Cryptography", which can be found at http://www.cacr.math.uwaterloo.ca/hac/

To use the program, create a matrix with the lattice basis vectors as rows. Note that there MUST be more columns than rows in the final matrix! (Otherwise they would be lin. dependent ;-) )

Let's say you created the matrix mat. Then execute lll(mat). The program will then create a new matrix called lllred, which contain the LLL reduced basis.

Simple, eh?

As an example of what LLL can be used for, let's find the greatest common divisor of the following numbers: 7362, 729, 275923 and 3729.

To do this, create this matrix:

[[1,0,0,0,736200  ]
 [0,1,0,0,72900   ]
 [0,0,1,0,27592300]
 [0,0,0,1,372900  ]]

and pas it to lll. Note the last column. It is our numbers multiplied by a large constant (here: 100). The result (which is stored in lllred) is


[[7  ,-40 ,0   ,-6,0]
 [-26,-29 ,0   ,57,0]
 [86 ,1   ,-3  ,52,0]
 [-28,-19,1,-15,100 ]]

Thus the GCD is 100/const. = 1 (const = 100, remember), and every row is an integer relation: (e.g 7 * 7362 - 40 * 729 - 6 * 3729 = 0 )

Have fun!

Jes Hansen