## Applying LLL

The LLL definition and algorithm has many application in number theory, e.g., to cracking lattice-based cryptosystems, to enumerating all short vectors in a lattice, to finding relations between decimal approximations to complex numbers, to very fast univariate polynomial factorization in and more generally in where is a number fields, and to computation of kernels and images of integer matrices. LLL can also be used to solve the problem of recognizing algebraic numbers mentioned at the beginning of Section 2.5.

Suppose as above that is a decimal approximation to some algebraic number , and to for simplicity assume that (the general case of is described in []). We finish by explaining how to use LLL to find a polynomial such that is small, hence has a shot at being the minimal polynomial of .

Given a real number decimal approximation , an integer (the degree), and an integer (a function of the precision to which is known), the following steps produce a polynomial of degree at most such that is small.

1. Form the lattice in with basis the rows of the matrix whose first part is the identity matrix, and whose last column has entries

 (2.2)

(Note this matrix is so the lattice is not of full rank in , which isn't a problem, since the LLL definition also makes sense for less vectors.)
2. Compute an LLL reduced basis for the -span of the rows of , and let be the corresponding matrix. Let be the first row of and notice that is obtained from by left multiplication by an invertible integer matrix. Thus are the linear combination of the (2.5.1) that equals . Moreover, since is LLL reduced we expect that is relatively small.

3. Output . We have that , which is small. Thus may be a very good candidate for the minimal polynomial of (the algebraic number we are approximating), assuming was chosen minimally and was computed to sufficient precision.

The following is a complete implementation of the above algorithm in Sage:

def myalgdep(a, d, K=10^6):
aa = [floor(K*a^i) for i in range(d+1)]
A = identity_matrix(ZZ, d+1)
B = matrix(ZZ, d+1, 1, aa)
A = A.augment(B)
L = A.LLL()
v = L[0][:-1].list()
return ZZ['x'](v)

Here is an example of using it:

sage: R.<x> = RDF[]
sage: f = 2*x^3 - 3*x^2 + 10*x - 4
sage: a = f.roots()[0][0]; a
sage: myalgdep(a, 3, 10^6)       # not tested
2*x^3 - 3*x^2 + 10*x - 4

William Stein 2012-09-24