Polynomial time, exponential approximation, and it is enough
LLL takes any basis of a lattice and returns one that is size-reduced and satisfies the Lovász condition, in time polynomial in the dimension and the input size. The first vector of the output is guaranteed within a factor of 2(n−1)/2 of the shortest — a weak-sounding bound that is comprehensively beaten in practice, and that turned polynomial factorisation, integer relation detection and simultaneous Diophantine approximation from research problems into library calls.
Learning objectives
- State the two LLL reduction conditions and their geometric meaning.
- Trace the swap-and-reduce loop and explain what each phase achieves.
- Explain the potential function argument for polynomial termination.
- State the quality guarantees and contrast them with observed behaviour.
- Choose between standard LLL, deep insertions and BKZ.
Section 01The reduction conditions
A basis is LLL-reduced for a parameter δ with 1/4 < δ < 1 when both conditions hold.
No basis vector has a large component along an earlier one. Achieved by subtracting the nearest integer multiple — a unimodular operation, so the lattice is unchanged.
‖b*i‖² ≥ (δ − μi,i−1²) ‖b*i−1‖². The orthogonal lengths may not decrease too quickly; where they do, swapping the two vectors improves the basis.
The standard choice δ = 3/4 is what appears in the original analysis; δ close to 1 gives better bases at greater cost, and the running time degrades as δ approaches 1.
Section 02The algorithm
- Compute the Gram–Schmidt data μij and ‖b*i‖2. Set k ← 2.
- Size-reduce bk against bk−1: subtract ⌊μk,k−1⌉ bk−1. Nearest integer, hence |μ| ≤ 1/2.
- If the Lovász condition fails at index k: swap bk and bk−1, update the Gram–Schmidt data, set k ← max(2, k−1) and return to step 2. The only step that can move backwards.
- Otherwise size-reduce bk against bk−2, …, b1 in that order.
- Set k ← k + 1. If k ≤ n return to step 2.
- Return the reduced basis.
Define the potential D = ∏i di, where di is the determinant of the first i basis vectors. D is a positive integer for an integer lattice, so it cannot decrease forever. Size reduction leaves D unchanged; every swap multiplies it by a factor of at most δ < 1. Hence the number of swaps is bounded by log1/δ of the initial potential — polynomial in the input size. This argument, not the geometry, is the heart of the result.
Section 03Guarantees versus practice
For a δ-reduced basis with δ = 3/4:
The proven bound is exponential; observed behaviour on random lattices is far better, with the first vector typically within a small polynomial factor. Two consequences follow: LLL is far more useful than its bound suggests, and cryptographic security estimates must be based on observed behaviour, not on the worst-case guarantee.
Section 04Variants
| Variant | Change | Effect |
|---|---|---|
| Deep insertion | On failure, insert bk at the best earlier position rather than swapping with its immediate predecessor | Noticeably better bases; no polynomial time bound, but usually fast in practice |
| Floating-point LLL | Gram–Schmidt in floating point with exact re-verification near thresholds | The standard production choice; large constant-factor speedup |
| Integral LLL | All arithmetic in ℤ using scaled μ coefficients | Fully exact, slower; the reference implementation for verification |
| Linearly dependent input | Handles generating sets that are not bases, extracting zero vectors | Essential for integer kernel computation |
| BKZ | Block-wise reduction with exhaustive search inside each block | Much better bases; cost rises sharply with block size — the standard tool for cryptanalytic estimates |
LLL returns a short vector, not the shortest. Algorithms whose correctness depends on having the true minimum — some CM constructions and exhaustive enumeration steps — require a genuine SVP solver such as Fincke–Pohst enumeration, with LLL used only as preprocessing.
ReferenceFrequently asked questions
What does the parameter delta actually control?
How aggressively the algorithm insists that orthogonal lengths not decrease. Larger delta means stricter conditions, better bases and more swaps. At delta = 1 the running time is no longer provably polynomial, so implementations use values slightly below 1 when quality matters.
Is LLL still competitive?
As a fast preprocessing step, yes — universally. As the final reduction where quality matters, BKZ with a moderate block size has replaced it. The standard pipeline runs LLL first, then BKZ on the already-reduced basis.
Can LLL handle a generating set that is not a basis?
Yes, with the dependent-vector variant, which detects linear dependencies and produces zero vectors that are then removed. This is exactly how integer kernels are computed, so the variant is not a curiosity but a working tool.
NavigateContinue in this stream
Curated next steps from this page. The site also surfaces algorithmically related reading below.
ProvenanceSources and further reading
This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.