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

Introduction to Lattices
Euclidean space Rⁿ
Lattices in Rⁿ
Geometry of numbers
Projects
Exercises

Two-Dimensional Lattices
The Euclidean algorithm
Two-dimensional lattices
Vallee'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