• About
  • Members
  • Seminar
  • Visitors
  • Publications
  • Conferences
  • Magma
  • Login
Computational Algebra Group
Computational Algebra Seminar
  • 2000-2004
  • 2005-2009
  • 2010-2014
  • 2015
  • 2016
  • 2017
  • 2018
  • 2024
  • 2025
  • Ivan Morel
  • (ENS, Lyon)
  • H-LLL: Householder inside LLL
  • 3pm–4pm, Thursday 24th September, 2009
  • Carlaw 535
  • 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.

The Computational Algebra Group is a research group within the School of Mathematics and Statistics, University of Sydney.
Copyright © 2010-2025 Computational Algebra Group.