You are here

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

Murray R. Bremner
Publisher: 
Chapman & Hall/CRC
Publication Date: 
2011
Number of Pages: 
316
Format: 
Hardcover
Series: 
Pure and Applied Mathematics
Price: 
89.95
ISBN: 
9781439807026
Category: 
Textbook
We do not plan to review this book.

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