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.

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

(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.) - 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.
- 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