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 Di becomes 0.

    Enter m1(1 ≤ m1 ≤ 1000):
    Enter n1(1 ≤ m1 ≤ n1 ≤ 1000):
    Enter m(≤ 50):
    Enter n(≤ 50):

    Enter the m × n matrix entries :

Last modified 27th September 2011
Return to main page