to an unknown quadratic equation with integer coefficients, one may apply LLL reduction to the lattice in spanned by and . The first vector in the reduced basis will be an integer linear combination of these three, thus necessarily of the form ; but such a vector is "short" only if a, b, c are small and is even smaller. Thus the first three entries of this short vector are likely to be the coefficients of the integral quadratic polynomial which has r as a root. In this example the LLL algorithm finds the shortest vector to be [1, -1, -1, 0.00025] and indeed has a root equal to the golden ratio, 1.6180339887.... Properties of LLL-reduced basis Let be a -LLL-reduced basis of a lattice . From the definition of LLL-reduced basis, we can derive several other useful properties about . The first vector in the basis cannot be much larger than the shortest non-zero vector: . In particular, for , this gives . The first vector in the basis is also bounded by the determinant of the lattice: . In particular, for , this gives . The product of the norms of the vectors in the basis cannot be much larger than the determinant of the lattice: let , then . LLL algorithm pseudocode The following description is based on , with the corrections from the errata. INPUT a lattice basis b0, b1, ..., bn in Zm a parameter δ with 1/4 < δ < 1, most commonly δ = 3/4 PROCEDURE B* <- GramSchmidt({b0, ..., bn}) = {b0*, ..., bn*}; and do not normalize μi,j <- InnerProduct(bi, bj*)/InnerProduct(bj*, bj*); using the most current values of bi and bj* k <- 1; while k <= n do for j from k−1 to 0 do if |μk,j| > 1/2 then bk <- bk − ⌊μk,j⌉bj; Update B* and the related μi,j's as needed. (The naive method is to recompute B* whenever bi changes: B* <- GramSchmidt({b0, ..., bn}) = {b0*, ..., bn*}) end if end for if InnerProduct(bk*, bk*) > (δ − μ2k,k−1) InnerProduct(bk−1*, bk−1*) then k <- k + 1; else Swap bk and bk−1; Update B* and the related μi,j's as needed. k <- max(k−1, 1); end if end while return B the LLL reduced basis of {b0, ..., bn} OUTPUT the reduced basis b0, b1, ..., bn in Zm Examples Example from Z3 Let a lattice basis