plll  1.0
Introduction

All lattices considered are integral lattices in , given by a generating system . Note that can be in any relation to since we do not assume that forms a basis of the lattice.

# Introduction to lattice reduction

Let be linearly independent vectors in , where . Then the lattice of rank generated by is the subgroup Any subgroup of of this form is called a lattice, and the corresponding number its rank. The dimension of the ambient space is called the dimension of the lattice, and the vectors are called a basis of the lattice. In case the lattice is contained in , we say that the lattice is integral.

An example for a two-dimensional lattice of rank 2 is given in the following picture: A two-dimensional lattice

This lattice can be given implicitly as The large dot in the center represents the zero vector. This lattice can be generated in different ways. A simple basis is which is shown in the following picture: A simple basis of the above lattice

But also other bases are possible. In fact, as soon as , there are infinitely many bases for every lattice of rank . The following picture shows a more complicated basis of the same lattice as before: A more complicated basis of the above lattice

The aim of lattice reduction is to start with a (complicated) basis and try to find a better, "nicer" basis. One goal is to find as short as possible basis vectors. The vectors in the first basis are a relatively good choice, but not optimal: a better basis would be as demonstrated by the following picture: An 'optimal' basis for the above lattice

Note that both in this basis as in the first one, a shortest non-zero vector is part of the basis, namely and also in the last basis: their Euclidean length is .

Since finding such shortest vectors is hard (for ), as M. Ajtai showed in 1998 , most lattice basis reduction algorithms try to find good approximations of a shortest vector, where the approximation quality usually increases with running time, but is often far away from optimal. The first polynomial time lattice basis reduction algorithm, 1982's celebrated LLL algorithm , has a exponential approximation bound (which Schnorr showed is optimal). For some problems, such bounds already suffice, while for others, better approximations are needed. Since 1982, many new algorithms have been designed to find better approximations. The plll library tries to make many of them available.

For a more detailed description of lattice reduction algorithms, see Lattice Reduction.

# Usage

A simple example of how to use the plll library is the following:

#include <plll.hpp>
#include <iostream>
int main()
{
std::cin >> A;
lr.setLattice(A);
lr.lll();
std::cout << lr.getLattice() << "\n";
}

It applies LLL with standard parameters (that is, reduction parameter 0.99) to a basis read from standard input, and writes the resulting basis to standard output.

A more thorough discussion of this example can be found in A simple example. More examples can be found in Examples. For a detailed explanation of the interface of the plll::LatticeReduction class, see its description. For a detailed description of how to work with matrices, including how to input and output them, see Matrices and Vectors. To know more about how to work with the arithmetic functions provided by plll, see Arithmetic Contexts. And for a detailed description of the supported lattice reduction algorithms, see Supported algorithms.

All code except the memory allocator was written by Felix Fontein.

All algorithms implemented in this library are taken from published papes. Some were slightly modified. See Supported algorithms for descriptions of the algorithms, attributions to their inventors and references to the relevant publications.

The memory allocator in the files plll/src/utilities/dlalloc.c and plll/src/utilities/dlalloc.h is Doug Lea's dlmalloc, which was released to the public domain. For more information, check out plll/src/utilities/dlalloc.c or ftp://gee.cs.oswego.edu/pub/misc/malloc.c.