Lattices and LLL Reduction
Finding Short Vectors in Lattices
Enumeration and reduction-based methods for finding short lattice vectors, and where the exact shortest vector is genuinely needed.
Engineering / MathematicsLattices and LLL Reduction2 min readKV-MATH-0553
LLL returns a short vector, not the shortest. When the exact shortest is required, enumeration over a bounded region is the standard approach, and its cost depends sharply on how good the reduced basis is.
Enumeration
Given a bound on the length, enumerate all lattice vectors within it by working through the Gram-Schmidt coordinates from the last downward, at each level bounding the range of the next coefficient.
Fincke-Pohst enumeration
- Reduce firstApply LLL, or a stronger reduction, to the basis.
- Set a boundTake the length of the shortest basis vector as an initial bound.
- RecurseEnumerate coefficients from the highest index down, pruning whenever the partial length exceeds the bound.
- UpdateWhenever a shorter vector is found, tighten the bound.
Cost
| Rank | Feasibility of exact enumeration |
|---|---|
| Up to about 10 | Routine |
| Around 20 to 40 | Feasible with good reduction and pruning |
| Substantially higher | Impractical; rely on approximation |
The closest vector problem
A related question asks for the lattice vector nearest a given target point. Babai's rounding gives a fast approximation by expressing the target in the reduced basis and rounding coefficients; enumeration gives the exact answer at similar cost to the shortest vector search.
Where exactness matters
Ideal reduction
An approximately short vector suffices — the goal is a small representative, not the smallest.
Polynomial factorisation
The sought vector is known to be much shorter than all others, so LLL alone finds it.
Form reduction in rank two
The exact shortest vector is wanted, but rank two admits a direct algorithm — see form reduction.
Number field sieve polynomial selection
Exactness is not required; quality of the search is what matters.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 2.7.3. 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.