Olivetti Club

Dylan PeiferCornell University
The LLL Algorithm

Tuesday, October 31, 2017 - 4:30pm
Malott 406

The Lenstra-Lenstra-Lovász basis reduction algorithm is an algorithm for finding small vectors in an integer lattice. While originally introduced in 1982 to factor polynomials over the rationals, the algorithm can be applied to many situations that can be expressed as finding minimal elements of lattices. In this talk we will develop the algorithm, starting from orthogonalization and the low-dimensional algorithms of Euclid, Gauss, and Lagrange, and see several applications, including to polynomial factorization.

Refreshments will be served in the lounge at 4:00 PM.