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 $\mathbf{Z}[x]$ and more generally in $K[x]$ where $K$ 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 $\alpha$ is a decimal approximation to some algebraic number $\beta$, and to for simplicity assume that $\alpha\in\mathbf{R}$ (the general case of $\alpha \in \mathbf{C}$ is described in []). We finish by explaining how to use LLL to find a polynomial $f(x) \in \mathbf{Z}[x]$ such that $f(\alpha)$ is small, hence has a shot at being the minimal polynomial of $\beta$.

Given a real number decimal approximation $\alpha$, an integer $d$ (the degree), and an integer $K$ (a function of the precision to which $\alpha$ is known), the following steps produce a polynomial $f(x) \in \mathbf{Z}[x]$ of degree at most $d$ such that $f(\alpha)$ is small.

1. Form the lattice in $\mathbf{R}^{d+2}$ with basis the rows of the matrix $A$ whose first $(d+1) \times (d+1)$ part is the identity matrix, and whose last column has entries

   $$K, \lfloor K\alpha \rfloor, \lfloor K\alpha^2 \rfloor, \ldots \lfloor K\alpha^{d} \rfloor.$$ (2.2)

   
   
   (Note this matrix is $(d+1) \times (d+2)$ so the lattice is not of full rank in $\mathbf{R}^{d+2}$, which isn't a problem, since the LLL definition also makes sense for less vectors.)
2. Compute an LLL reduced basis for the $\mathbf {Z}$-span of the rows of $A$, and let $B$ be the corresponding matrix. Let $b_1 = (a_0, a_1, \ldots, a_{d+1})$ be the first row of $B$ and notice that $B$ is obtained from $A$ by left multiplication by an invertible integer matrix. Thus $a_0,\ldots, a_d$ are the linear combination of the (2.5.1) that equals $a_{d+1}$. Moreover, since $B$ is LLL reduced we expect that $a_{d+1}$ is relatively small.

3. Output $f(x) = a_0 + a_1 x + \cdots a_{d} x^d$. We have that $f(\alpha) \sim a_{d+1}/K$, which is small. Thus $f(x)$ may be a very good candidate for the minimal polynomial of $\beta$ (the algebraic number we are approximating), assuming $d$ was chosen minimally and $\alpha$ 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