Introduction to Lattices
Lattice theory is a subalgebra (a subset of algebra) in abstract algebra that describes how collections of objects depict algebraic structure. Lattices can also be described as combinatorial objects used as a tool to solve complex mathematical and computer science problems. It is thought by some to be a precursor to category theory.
-
What a Lattice Looks Like
-
Professor Daniele Micciancio of the University of California at San Diego states that lattices can be thought of as all of the points of intersection on an N-dimensional infinite grid. A simple representation of a 2-D lattice can be modeled by taking a sheet of graph paper, dotting each intersection, and specifying the lattice.
How to Specify a Lattice
-
Subash Khot states that in order to specify a lattice, you need N linearly independent vectors called a basis. According to Micciancio, each point on the lattice can be calculated by an integer linear combination of the basis vectors.
Fundamental Problems
-
The two fundamental problems in lattice theory are the shortest vector problem and the closest vector problem. Micciancio defines a closest vector problem as, "Given a lattice basis B and a target point T (not necessarily in the lattice), find a lattice point closest to T;" while a shortest vector problem is defined as, "Given a lattice basis B, find a shortest nonzero lattice vector in the lattice."
Use in Cryptography
-
Lattices are used in combinatorics to solve problems in crypotology (combinatorics is a branch of mathematics that deals with the study of discrete objects). Micciancio notes that lattices are useful in both breaking cryptosystems and designing them.
Special Types
-
Special types include unimodular lattices (a lattice of discriminant 1 or '1), Leech lattices (n 24-dimensional Euclidean space) and Niemeier lattice. A Niemeier lattice is an even, unimodular lattice of rank 24.
-
Related Searches
References
- Photo Credit Image by Flickr.com, courtesy of David Goehring
