Grid (math)
A grid (engl. Lattice ) in the mathematics is a discrete subset of Euclidean space. Grids are used u. a. in group theory , geometry and approximation issues.
The individual elements of a grid are called grid points or grid vectors.
Lattice in Euclidean space
Let there be linearly independent vectors of the Euclidean vector space . Then you call
a lattice with a base of rank . The matrix formed from the vectors is called the base matrix of . The grid does not define the basis. However, each base of has the same rank . As a subgroup of the additive group of is a free Abelian group of rank .
The limited amount
is called the basic mesh or fundamental mesh of . It spans in a -dimensional sub-vector space
and forms a right- dimensional parallelepiped open to the right . The basis of the lattice is a basis of this vector space.
Through the grating is on an equivalence relation defined as follows:
- .
Each element of is equivalent to exactly one element from the basic mesh. Each equivalence class has exactly one representative in the basic mesh.
A there is no with . Since the interesting thing only takes place in the subspace and this is isomorphic , most authors only consider the case of equality (grid with full rank ).
In this case, the whole can of elementary mesh with a mesh shape parquetted be. However, shapes that are not parallelepiped are also interesting . One then speaks of a fundamental region .
A grid is called whole if the scalar product is an integer for all of them . Is even for everyone , the grid is called straight (straight grids are automatically complete).
Examples:
- The grid in the figure has the basis vectors and . It is neither whole nor straight.
- The lattice with basis vectors and is both whole and straight.
Grid in the complex number plane
By considering the complex number plane as a real vector space, one can speak of lattices in ; they are free Abelian groups of rank 2. They play a central role in the theory of elliptic functions and elliptic curves .
If, more generally, is a natural number, then lattices in real- dimensional space are related to complex Tori and Abelian varieties .
Lattice in Lie groups
A subgroup of a topological group is discrete subgroup , if for every one open environment with
gives.
If a locally compact group is with Haar's measure , then a discrete subgroup is called a lattice if the quotient has finite volume (with respect to Haar's measure).
A grid is called uniform or co-compact if it is compact.
Lattices in Lie groups play an important role in Thurston's geometry program .
Examples
- Let the grid belonging to the basis matrix be of rank 2. Then is .
- Be . Then the basic mesh is of the -dimensional hypercube , and we have e.g. B. .
- The ring of Gaussian numbers is a grid in .
- The ring of the Hurwitz quaternions is a lattice in the oblique body of the quaternions .
- The Leech grid is a special grid in the
Lattice discriminator
One parameter for the classification of grids is the grid discriminant. It is calculated as the volume of the basic mesh.
For grids in Euclidean space with the base matrix , this corresponds to the formula
Has full rank, this can be simplified to the following expression:
As an invariant , the value of the grid discriminant is independent of the chosen basis.
Grid reduction
Lattice reduction is the problem of calculating a basis with certain properties from a given lattice basis, such as a basis with short, almost orthogonal vectors. The LLL algorithm (after Lenstra, Lenstra and Lovász) calculates a so-called LLL-reduced basis in polynomial time, with the help of which one obtains demonstrably short lattice vectors. Indeed, the length of the first vector of an LLL reduced basis is close to the length of the shortest nontrivial lattice vector.
The LLL algorithm has found numerous applications in the cryptanalysis of asymmetric encryption methods such as the RSA cryptosystem and the Merkle-Hellman cryptosystem .
literature
- Gudrun Susanne Wetzel: Lattice basis reduction algorithms and their applications. Shaker Verlag, Aachen 1998, ISBN 3-8265-4543-5 .
- John Horton Conway , Neil Sloane : Sphere packings, lattices and groups. Basic teaching of mathematical sciences 290, Springer, 3rd edition 1999, ISBN 0-387-98585-9 .
- Phong Q. Nguyen, Jacques Stern : The two faces of lattices in cryptology. In: Joseph Silverman (Ed.): Cryptography and lattices (Proceedings CALC 2001), Lecture Notes Computer Science 2146, Springer 2001, pp. 146-180
- Daniele Micciancio, Shafrira Goldwasser : Complexity of lattice problems. A cryptographic perspective. Kluwer Academic & Springer 2002, ISBN 978-0-7923-7688-0 .
- Phong Q. Nguyen, Brigitte Vallée (Eds.): The LLL algorithm. Survey and applications. Information Security and Cryptography series, Springer 2010, ISBN 978-3-642-02294-4 .
Web links
- Noam Elkies : Lattices, linear codes, and invariants. Part I (PDF; 156 kB) Notices AMS 47 (2000), No. 10, pp. 1238-1245 Part II (PDF; 176 kB) Notices AMS 47 (2000), No. 11, pp. 1382-1391
- Hendrik Lenstra : Flags and lattice basis reduction. in Carles Casacuberta et al. (Ed.): European Congress of Mathematics. Barcelona 2000, Vol. I. Birkhäuser 2002, ISBN 978-3-7643-6417-5 , pp. 37-52. Online here (PDF; 165 kB) or there
- Oded Regev: Lattices in Computer Science. Tel-Aviv University, 2004
- Daniele Micciancio: Lecture Notes on lattice algorithms and applications University of California, 2007
- Hendrik Lenstra: Lattices. in Joseph P. Buhler, Peter Stevenhagen (Eds.): Algorithmic Number Theory . MSRI Publications Vol. 44, Cambridge University Press 2008, ISBN 978-0-521-80854-5 , pp. 127-181. Online here or there (PDF; 368 kB)
- Daniel J. Bernstein : Bibliography on Lattice-based public-key cryptography
- Keita Xagawa: Bibliography on Lattice-based Cryptosystems
See also
- Space group
- Bravais grid
- According to Dedekind, special grids are used in the investigation of algebraic integers. See order (algebraic number theory)
- The mathematical term is based on the colloquial use of a grid .