10h30: Gradual Sub-Lattice Reduction and Applications. Andy Novocin, LIRMM, Montpellier.

One of the primary uses of lattice reduction algorithms is to approximate short vectors in a lattice. I present a new algorithm which produces approximations of short vectors in certain lattices. It does this by generating a reduced basis of a sub-lattice which is guaranteed to contain all short vectors in the given lattice. This algorithm has a complexity which is less dependent on the size of the input basis vectors and more dependent on the size of the output vectors. To illustrate the usefulness of the new algorithm I will show how it can be used to give new complexity bounds for factoring polynomials in Z[x] and reconstructing algebraic numbers from approximations.