Computational Algebra Seminar: Morel -- H-LLL: Householder inside LLL

Speaker: Ivan Morel
Title: H-LLL: Householder inside LLL
Time & Place: 3-4pm, Thursday 24 Sept,  Carslaw 535.

Abstract:
Lattice reduction is a fundamental tool in diverse fields of
computational mathematics and computer science, like cryptography and
algorithmic number theory... The LLL algorithm allows one to reduce a
basis of a given lattice into a ’good’ basis in time polynomial in
both the dimension and the size of the entries. However, the size of
the integers that arise during the execution of the algorithm make it
unusable in practice for large inputs. We describe here a new proven
LLL-type algorithm, H-LLL, that relies on Householder transformations
to compute the QR decomposition of the basis. I will present the
advantages and drawbacks of this over already existing methods.