• 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
  • Damien Stehlé
  • (ENS, Lyon)
  • Lattice Point Enumeration Revisited
  • 3pm–4pm, Thursday 18th January, 2007
  • Carlaw 535
  • Lattice point enumeration is the basis of the best known algorithm to solve exactly the shortest vector problem. This is also the time-consuming part of Schnorr's block-based lattice reductions, that are very famous in the cryptography community. This enumeration algorithm, known as Fincke-Pohst algorithm for number theorists and Kannan's algorithm for cryptographers, has a dd/2 +o(d) complexity, where d is the lattice dimension. This upper bound was proved by Hellfrich more than 20 years ago. In this talk, I will show that this analysis is far from being tight, and describe the proof of an improved upper bound.

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