Lattices and LLL Reduction
The Gram-Schmidt Orthogonalisation Procedure
Gram-Schmidt orthogonalisation, the coefficients that drive lattice reduction, and why the orthogonal vectors themselves are not lattice vectors.
Engineering / MathematicsLattices and LLL Reduction2 min readKV-MATH-0544
Gram-Schmidt supplies the measurements that lattice reduction acts on. It is not itself a reduction — the vectors it produces are generally not in the lattice — but the coefficients it computes are exactly what LLL manipulates.
The procedure
Each vector has its projections onto the preceding orthogonal vectors subtracted, leaving the component orthogonal to everything before it.
What the coefficients mean
- Size of mu
- Measures how far the basis is from orthogonal. Coefficients larger than one half indicate a vector that can be shortened by subtracting a multiple of an earlier one.
- Length of the orthogonal vectors
- A decreasing sequence indicates a well-ordered basis. Sharp drops signal that a swap will help.
- Product of orthogonal lengths
- Equals the lattice determinant, independent of the basis.
Size reduction
Size reduction of one pair
- Compute the coefficientTake mu for the pair of indices.
- RoundRound to the nearest integer.
- SubtractSubtract that integer multiple of the earlier vector.
- UpdateRecompute the affected coefficients.
Numerical considerations
| Approach | Cost | Reliability |
|---|---|---|
| Floating point | Fast | Can fail silently on skewed input |
| Exact rational | Slow; denominators grow | Correct |
| Integral (scaled) | Moderate | Correct — see integral LLL |
| Floating point with verification | Fast plus a check | Correct if the check is exact |
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 2.5.2. 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.