This is an introductory text on lattice algorithms and their applications. A lattice consists of all vectors that can be expressed as an integer combination of a given fixed set of vectors in Rn (the vectors in the set form the basis of the lattice). One can envision a lattice as the points in a grid, where the basic cell of the grid is given by the vectors in the basis. A lattice has in fact infinitely many bases because any transformation of a given basis via a unimodular matrix with integer elements produces another basis.
Lattice basis reduction is the following problem: given a basis, find another basis consisting of shorter vectors. This is a fundamental problem in the geometry of numbers and has several important applications. The famous LLL algorithm--of Lenstra, Lenstra, and Lovasz--is a polynomial-time algorithm for lattice basis reduction and occupies a prominent place in the book. The LLL algorithm is in fact mentioned in the subtitle of the book, but this may be misleading because the book is much broader, as can be seen from the titles of the chapters: “Introduction to Lattices,” “Two-Dimensional Lattices,” “Gram-Schmidt Orthogonalization,” “The LLL Algorithm,” “Deep Insertions,” “Linearly Dependent Vectors,” “The Knapsack Problem,” “Coppersmith’s Algorithm,” “Diophantine Approximation,” “The Fincke-Pohst Algorithm,” “Kannan’s Algorithm,” “Schnorr’s Algorithm,” “NP-Completeness,” “The Hermite Normal Form,” and “Polynomial Factorization.”
The book is written for a general audience and only standard undergraduate-level background in linear algebra is assumed. In this respect, it complements several research monographs on the geometry of numbers and on algebraic computational theory. The style is that of a collection of lecture notes: the exposition is concise (the flip side being that this style does not convey very well the intuitive ideas on which the algorithms and the proofs are based), and the more advanced results are given without proof. The algorithms are given in pseudocode and illustrated by examples that are fully worked-out. Each chapter is accompanied by an exercise section and a list of possible projects. The exercises are either of a computational nature (“determine a basis such that...”) or a theoretical nature (“prove that...”).
To conclude, the book succeeds in making accessible to nonspecialists the area of lattice algorithms, which is remarkable because some of the most important results in the field are fairly recent.
