Lattices and LLL Reduction
LLL with Deep Insertions
Allowing a vector to move further than one position, the quality gain, and the loss of the polynomial time guarantee.
Engineering / MathematicsLattices and LLL Reduction2 min readKV-MATH-0548
Standard LLL only ever swaps adjacent vectors. Deep insertion allows a short vector to move directly to a much earlier position, which produces markedly better bases at the cost of the clean complexity bound.
The modification
When the Lovasz condition fails, standard LLL swaps with the immediate predecessor. Deep insertion instead searches backwards for the earliest position where the vector can usefully be inserted, and moves it there.
LLL with deep insertions
- Size reduceAs in standard LLL.
- Search backwardsFind the earliest index at which inserting the current vector satisfies the condition.
- InsertMove the vector to that position, shifting the others.
- RestartResume from the insertion point.
The trade-off
| Aspect | Standard LLL | Deep insertions |
|---|---|---|
| Basis quality | Good | Noticeably better |
| Time bound | Provably polynomial | No polynomial bound known |
| Practical speed | Fast | Usually slower per pass, fewer passes |
| Predictability | High | Input dependent |
Bounding the depth
When it is worth using
Worth it
When the reduced basis feeds a search that scales badly with basis quality — enumeration for shortest vectors, or short vector search.
Not worth it
When any reduced basis suffices, as in growth control for normal forms, where the requirement is merely that entries stay bounded.
Relation to blockwise methods
Deep insertion sits between LLL and blockwise reduction in both cost and quality. Blockwise methods reduce sublattices of fixed dimension exactly, giving a tunable quality parameter with a corresponding exponential cost in the block size.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 2.6.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.