The LLL lattice basis reduction algorithm


Mental Wilderness

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


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


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s