Bremner, Murray R. Lattice basis reduction. An introduction to the LLL algorithm and its applications. (English) Zbl 1237.68007 Pure and Applied Mathematics (Boca Raton) 300. Boca Raton, FL: CRC Press (ISBN 978-1-4398-0702-6/hbk; 978-1-4398-0704-0/ebook). xvii, 316 p. (2012). This text is meant as a survey of lattice basis reduction at a level suitable for students and interested researchers with a solid background in undergraduate linear algebra. A “lattice” is a linear combination over \(\mathbb{Z}\) of linearly independent vectors over \(\mathbb{R}^n\). In many problems a basis for the lattice is known but a “reduced basis” with shorter vectors is more desirable. Applications include polynomial factorization and cryptography. One of the best known algorithms for computing a reduced lattice basis is the Lenstra-Lenstra-Lovász algorithm (LLL), an algorithm whose time is polynomial in the dimension of the inputs.The first three chapters of the text provide background; two important topics reviewed carefully are an algorithm by Gauss to reduce a lattice basis in two dimensions, and Gram-Schmidt orthogonalization. Gauss’ algorithm is compared to the Euclidean algorithm to compute the gcd of two integers, while Gram-Schmidt orthogonalization is considered somewhat rather deeply: the author also discusses the \(k\)th Gram matrices and their determinants, which are used later to prove termination of LLL.The author describes and analyzes LLL in Chapter 4. This chapter is short, but detailed and thorough in its consideration of the theory. Subsequent chapters consider variants of LLL. The basic algorithm, for example, exchanges only adjacent rows of a matrix; the text describes a “deep-insertion” variant that exchanges non-adjacent rows.The text contains a wealth of additional information; at this point, the reader has completed Chapter 6, and is less than halfway through the 15 chapters of the book! Many of the subsequent chapters cover applications such as Knapsack algorithms, Coppersmith’s algorithm, Diophantine approximation. One chapter addresses the NP-completeness of finding a shortest vector. Naturally, polynomial factorization makes an appearance.The writing is clear and quite concise. Maple code appears for some of the algorithms. In addition to exercises, the author provides a number of projects for students to explore; besides implementing algorithms, topics for seminars are provided, as well as explorations and experiments. The text, while self-contained, provides an extensive bibliography, and directs the reader frequently to original sources, as well as to papers and textbooks that provide additional information. Reviewer: John Perry (Hattiesburg) Cited in 1 ReviewCited in 19 Documents MSC: 68-02 Research exposition (monographs, survey articles) pertaining to computer science 68W30 Symbolic computation and algebraic computation 13P05 Polynomials, factorization in commutative rings 11Y16 Number-theoretic algorithms; complexity 11H06 Lattices and convex bodies (number-theoretic aspects) Keywords:lattice basis reduction; LLL algorithm; polynomial factorization; cryptography Software:Maple × Cite Format Result Cite Review PDF Full Text: Link