Atjaunināt sīkdatņu piekrišanu

E-grāmata: Lattice Basis Reduction: An Introduction to the LLL Algorithm and Its Applications

5.00/5 (2 ratings by Goodreads)
(University of Saskatchewan, Saskatoon, Canada)
Citas grāmatas par šo tēmu:
  • Formāts - PDF+DRM
  • Cena: 71,37 €*
  • * ši ir gala cena, t.i., netiek piemērotas nekādas papildus atlaides
  • Ielikt grozā
  • Pievienot vēlmju sarakstam
  • Šī e-grāmata paredzēta tikai personīgai lietošanai. E-grāmatas nav iespējams atgriezt un nauda par iegādātajām e-grāmatām netiek atmaksāta.
Lattice Basis Reduction: An Introduction to the LLL Algorithm and Its ApplicationsPalielināt
Citas grāmatas par šo tēmu:

DRM restrictions

  • Kopēšana (kopēt/ievietot):

    nav atļauts

  • Drukāšana:

    nav atļauts

  • Lietošana:

    Digitālo tiesību pārvaldība (Digital Rights Management (DRM))
    Izdevējs ir piegādājis šo grāmatu šifrētā veidā, kas nozīmē, ka jums ir jāinstalē bezmaksas programmatūra, lai to atbloķētu un lasītu. Lai lasītu šo e-grāmatu, jums ir jāizveido Adobe ID. Vairāk informācijas šeit. E-grāmatu var lasīt un lejupielādēt līdz 6 ierīcēm (vienam lietotājam ar vienu un to pašu Adobe ID).

    Nepieciešamā programmatūra
    Lai lasītu šo e-grāmatu mobilajā ierīcē (tālrunī vai planšetdatorā), jums būs jāinstalē šī bezmaksas lietotne: PocketBook Reader (iOS / Android)

    Lai lejupielādētu un lasītu šo e-grāmatu datorā vai Mac datorā, jums ir nepieciešamid Adobe Digital Editions (šī ir bezmaksas lietotne, kas īpaši izstrādāta e-grāmatām. Tā nav tas pats, kas Adobe Reader, kas, iespējams, jau ir jūsu datorā.)

    Jūs nevarat lasīt šo e-grāmatu, izmantojot 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.

Recenzijas

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.
Biežāk uzdotie jautājumi par e-grāmatām Biežāk uzdotie jautājumi par e-grāmatām
Permanent link: https://www.kriso.lv/db/97814398070402e.html
Keywords: