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