ABSTRACT

First developed in the early 1980s by Lenstra, Lenstra, and Lovasz, 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 i

chapter 1|20 pages

Introduction to Lattices

chapter 2|20 pages

Two-Dimensional Lattices

chapter 3|14 pages

Gram-Schmidt Orthogonalization

chapter 4|32 pages

The LLL Algorithm

chapter 5|16 pages

Deep Insertions

chapter 6|12 pages

Linearly Dependent Vectors

chapter 7|16 pages

The Knapsack Problem

chapter 8|14 pages

Coppersmith’s Algorithm

chapter 9|10 pages

Diophantine Approximation

chapter 10|24 pages

The Fincke-Pohst Algorithm

chapter 11|18 pages

Kannan’s Algorithm

chapter 12|12 pages

Schnorr’s Algorithm

chapter 13|12 pages

NP-Completeness

chapter 14|40 pages

The Hermite Normal Form

chapter 15|38 pages

Polynomial Factorization