## Lattice Basis Reduction: An Introduction to the LLL Algorithm and Its ApplicationsFirst 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. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Other editions - View all

### Common terms and phrases

algebra apply the LLL basis vectors basis x1 Cholesky decomposition closest vector problem coefficients column completes the proof components Coppersmith deep insertion deﬁne Deﬁnition deg(f det(L diagonal entries equation Euclidean algorithm Example exchange Exercise Figure Fincke-Pohst algorithm ﬁnd finite fields ﬁrst G Z[x Gaussian algorithm gives Gram determinants Gram matrix Gram-Schmidt orthogonalization greatest common divisor hence Hermite normal form Hermite-reduced inequality input integral linear combination irreducible factors iteration Kannan’s algorithm lattice basis reduction lattice vector Lemma linearly independent LLL algorithm main loop Maple code MLLL modulo multiple n-dimensional lattice NP-completeness nullspace Number Theory obtain original LLL algorithm Output polynomial f present a seminar procedure Project real number reduced basis reduction parameter report and present row operations satisﬁes Schnorr seminar talk shortest nonzero vector shortest vector spanned squared length squarefree Step Theorem upper bound vectors x1 Write a report