Lattices and LLL Reduction
The LLL Lattice Basis Reduction Algorithm
The LLL algorithm: size reduction interleaved with swaps under the Lovasz condition, and the guarantees it provides in polynomial time.
Engineering / MathematicsLattices and LLL Reduction3 min readKV-MATH-0546
LLL produces a basis that is short and nearly orthogonal, in polynomial time, for a lattice of any rank. It is the single most important algorithm in this collection outside the factoring methods, and it appears in polynomial factorisation, number field computation and normal form control alike.
The two operations
LLL alternates between size reduction, which bounds the Gram-Schmidt coefficients, and swapping adjacent basis vectors when doing so shortens the basis.
The LLL algorithm
- Size reduceReduce the current vector against all preceding ones, rounding each coefficient.
- Test LovaszCheck whether the current vector is long enough relative to its predecessor.
- Swap or advanceIf the condition fails, swap with the predecessor and step back; otherwise advance.
- RepeatContinue until the condition holds at every index.
What it guarantees
The first vector of an LLL-reduced basis is within an exponential factor of the shortest — but the factor depends only on the rank, not on the entries.
Termination and cost
Termination is proved by a potential function built from the Gram-Schmidt lengths, which strictly decreases at every swap and is bounded below. The number of swaps is therefore polynomial.
Why it is everywhere
| Application | What LLL provides |
|---|---|
| Polynomial factoring | Recovers a true factor from a p-adic approximation |
| Normal forms | Controls coefficient growth |
| Polynomial reduction | Finds a small defining polynomial for a number field |
| Dependence detection | Recovers exact relations from numerical approximations |
| Ideal reduction | Finds a small representative in an ideal class |
Frequently Asked Questions
What does the delta parameter do?
Does LLL find the shortest vector?
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 2.6.1. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.