The floating-point LLL algorithm
Dr. Damien Stehle (University of Sydney)
MSI Advanced ComputationDATE: 2006-09-11
TIME: 11:00:00 - 12:00:00
LOCATION: G 35 (John Dedman building)
CONTACT: JavaScript must be enabled to display this email address.
ABSTRACT:
The aim of the algorithm of Lenstra, Lenstra and Lovasz (LLL) is to reduce bases of euclidean lattices, i.e., dicrete subgroups of a Euclidean space. Since its introduction, it proved central in many areas, including algorithmic number theory, public-key cryptanalysis and, more recently, computer arithmetic. Given as input a basis of a lattice in Z^d with integer vectors of norms smaller than B, the LLL algorithm computes a so-called LLL-reduced basis in time O(d^6 log^3 B), by using arithmetic operations on integers of lengths O(d log B). This running-time is too high to tackle lattice bases of large dimension or with large entries. Instead of the text-book LLL, one uses in practice floating-point variants, where the integer/rational arithmetic within the Gram-Schmidt orthogonalization (central and cost-dominant in LLL) is replaced by floating-point arithmetic with small mantissas.
In this talk, after some reminders on the LLL algorithm, I will describe the L2 algorithm. It is a natural floating-point variant of the LLL algorithm, that always outputs LLL-reduced bases in time O(d^5 (d+logB) logB). The code derived from this algorithm is the fastest available so far.
BIO:
