Lattice Basis Reduction: An Introduction to the LLL Algorithm and Its Applications (Chapman & Hall Pure and Applied Mathematics)

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. Lattice Basis Reduction: An Introduction To The Lll Algorithm And Its Applications......Page 2 Pure And Applied Mathematics......Page 3 Monographs And Textbooks Inpure And Applied Mathematics......Page 5 Lattice Basis Reduction: An Introduction To The Lll Algorithm And Its Applications......Page 6 Contents......Page 8 List Of Figures......Page 12 Preface......Page 14 About The Author......Page 18 1.1 Euclidean space Rn......Page 19 1.2 Lattices in Rn......Page 23 1.3 Geometry of numbers......Page 31 1.5 Exercises......Page 33 2.1 The Euclidean algorithm......Page 39 2.2 Two-dimensional lattices......Page 43 2.3 Vallee’s analysis of the Gaussian algorithm......Page 49 2.4 Projects......Page 55 2.5 Exercises......Page 56 3.1 The Gram-Schmidt theorem......Page 59 3.2 Complexity of the Gram-Schmidt process......Page 65 3.3 Further results on the Gram-Schmidt process......Page 67 3.4 Projects......Page 70 3.5 Exercises......Page 71 4.1 Reduced lattice bases......Page 73 4.2 The original LLL algorithm......Page 80 4.3 Analysis of the LLL algorithm......Page 85 4.4 The closest vector problem......Page 96 4.5 Projects......Page 98 4.6 Exercises......Page 101 5.1 Modifying the exchange condition......Page 105 5.2 Examples of deep insertion......Page 109 5.3 Updating the GSO......Page 112 5.4 Projects......Page 116 5.5 Exercises......Page 117 6.1 Embedding dependent vectors......Page 121 6.2 The modified LLL algorithm......Page 124 6.3 Projects......Page 129 6.4 Exercises......Page 130 7.1 The subset-sum problem......Page 133 7.2 Knapsack cryptosystems......Page 135 7.3 Projects......Page 140 7.4 Exercises......Page 141 8.1 Introduction to the problem......Page 149 8.2 Construction of the matrix......Page 151 8.3 Determinant of the lattice......Page 155 8.4 Application of the LLL algorithm......Page 158 8.6 Exercises......Page 161 9.1 Continued fraction expansions......Page 163 9.2 Simultaneous Diophantine approximation......Page 166 9.3 Projects......Page 170 9.4 Exercises......Page 171 10.1 The rational Cholesky decomposition......Page 173 10.2 Diagonalization of quadratic forms......Page 176 10.3 The original Fincke-Pohst algorithm......Page 177 10.4 The FP algorithm with LLL preprocessing......Page 186 10.6 Exercises......Page 193 11.1 Basic definitions......Page 197 11.2 Results from the geometry of numbers......Page 200 11.3 Kannan’s algorithm......Page 201 11.3.1 Procedure COMPUTEBASIS......Page 202 11.3.2 Procedure SHORTESTVECTOR......Page 205 11.3.3 Procedure REDUCEDBASIS......Page 207 11.4 Complexity of Kannan’s algorithm......Page 209 11.5 Improvements to Kannan’s algorithm......Page 211 11.6 Projects......Page 212 11.7 Exercises......Page 213 12.1 Basic definitions and theorems......Page 215 12.2 A hierarchy of polynomial-time algorithms......Page 220 12.3 Projects......Page 224 12.4 Exercises......Page 225 13.1 Combinatorial problems for lattices......Page 227 13.2 A brief introduction to NP-completeness......Page 230 13.3 NP-completeness of SVP in the max norm......Page 231 13.4 Projects......Page 236 13.5 Exercises......Page 237 CONTENTS......Page 239 14.1 The row canonical form over a field......Page 240 14.2 The Hermite normal form over the integers......Page 243 14.3 The HNF with lattice basis reduction......Page 247 14.4 Systems of linear Diophantine equations......Page 249 14.5 Using linear algebra to compute the GCD......Page 252 14.6 The HMM algorithm for the GCD......Page 257 14.7 The HMM algorithm for the HNF......Page 268 14.8 Projects......Page 275 14.9 Exercises......Page 276 CONTENTS......Page 279 15.1 The Euclidean algorithm for polynomials......Page 280 15.2 Structure theory of finite fields......Page 282 15.3 Distinct-degree decomposition of a polynomial......Page 285 15.4 Equal-degree decomposition of a polynomial......Page 288 15.5 Hensel lifting of polynomial factorizations......Page 293 15.6 Polynomials with integer coefficients......Page 301 15.7 Polynomial factorization using LLL......Page 308 15.8 Projects......Page 312 15.9 Exercises......Page 313 Bibliography......Page 317 Index......Page 329 1. Introduction To Lattices -- 2. Two-dimensional Lattices -- 3. Gram-schmidt Orthogonalization -- 4. The Lll Algorithm -- 5. Deep Insertions -- 6. Linearly Dependent Vectors -- 7. The Knapsack Problem -- 8. Coppersmith's Algorithm -- 9. Diophantine Approximation -- 10. The Fincke-pohst Algorithm -- 11. Kannan's Algorithm -- 12. Schnorr's Algorithm -- 13. Np-completeness -- 14. The Hermite Normal Form -- 15. Polynomial Factorization. Murray R. Bremner. Includes Bibliographical References (p. 299-309) And Index. 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 2012This 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 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