2 min read
Lovász Condition in LLL Explained

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 nn 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 δ\delta slacking factor introduced

In the following whiteboard session, I explained the mysterious-looking Lovasz condition to answer all foregoing questions.