1st Edition

Lattice Basis Reduction An Introduction to the LLL Algorithm and Its Applications

By Murray R. Bremner Copyright 2012
    332 Pages 54 B/W Illustrations
    by CRC Press

    First developed in the early 1980s by Lenstra, Lenstra, and Lovász, the LLL algorithm was originally used to provide a polynomial-time algorithm for factoring polynomials with rational coefficients. It very quickly became an essential tool in integer linear programming problems and was later adapted for use in cryptanalysis. This book provides an introduction to the theory and applications of lattice basis reduction and the LLL algorithm. With numerous examples and suggested exercises, the text discusses various applications of lattice basis reduction to cryptography, number theory, polynomial factorization, and matrix canonical forms.

    Introduction to Lattices
    Euclidean space Rn
    Lattices in Rn
    Geometry of numbers
    Projects
    Exercises

    Two-Dimensional Lattices
    The Euclidean algorithm
    Two-dimensional lattices
    Vallée's analysis of the Gaussian algorithm
    Projects
    Exercises

    Gram-Schmidt Orthogonalization
    The Gram-Schmidt theorem
    Complexity of the Gram-Schmidt process
    Further results on the Gram-Schmidt process
    Projects
    Exercises

    The LLL Algorithm
    Reduced lattice bases
    The original LLL algorithm
    Analysis of the LLL algorithm
    The closest vector problem
    Projects
    Exercises

    Deep Insertions
    Modifying the exchange condition
    Examples of deep insertion
    Updating the GSO
    Projects
    Exercises

    Linearly Dependent Vectors
    Embedding dependent vectors
    The modified LLL algorithm
    Projects
    Exercises

    The Knapsack Problem
    The subset-sum problem
    Knapsack cryptosystems
    Projects
    Exercises

    Coppersmith’s Algorithm
    Introduction to the problem
    Construction of the matrix
    Determinant of the lattice
    Application of the LLL algorithm
    Projects
    Exercises

    Diophantine Approximation
    Continued fraction expansions
    Simultaneous Diophantine approximation
    Projects
    Exercises

    The Fincke-Pohst Algorithm
    The rational Cholesky decomposition
    Diagonalization of quadratic forms
    The original Fincke-Pohst algorithm
    The FP algorithm with LLL preprocessing
    Projects
    Exercises

    Kannan’s Algorithm
    Basic definitions
    Results from the geometry of numbers
    Kannan’s algorithm
    Complexity of Kannan’s algorithm
    Improvements to Kannan’s algorithm
    Projects
    Exercises

    Schnorr’s Algorithm
    Basic definitions and theorems
    A hierarchy of polynomial-time algorithms
    Projects
    Exercises

    NP-Completeness
    Combinatorial problems for lattices
    A brief introduction to NP-completeness
    NP-completeness of SVP in the max norm
    Projects
    Exercises

    The Hermite Normal Form
    The row canonical form over a field
    The Hermite normal form over the integers
    The HNF with lattice basis reduction
    Systems of linear Diophantine equations
    Using linear algebra to compute the GCD
    The HMM algorithm for the GCD
    The HMM algorithm for the HNF
    Projects
    Exercises

    Polynomial Factorization
    The Euclidean algorithm for polynomials
    Structure theory of finite fields
    Distinct-degree decomposition of a polynomial
    Equal-degree decomposition of a polynomial
    Hensel lifting of polynomial factorizations
    Polynomials with integer coefficients
    Polynomial factorization using LLL
    Projects
    Exercises

    Biography

    Murray R. Bremner received a Bachelor of Science from the University of Saskatchewan in 1981, a Master of Computer Science from Concordia University in Montreal in 1984, and a Doctorate in Mathematics from Yale University in 1989. He spent one year as a Postdoctoral Fellow at the Mathematical Sciences Research Institute in Berkeley, and three years as an Assistant Professor in the Department of Mathematics at the University of Toronto. He returned to the Department of Mathematics and Statistics at the University of Saskatchewan in 1993 and was promoted to Professor in 2002. His research interests focus on the application of computational methods to problems in the theory of linear nonassociative algebras, and he has had more than 50 papers published or accepted by refereed journals in this area.

    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.
    —M. Zimand, Computing Reviews, March 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. … The writing is clear and quite concise.
    —Zentralblatt MATH 1237