LLL Algorithm
The LLL algorithm reduces a lattice basis to a nearly orthogonal one in polynomial time; its first vector is at most 2^((n-1)/2) times the shortest vector.
Purpose
To perform polynomial-time approximate lattice reduction, widely used in cryptanalysis and number theory.
Mechanism
After Gram-Schmidt orthogonalization, it checks the Lovász condition (|μ_{i,i-1}|≤1/2 and B_i≥(3/4-μ^2)B_{i-1}), swapping and reducing when it fails. The first vector of the output basis has length ≤2^((n-1)/2) * λ_1.
Use cases
- Lattice cryptanalysis
- Polynomial factorization
- CVP approximation