I did not use LLL algorithm but I think this book will help you "The LLL Algorithm: Survey and Applications" by Nguyen, Phong Q.; Vallée, Brigitte (2010)

I used LLL to implement Rathburn's algorithm for reducing the Mordell-Weil basis of points on the elliptic curve, in particular i used the qflllgram() function in PARI/GP (it is a variant of qflll() function).

You can download PARI/GP from: http://pari.math.u-bordeaux.fr/download.html

Here are the (somewhat lengthy) descriptions of these functions from the documentation:

qflll(x,{flag = 0})

LLL algorithm applied to the columns of the matrix x. The columns of x may be linearly dependent. The result is a unimodular transformation matrix T such that x .T is an LLL-reduced basis of the lattice generated by the column vectors of x. Note that if x is not of maximal rank T will not be square. The LLL parameters are (0.51,0.99), meaning that the Gram-Schmidt coefficients for the final basis satisfy mu_{i,j} = |v_i| for any two distinct basis vectors v_i, v_j.

This is faster than flag = 1, esp. when one row is huge compared to the other rows (knapsack-style), and should quickly produce relatively short vectors. The resulting basis is not LLL-reduced in general. If LLL reduction is eventually desired, avoid this partial reduction: applying LLL to the partially reduced matrix is significantly slower than starting from a knapsack-type lattice.

If flag = 4, as flag = 1, returning a vector [K, T] of matrices: the columns of K represent a basis of the integer kernel of x (not LLL-reduced in general) and T is the transformation matrix such that x.T is an LLL-reduced Z-basis of the image of the matrix x.

If flag = 5, case as case 4, but x may have polynomial coefficients.

If flag = 8, same as case 0, but x may have polynomial coefficients.

The library syntax is GEN qflll0(GEN x, long flag). Also available are GEN lll(GEN x) (flag = 0), GEN lllint(GEN x) (flag = 1), and GEN lllkerim(GEN x) (flag = 4).

qflllgram(G,{flag = 0})

same as qflll, except that the matrix G = x~ * x is the Gram matrix of some lattice vectors x, and not the coordinates of the vectors themselves. In particular, G must now be a square symmetric real matrix, corresponding to a positive quadratic form (not necessarily definite: x needs not have maximal rank). The result is a unimodular transformation matrix T such that x.T is an LLL-reduced basis of the lattice generated by the column vectors of x. See qflll for further details about the LLL implementation.

If flag = 0 (default), assume that G has either exact (integral or rational) or real floating point entries. The matrix is rescaled, converted to integers and the behavior is then as in flag = 1.

If flag = 1, assume that G is integral. Computations involving Gram-Schmidt vectors are approximate, with precision varying as needed (Lehmer's trick, as generalized by Schnorr). Adapted from Nguyen and Stehlé's algorithm and Stehlé's code ( fplll-1.3).

flag = 4: G has integer entries, gives the kernel and reduced image of x.

flag = 5: same as 4, but G may have polynomial coefficients.

The library syntax is GEN qflllgram0(GEN G, long flag). Also available are GEN lllgram(GEN G) (flag = 0), GEN lllgramint(GEN G) (flag = 1), and GEN lllgramkerim(GEN G) (flag = 4).

Thank you Samah and Konrad!

I shall have a look at these in detail!

Hi all,

just to inform you, there is also Damien Stehle's implementation of the LLL and it is probably the fastest implementation at the moment!