Atnaujinkite slapukų nuostatas

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

5.00/5 (2 ratings by Goodreads)
(University of Saskatchewan, Saskatoon, Canada)
Kitos knygos pagal šią temą:
Lattice Basis Reduction: An Introduction to the LLL Algorithm and Its ApplicationsDidesnis paveikslėlis
Kitos knygos pagal šią temą:

DRM apribojimai

  • Kopijuoti:

    neleidžiama

  • Spausdinti:

    neleidžiama

  • El. knygos naudojimas:

    Skaitmeninių teisių valdymas (DRM)
    Leidykla pateikė šią knygą šifruota forma, o tai reiškia, kad norint ją atrakinti ir perskaityti reikia įdiegti nemokamą programinę įrangą. Norint skaityti šią el. knygą, turite susikurti Adobe ID . Daugiau informacijos  čia. El. knygą galima atsisiųsti į 6 įrenginius (vienas vartotojas su tuo pačiu Adobe ID).

    Reikalinga programinė įranga
    Norint skaityti šią el. knygą mobiliajame įrenginyje (telefone ar planšetiniame kompiuteryje), turite įdiegti šią nemokamą programėlę: PocketBook Reader (iOS / Android)

    Norint skaityti šią el. knygą asmeniniame arba „Mac“ kompiuteryje, Jums reikalinga  Adobe Digital Editions “ (tai nemokama programa, specialiai sukurta el. knygoms. Tai nėra tas pats, kas „Adobe Reader“, kurią tikriausiai jau turite savo kompiuteryje.)

    Negalite skaityti šios el. knygos naudodami „Amazon Kindle“.

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.

Recenzijos

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 2012

This 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

List of Figures
xi
Preface xiii
About the Author xvii
1 Introduction to Lattices
1(20)
1.1 Euclidean space Rn
1(4)
1.2 Lattices in Rn
5(8)
1.3 Geometry of numbers
13(2)
1.4 Projects
15(1)
1.5 Exercises
15(6)
2 Two-Dimensional Lattices
21(20)
2.1 The Euclidean algorithm
21(4)
2.2 Two-dimensional lattices
25(6)
2.3 Vallee's analysis of the Gaussian algorithm
31(6)
2.4 Projects
37(1)
2.5 Exercises
38(3)
3 Gram-Schmidt Orthogonalization
41(14)
3.1 The Gram-Schmidt theorem
41(6)
3.2 Complexity of the Gram-Schmidt process
47(2)
3.3 Further results on the Gram-Schmidt process
49(3)
3.4 Projects
52(1)
3.5 Exercises
53(2)
4 The LLL Algorithm
55(32)
4.1 Reduced lattice bases
55(7)
4.2 The original LLL algorithm
62(5)
4.3 Analysis of the LLL algorithm
67(11)
4.4 The closest vector problem
78(2)
4.5 Projects
80(3)
4.6 Exercises
83(4)
5 Deep Insertions
87(16)
5.1 Modifying the exchange condition
87(4)
5.2 Examples of deep insertion
91(3)
5.3 Updating the GSO
94(4)
5.4 Projects
98(1)
5.5 Exercises
99(4)
6 Linearly Dependent Vectors
103(12)
6.1 Embedding dependent vectors
103(3)
6.2 The modified LLL algorithm
106(5)
6.3 Projects
111(1)
6.4 Exercises
112(3)
7 The Knapsack Problem
115(16)
7.1 The subset-sum problem
115(2)
7.2 Knapsack cryptosystems
117(5)
7.3 Projects
122(1)
7.4 Exercises
123(8)
8 Coppersmith's Algorithm
131(14)
8.1 Introduction to the problem
131(2)
8.2 Construction of the matrix
133(4)
8.3 Determinant of the lattice
137(3)
8.4 Application of the LLL algorithm
140(3)
8.5 Projects
143(1)
8.6 Exercises
143(2)
9 Diophantine Approximation
145(10)
9.1 Continued fraction expansions
145(3)
9.2 Simultaneous Diophantine approximation
148(4)
9.3 Projects
152(1)
9.4 Exercises
153(2)
10 The Fincke-Pohst Algorithm
155(24)
10.1 The rational Cholesky decomposition
155(3)
10.2 Diagonalization of quadratic forms
158(1)
10.3 The original Fincke-Pohst algorithm
159(9)
10.4 The FP algorithm with LLL preprocessing
168(7)
10.5 Projects
175(1)
10.6 Exercises
175(4)
11 Kannan's Algorithm
179(18)
11.1 Basic definitions
179(3)
11.2 Results from the geometry of numbers
182(1)
11.3 Kannan's algorithm
183(8)
11.3.1 Procedure COMPUTEBASIS
184(3)
11.3.2 Procedure SHORTESTVECTOR
187(2)
11.3.3 Procedure REDUCEDBASIS
189(2)
11.4 Complexity of Kannan's algorithm
191(2)
11.5 Improvements to Kannan's algorithm
193(1)
11.6 Projects
194(1)
11.7 Exercises
195(2)
12 Schnorr's Algorithm
197(12)
12.1 Basic definitions and theorems
197(5)
12.2 A hierarchy of polynomial-time algorithms
202(4)
12.3 Projects
206(1)
12.4 Exercises
207(2)
13 NP-Completeness
209(12)
13.1 Combinatorial problems for lattices
209(3)
13.2 A brief introduction to NP-completeness
212(1)
13.3 NP-completeness of SVP in the max norm
213(5)
13.4 Projects
218(1)
13.5 Exercises
219(2)
14 The Hermite Normal Form
221(40)
14.1 The row canonical form over a field
222(3)
14.2 The Hermite normal form over the integers
225(4)
14.3 The HNF with lattice basis reduction
229(2)
14.4 Systems of linear Diophantine equations
231(3)
14.5 Using linear algebra to compute the GCD
234(5)
14.6 The HMM algorithm for the GCD
239(11)
14.7 The HMM algorithm for the HNF
250(7)
14.8 Projects
257(1)
14.9 Exercises
258(3)
15 Polynomial Factorization
261(38)
15.1 The Euclidean algorithm for polynomials
262(2)
15.2 Structure theory of finite fields
264(3)
15.3 Distinct-degree decomposition of a polynomial
267(3)
15.4 Equal---degree decomposition of a polynomial
270(5)
15.5 Hensel lifting of polynomial factorizations
275(8)
15.6 Polynomials with integer coefficients
283(7)
15.7 Polynomial factorization using LLL
290(4)
15.8 Projects
294(1)
15.9 Exercises
295(4)
Bibliography 299(12)
Index 311
Murray R. Bremner received a Bachelor of Science from the University of Saskatchewan in 1981, a Master of Computer Science from Concordia University in Montreal in 1984, and a Doctorate in Mathematics from Yale University in 1989. He spent one year as a Postdoctoral Fellow at the Mathematical Sciences Research Institute in Berkeley, and three years as an Assistant Professor in the Department of Mathematics at the University of Toronto. He returned to the Department of Mathematics and Statistics at the University of Saskatchewan in 1993 and was promoted to Professor in 2002. His research interests focus on the application of computational methods to problems in the theory of linear nonassociative algebras, and he has had more than 50 papers published or accepted by refereed journals in this area.
Daugiau apie elektronines knygas Daugiau apie elektronines knygas
Pastovi nuoroda: https://www.kriso.lt/db/97814398070402e.html
Raktažodžiai: