Lattices and LLL Reduction
LLL for Linearly Dependent Generating Sets
Extending LLL to generating sets that are not independent, and using the resulting zero vectors to extract relations.
Engineering / MathematicsLattices and LLL Reduction2 min readKV-MATH-0550
Standard LLL assumes an independent basis. Generating sets in practice are frequently dependent, and the extension that handles them turns the dependency into useful output rather than an error.
What goes wrong
The modification
When a Gram-Schmidt vector vanishes, the corresponding basis vector lies in the span of its predecessors. Size reduction against those predecessors then reduces it to the zero vector, which is moved to the end and dropped.
LLL with dependent input
- DetectIdentify a vanishing Gram-Schmidt vector.
- Size reduce fullyReduce the offending vector against all predecessors; it becomes zero.
- RecordThe coefficients used constitute a dependency relation.
- RemoveMove the zero vector to the end and reduce the working rank.
- ContinueResume reduction on the remaining vectors.
Two outputs
| Output | Meaning |
|---|---|
| Surviving non-zero vectors | A reduced basis of the lattice generated by the input |
| Recorded relations | A generating set for the integer kernel |
| Transformation matrix | Expresses the output in terms of the input; unimodular |
Numerical caution
Applications
Dependent-input LLL is the workhorse behind integer kernel computation, and it also underlies dependence detection, where a deliberately over-determined generating set is constructed so that the relations found reveal the sought dependency.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 2.6.4. 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.