A lattice is an infinite set that can be specified by finitely many integer combinations. That makes it a natural object for computational number theory: arithmetic constraints become geometry, and geometric algorithms can expose short relations hidden inside large coefficients.
The Lenstra–Lenstra–Lovász algorithm does not generally solve the shortest-vector problem exactly. Instead, it transforms a poor basis into a reduced basis whose vectors are shorter and more nearly orthogonal, with a provable approximation guarantee. That weaker objective is strong enough to support polynomial factorisation, Diophantine approximation, integer-relation searches and many other algorithms.
This is Guide 15 in the Bukit Timah Tutor Computational Number Theory series. It follows fast integer multiplication and prepares the transition to computational algebraic number theory. It is an advanced enrichment route. Return to the BTT Mathematics Hub for the wider Mathematics estate.
1. A lattice from a basis
Let b1,…,bm be linearly independent vectors in R^n. The lattice they generate is
L = {z1b1+…+zmbm : z_i in Z}.
The rank is m. If m=n, the lattice is full rank in R^n. Different bases can generate exactly the same lattice.
For example, b1=(4,1) and b2=(1,3) generate all integer combinations z1(4,1)+z2(1,3). Replacing b2 by b2−b1 gives another basis of the same lattice because the change of coordinates uses an integer matrix with determinant ±1.
This last condition is fundamental: unimodular basis transformations preserve the lattice.
2. Basis vectors are not lattice invariants
A long awkward basis may generate a lattice containing very short vectors. Therefore one cannot estimate the intrinsic geometry of a lattice simply by inspecting the lengths of the supplied basis vectors.
The lattice remains unchanged under swapping basis vectors, changing a vector’s sign or replacing one vector by itself plus an integer multiple of another. These elementary operations correspond to unimodular transformations.
LLL repeatedly applies transformations of this kind. Its output is not a different lattice; it is a better coordinate system for the same one.
3. Determinant and covolume
For a full-rank lattice with basis matrix B whose columns are the basis vectors, the absolute determinant |det B| is the covolume: the volume of a fundamental parallelepiped.
For b1=(4,1), b2=(1,3):
det [[4,1],[1,3]] = 12−1 = 11.
Any other basis of the same full-rank lattice has determinant ±11. This gives a cheap check that a sequence of claimed unimodular basis operations has not accidentally changed the lattice.
For a rank-m lattice embedded in a higher-dimensional space, the covolume is sqrt(det(B^T B)).
4. Gram–Schmidt exposes geometric dependence
Given basis vectors b1,…,bm, Gram–Schmidt builds orthogonal vectors b1*,…,bm*:
b_i* = b_i − Σ(j<i) μ_ij b_j*, μ_ij = <b_i,b_j*>/||b_j*||².
The starred vectors need not belong to the lattice because the coefficients μ_ij are generally not integers. They are analytical tools that measure how much of one basis vector lies in directions already represented by earlier vectors.
In numerical linear algebra, Gram–Schmidt is often introduced as a route to orthogonal bases. In LLL, the orthogonalisation is bookkeeping that guides integer basis changes.
5. First Gram–Schmidt calculation
Take b1=(4,1), b2=(1,3). Then b1*=b1 and ||b1*||²=17.
The Gram–Schmidt coefficient is
μ21 = <(1,3),(4,1)>/17 = 7/17.
So
b2* = (1,3)−(7/17)(4,1)
= (−11/17,44/17).
Its squared norm is 121/17. The coefficient 7/17 is already within the usual size-reduced interval [−1/2,1/2].
6. Size reduction
If |μ_ij| is large, replace b_i by
b_i ← b_i − round(μ_ij)b_j.
This is an integer column operation and therefore preserves the lattice. After the update, the new Gram–Schmidt coefficient relative to b_j* is closer to zero.
The usual LLL size-reduction condition is |μ_ij|≤1/2 for j<i. Tie-breaking when μ is exactly a half should be specified by an implementation because different rounding conventions can produce different but still valid reduced bases.
7. Size reduction alone is not enough
A basis can be size reduced but ordered badly. A later Gram–Schmidt vector may be much shorter than the previous one, indicating that the current sequence hides a better leading direction.
LLL therefore combines size reduction with a swap condition. Choose a parameter δ with 1/4<δ<1, commonly δ=3/4. The Lovász condition for adjacent vectors is
δ ||b_(k−1)*||² ≤ ||b_k*||² + μ_(k,k−1)² ||b_(k−1)*||².
Equivalently, (δ−μ²)||b_(k−1)*||²≤||b_k*||².
If the condition fails, swap b_k and b_(k−1), recompute the affected Gram–Schmidt data and move backward in the basis.
8. A complete two-dimensional LLL example
For b1=(4,1), b2=(1,3), we found μ=7/17 and ||b2*||²=121/17. With δ=3/4, the Lovász inequality fails, so swap the vectors.
The basis is now b1=(1,3), b2=(4,1). The new coefficient is
μ21 = 7/10.
Size reduce by subtracting b1 once:
b2 ← (4,1)−(1,3) = (3,−2).
Now μ21=−3/10. The orthogonal component is
b2* = (3,−2)−(−3/10)(1,3)
= (33/10,−11/10).
Its squared norm is 121/10. The Lovász right-hand comparison becomes
(3/4−9/100)·10 = 6.6, while ||b2*||² = 12.1.
The condition now holds. The reduced basis is (1,3),(3,−2).
The determinant is 1·(−2)−3·3=−11, whose absolute value matches the original 11. The lattice has been preserved.
9. What LLL means by reduced
An LLL-reduced basis satisfies two families of inequalities: size-reduced Gram–Schmidt coefficients and the Lovász condition between successive orthogonalised directions.
These conditions do not make the basis unique. Different valid rounding choices, δ values or equivalent initial bases can produce different reduced outputs.
The point is structural quality rather than canonical form: vectors are controlled in length and the basis avoids severe near-linear dependence.
10. Why the algorithm terminates
LLL uses a potential built from volumes or Gram–Schmidt lengths. Size reduction does not increase the relevant potential, while a Lovász-triggered swap decreases it by a controlled factor.
Because an integer lattice has discrete determinant structure and the basis entries have bounded input size, the potential cannot decrease forever. This yields polynomial-time termination for fixed reduction parameter δ away from one.
The full proof requires careful bit-complexity analysis because Gram–Schmidt coefficients are rational numbers whose numerator and denominator sizes can grow. Practical implementations use exact rational arithmetic, floating approximations with safeguards, or hybrid strategies.
11. The first-vector approximation guarantee
For the standard δ=3/4 form, LLL guarantees that the first reduced basis vector is within an exponential-in-dimension factor of a shortest nonzero lattice vector. A common statement is
||b1|| ≤ 2^((m−1)/2) λ1(L),
where λ1(L) is the shortest nonzero vector length and m is the lattice rank.
This is not an exact shortest-vector guarantee. The approximation factor grows with dimension. The algorithm is valuable because it achieves this controlled reduction in polynomial time.
12. Shortest vector and closest vector are different problems
The shortest-vector problem asks for a nonzero lattice vector of minimum norm. The closest-vector problem supplies a target t and asks for a lattice vector nearest to t.
A reduced basis helps with both, but LLL by itself does not exactly solve arbitrary high-dimensional instances. Algorithms such as Babai’s nearest-plane method use a reduced basis to produce an approximate closest vector.
When reading an application, identify which problem is actually being reduced. Short vector, close vector, short relation and reduced basis are related phrases with different outputs.
13. Diophantine approximation as a lattice problem
Suppose we want integers p,q such that qα−p is small. Scale the approximation error by a large factor C and consider a lattice generated by vectors such as
(1, round(Cα)) (0, C).
An integer combination can encode q together with a scaled residue qα−p. A short vector may therefore correspond to a good rational approximation.
The exact embedding depends on the desired bounds. LLL does not magically prove that every short vector solves the original problem; the decoding and inequality checks are part of the application.
This geometric viewpoint complements the continued-fraction guide, where one-dimensional rational approximation has a much more specialised optimal structure.
14. Integer relations
Given real numbers α1,…,αm, an integer relation is a nonzero integer vector z with z1α1+…+zmαm=0 or extremely small. Lattice embeddings can search for small-coefficient candidate relations using finite-precision approximations.
A candidate discovered numerically must be verified at higher precision or symbolically. A small floating residual is evidence, not proof of an exact algebraic relation.
This distinction is especially important when a relation search is used to guess a minimal polynomial. The polynomial must subsequently be checked independently.
15. Polynomial factorisation and LLL
LLL entered computational number theory partly through polynomial factorisation. Modular information can identify possible factors, while a lattice encodes coefficient combinations whose short vectors correspond to small integer factors.
The celebrated Lenstra–Lenstra–Lovász paper gave a polynomial-time algorithm for factoring rational polynomials using lattice basis reduction. The complete method combines modular factorisation, coefficient bounds and lifting; LLL is the reconstruction engine, not the entire factorisation procedure.
This connects directly to finite-field polynomial factorisation: local factors are found modulo primes, then global integer structure must be reconstructed under coefficient bounds.
16. Exact versus floating Gram–Schmidt
The textbook formulas use exact rational coefficients. Exact arithmetic makes decisions reproducible but can create large numerators and denominators.
Floating-point Gram–Schmidt is faster, but an incorrectly rounded coefficient or Lovász comparison can violate the reduction conditions. High-performance libraries use carefully designed floating variants with precision management and exact verification.
For a teaching implementation, exact fractions are often the clearest choice. For large industrial instances, arithmetic strategy becomes part of the algorithm.
17. A minimal educational LLL skeleton
k = 1
while k < m:
size-reduce b[k] against b[k-1],...,b[0]
recompute affected Gram-Schmidt data
if Lovasz condition holds:
k += 1
else:
swap b[k], b[k-1]
recompute affected data
k = max(k-1, 1)A real implementation must also specify exact or approximate arithmetic, rounding of half-integers, representation of basis vectors, overflow behaviour and termination checks.
The output should be accompanied by verification of the reduction inequalities and, where practical, a unimodular transformation matrix U satisfying B_out=B_in U.
18. The unimodular transformation is a certificate
If U is an integer matrix with determinant ±1 and B’=BU, then B and B’ generate the same lattice. Returning U makes lattice preservation independently checkable.
For the two-dimensional worked example, the sequence of a swap and an integer column subtraction can be multiplied into one 2×2 unimodular matrix. Checking BU against the returned basis establishes that no noninteger operation entered the lattice basis.
The determinant check alone is not sufficient to prove two arbitrary bases generate the same lattice, but it is a useful quick invariant when combined with explicit unimodular operations.
19. Norm choice matters
Classical LLL is formulated with the Euclidean norm and its associated inner product. Changing the norm changes the geometry and generally changes the algorithmic theorem.
Applications may care about infinity norm, weighted norms or problem-specific coefficient bounds. One can still use an LLL-reduced Euclidean basis as a tool, but the final application must translate the Euclidean guarantee into the required metric.
This is another example of keeping the model attached to the result: shortest is meaningless without specifying the norm.
20. Common mistakes
1. Assuming the supplied basis vectors are intrinsically meaningful. 2. Using noninteger basis transformations and claiming the same lattice. 3. Treating Gram–Schmidt vectors as lattice vectors. 4. Performing size reduction without the Lovász swap test.
5. Calling an LLL first vector the exact shortest vector. 6. Ignoring the δ parameter. 7. Using floating decisions without a precision strategy. 8. Accepting an integer-relation candidate without independent verification.
21. Practice set
1. Define the lattice generated by (4,1),(1,3). 2. Compute its determinant. 3. Compute μ21 and b2* for the original basis. 4. Check whether the basis is size reduced.
5. With δ=3/4, determine whether the Lovász condition holds. 6. After swapping, compute the new μ21. 7. Perform the required size reduction. 8. Verify the determinant of the reduced basis.
9. Explain why replacing b2 by b2−3b1 preserves the lattice. 10. State the difference between a Gram–Schmidt vector and a lattice vector. 11. Define λ1(L). 12. Does LLL always return a vector of length λ1?
13. What is the role of a lattice embedding in Diophantine approximation? 14. Why does a tiny floating residual not prove an integer relation? 15. What does a unimodular transformation matrix certify? 16. Why must a shortest-vector claim specify a norm?
22. Answers and checks
1. All z1(4,1)+z2(1,3) with integer z1,z2. 2. The absolute determinant is 11. 3. μ21=7/17 and b2*=(−11/17,44/17). 4. Yes, because |7/17|<1/2.
5. It fails, causing a swap. 6. The swapped coefficient is 7/10. 7. Subtract the first vector once, giving (3,−2), after which μ=−3/10. 8. The determinant is −11, so the absolute value is preserved.
9. It is an elementary unimodular column operation with an inverse integer operation. 10. A lattice vector is an integer combination of the original basis; a Gram–Schmidt vector may use rational coefficients and need not lie in the lattice. 11. The Euclidean length of a shortest nonzero lattice vector. 12. No; LLL gives an approximation guarantee.
13. It converts small approximation error and small integer coefficients into the geometric notion of a short vector. 14. Finite precision can make a nonzero expression appear tiny; the candidate needs higher-precision or symbolic checking. 15. That the output basis is obtained from the input by an invertible integer change of basis. 16. Vector length depends on the metric being used.
Sources and further study
A. K. Lenstra, H. W. Lenstra Jr. and L. Lovász, Factoring polynomials with rational coefficients, Mathematische Annalen 261 (1982), introduced the LLL basis-reduction algorithm in this computational context. Henri Cohen, A Course in Computational Algebraic Number Theory, develops lattice reduction throughout computational number theory. The fplll project provides an implementation-oriented reference for modern lattice reduction.
Continue through Batch 04
Return to Guide 14: Fast Integer Multiplication. Continue to Guide 16: Algebraic Number Fields, Ideals, Norms and Computational Arithmetic.