Bremner Lattice Basis Reduction

An Introduction to the LLL Algorithm and Its Applications
Erscheinungsjahr 2011
ISBN: 978-1-4398-0704-0
Verlag: Taylor & Francis
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 332 Seiten

Reihe: 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.

Zielgruppe

Students and researchers in mathematics and computer science.

Autoren/Hrsg.

Bremner, Murray R.

Fachgebiete

• Mathematik | Informatik EDV | Informatik Programmierung | Softwareentwicklung Algorithmen & Datenstrukturen
• Mathematik | Informatik Mathematik Algebra Zahlentheorie
• Mathematik | Informatik EDV | Informatik Technische Informatik Computersicherheit Datensicherheit, Datenschutz
• Mathematik | Informatik Mathematik Numerik und Wissenschaftliches Rechnen Angewandte Mathematik, Mathematische Modelle

Inhaltsverzeichnis

Introduction to Lattices
Euclidean space Rn
Lattices in Rn
Geometry of numbers
Projects
Exercises

Two-Dimensional Lattices
The Euclidean algorithm
Two-dimensional lattices
Vallée's analysis of the Gaussian algorithm
Projects
Exercises

Gram-Schmidt Orthogonalization
The Gram-Schmidt theorem
Complexity of the Gram-Schmidt process
Further results on the Gram-Schmidt process
Projects
Exercises

The LLL Algorithm
Reduced lattice bases
The original LLL algorithm
Analysis of the LLL algorithm
The closest vector problem
Projects
Exercises

Deep Insertions
Modifying the exchange condition
Examples of deep insertion
Updating the GSO
Projects
Exercises

Linearly Dependent Vectors
Embedding dependent vectors
The modified LLL algorithm
Projects
Exercises

The Knapsack Problem
The subset-sum problem
Knapsack cryptosystems
Projects
Exercises

Coppersmith’s Algorithm
Introduction to the problem
Construction of the matrix
Determinant of the lattice
Application of the LLL algorithm
Projects
Exercises

Diophantine Approximation
Continued fraction expansions
Simultaneous Diophantine approximation
Projects
Exercises

The Fincke-Pohst Algorithm
The rational Cholesky decomposition
Diagonalization of quadratic forms
The original Fincke-Pohst algorithm
The FP algorithm with LLL preprocessing
Projects
Exercises

Kannan’s Algorithm
Basic definitions
Results from the geometry of numbers
Kannan’s algorithm
Complexity of Kannan’s algorithm
Improvements to Kannan’s algorithm
Projects
Exercises

Schnorr’s Algorithm
Basic definitions and theorems
A hierarchy of polynomial-time algorithms
Projects
Exercises

NP-Completeness
Combinatorial problems for lattices
A brief introduction to NP-completeness
NP-completeness of SVP in the max norm
Projects
Exercises

The Hermite Normal Form
The row canonical form over a field
The Hermite normal form over the integers
The HNF with lattice basis reduction
Systems of linear Diophantine equations
Using linear algebra to compute the GCD
The HMM algorithm for the GCD
The HMM algorithm for the HNF
Projects
Exercises

Polynomial Factorization
The Euclidean algorithm for polynomials
Structure theory of finite fields
Distinct-degree decomposition of a polynomial
Equal-degree decomposition of a polynomial
Hensel lifting of polynomial factorizations
Polynomials with integer coefficients
Polynomial factorization using LLL
Projects
Exercises

Über Autor(innen)

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.