With many excellent lecture notes on Lenstra, Lenstra, Lovász (LLL) algorithm, from Micciancio, from Regev, from Peikert, from Vaikuntanathan, and with roughly 8 lines of pseudocode, LLL should be super digestable. (right?)
Personally, I struggle with the following questions when I first learned about the algorithm:
- why is LLL a generalization of GCD algorithm in dimension?
- why LLL only approximate instead of compute the exact the shortest vector as the Gauss/Lagrange/GCD can for dimension 1 and 2?
- how to make sense of the Lovász condition?
- why not just sort based on the length of reduced basis (like Lagrange reduction in dimension 2)
- why is slacking factor introduced
In the following whiteboard session, I explained the mysterious-looking Lovasz condition to answer all foregoing questions.