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

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