Type: Seminar

Distribution: World

Expiry: 24 Sep 2009

Auth: billu@daumier.maths.usyd.edu.au

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.