## LLL Reduced Basis

Given a basis for , the Gramm-Schmidt orthogonalization process produces an orthogonal basis for as follows. Define inductively

where

Example 2.5.1   We compute the Gramm-Schmidt orthogonal basis of the rows of a matrix. Note that no square roots are introduced in the process; there would be square roots if we constructed an orthonormal basis.
sage: A = matrix(ZZ, 2, [1,2, 3,4]); A
[1 2]
[3 4]
sage: Bstar, mu = A.gramm_schmidt()


The rows of the matrix are obtained from the rows of by the Gramm-Schmidt procedure.

sage: Bstar
[   1    2]
[ 4/5 -2/5]
sage: mu
[   0    0]
[11/5    0]


A lattice is a subgroup that is free of rank such that .

Definition 2.5.2 (LLL-reduced basis)   The basis for a lattice is LLL reduced if for all ,

and for each ,

For example, the basis , for a lattice is not LLL reduced because and

However, the basis , for is LLL reduced, since

and

sage: A = matrix(ZZ, 2, [1,2, 3,4])
sage: A.LLL()
[1 0]
[0 2]


William Stein 2012-09-24