Lattices and LLL Reduction
LLL Reduction Quality and Proof Sketch
Why LLL terminates in polynomial time and what its output guarantees, via the potential function and the Lovasz condition.
Engineering / MathematicsLattices and LLL Reduction2 min readKV-MATH-0547
The LLL guarantees follow from two short arguments: a potential function that forces termination, and a chain of inequalities from the Lovasz condition that bounds the output. Both are worth understanding because they explain the algorithm's tuning parameters.
Termination
Define a potential from the Gram-Schmidt lengths, weighted so that earlier vectors count more. Size reduction leaves it unchanged; each swap multiplies it by a factor strictly less than one.
Why delta must exceed one quarter
The output guarantee
The Lovasz condition, combined with size reduction, gives a bound relating consecutive Gram-Schmidt lengths. Chaining it across the basis bounds the first vector against every orthogonal length, and hence against the shortest vector.
| Quantity | Guarantee |
|---|---|
| First vector length | Within 2^((n-1)/2) of the shortest vector |
| Product of basis lengths | Within 2^(n(n-1)/4) of the determinant |
| Coefficients | All bounded by one half in absolute value |
| Ordering | Gram-Schmidt lengths decrease at a controlled rate |
Practice versus the bound
Stronger reductions
Where LLL is not strong enough, blockwise methods reduce sublattices of fixed dimension exactly and interleave with LLL, trading time for quality. Deep insertions, described in LLL with deep insertions, are a cheaper intermediate option.
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.