Fascinating!

I gave a talk on Tuesday at the “Gems of Theoretical Computer Science” seminar on the LLL algorithm.

Abstract:

The LLL (Lenstra–Lenstra–Lovász) algorithm is a lattice reduction algorithm that can approximate the shortest vector in a lattice, and has numerous applications (which I’ll cover as time permits), including polynomial-time algorithms to

- factor polynomials over the rationals
- given an approximate root of a low-degree rational polynomial, recover the polynomial
- find integer relations such as $latex pi = 176 tan^{-1}(frac{1}{57}) + 28 tan^{-1}(frac{1}{239}) – 48 tan^{-1}(frac{1}{682}) + 96 tan^{-1}(frac{1}{12943}).$
- solve integer programming in fixed dimension
- break certain cryptosystems.

Notes from the talk are here (TYPO on pg. 3: the example at the bottom should be [[1, .3, 4.2], [0, 1, -.3], [0,0,1]] -> [[1, .3, .2], [0, 1, -.3], [0, 0, 1]]. I didn’t get to cover all topics). Quick summary:

- The goal is to find the shortest vector in a lattice. The LLL…

View original post 240 more words