### The MLLL algorithm

A is an m × n matrix of integers, whose first row is nonzero and with at least two rows.

Output:

(i) a unimodular matrix P and MLLL(A), such that PA=MLLL(A), a ρ × n matrix, whose rows are LLL-reduced and form a basis for R(A), the lattice spanned by the rows of A;

(ii) the last n - ρ rows of P form a basis for the lattice N(A) of row vectors X such that XA = 0.
The LLL parameter alpha = m1/n1 has to satisfy 1/4 < α ≤ 1, but here we use a default value 1.

See slides and the account in pp. 94-96 of *A Course in Computational Algebraic Number Theory* by Henri Cohen.

The matrix A can be entered either (i) as a string of mn integers separated by spaces, or

(ii) cut and pasted from a text file, with entries separated by spaces and each row ended by a newline.

If the matrix entered has LD rows, this is detected during the initial Gram-Schmidt process when D_{i} becomes 0.

*Last modified 27th September 2011*

Return to main page