ACAC Seminar Abstract

ACAC Seminar Abstract

ACAC Seminars

ACAC Seminar Abstract

From an LLL-Reduced Basis to Another

Speaker: Ivan Morel
Date, Time: Fri, 07 Nov 2008 15:00

Lattice reduction has important applications in very diverse fields of both mathematics and computer science: cryptology, computer algebra , algorithmic number theory, algorithmic group theory, MIMO communications, computer arithmetic, etc. The LLL algorithm allows one to reduce any given basis of a lattice to a ``good basis'' in polynomial time. The quality of the obtained reduction is directly related to a parameter delta: the higher delta is, the better the reduction. It was suggested by LaMacchia and Cohen that one could gradually reduce a basis by first using a small value of delta, and then increasing the value of delta to reach the maximum quality. We concentrate on the second phase, which is further reducing a basis already reduced with a small value of delta. We show how to take advantage of the knowledge of the lattice obtained from the first reduction to perform the second one.

Back to the top of this page