- Gitter (Mathematik)
-
In der Mathematik sind Gitter in gewissem Sinne regelmäßige Mengen. Sie finden u. a. Anwendung in der Gruppentheorie, der Geometrie und bei Approximationsfragestellungen.
Die einzelnen Elemente eines Gitters heißen Gitterpunkte oder Gittervektoren.
Inhaltsverzeichnis
Gitter im euklidischen Raum
Es seien
linear unabhängige Vektoren des euklidischen Vektorraums
. Dann nennt man
ein Gitter mit Basis
vom Rang m. Die aus den Vektoren
gebildete Matrix
heißt Basismatrix von Γ. Die Basis ist durch das Gitter nicht festgelegt. Jede Basis von Γ hat jedoch denselben Rang m. Als Untergruppe der additiven Gruppe von
ist Γ eine freie abelsche Gruppe vom Rang m.
Die beschränkte Menge
heißt Grundmasche oder Fundamentalmasche von Γ. Sie spannt im
einen m-dimensionalen Unterraum
auf und bildet darin ein rechtsoffenes m-dimensionales Parallelepiped.
Durch das Gitter Γ wird auf
eine Äquivalenzrelation wie folgt definiert:
.
Jedes Element von R ist zu genau einem Element aus der Grundmasche äquivalent. Jede Äquivalenzklasse hat also genau einen Repräsentanten in der Grundmasche.
Zu einem
gibt es kein
mit
. Da sich das Interessante also nur im Unterraum R abspielt und dieser isomorph zu
ist, betrachten die meisten Autoren nur den Fall der Gleichheit m = n (Gitter mit vollem Rang).
In diesem Fall kann der ganze
mit Maschen der Form der Grundmasche parkettiert werden. Jedoch sind auch Formen interessant, die kein Parallelepiped sind. Man spricht dann von einer Fundamentalregion.
Ein Gitter Γ heißt ganz, falls für alle
das Skalarprodukt
eine ganze Zahl ist. Ist darüber hinaus
, so nennt man das Gitter Γ gerade.
Beispiele:
- Das Gitter in der Abbildung hat die Basisvektoren
und
. Es ist weder ganz noch gerade.
- Das Gitter mit Basisvektoren b1 = (3,1) und b2 = (1, − 1) ist sowohl ganz als auch gerade.
Gitter in der komplexen Zahlenebene
Indem man die komplexe Zahlenebene
als reellen Vektorraum auffasst, kann man von Gittern in
sprechen; sie sind freie abelsche Gruppen vom Rang 2. Sie spielen eine zentrale Rolle in der Theorie der elliptischen Funktionen und elliptischen Kurven.
Ist allgemeiner g eine natürliche Zahl, so stehen Gitter im reell 2g-dimensionalen Raum
in Beziehung zu komplexen Tori und abelschen Varietäten.
Beispiele
- Sei Γ das zur Basismatrix
gehörige Gitter vom Rang 2. Dann ist
.
- Sei
. Dann ist die Grundmasche von Γ der n-dimensionale Hyperwürfel
, und es gilt z. B.
.
- Der Ring der gaußschen Zahlen
ist ein Gitter in
.
- Der Ring der Hurwitzquaternionen ist ein Gitter im Schiefkörper
der Quaternionen.
Gitterdiskriminante
Eine Kenngröße zur Klassifikation von Gittern ist die Gitterdiskriminante. Sie berechnet sich als Volumen der Grundmasche.
Bei Gittern im euklidischen Raum mit der Basismatrix B entspricht dies der Formel
Als Invariante ist der Wert der Gitterdiskriminante unabhängig von der gewählten Basis.
Gitterreduktion
Die Gitterreduktion ist das Problem, aus einer gegebenen Gitterbasis eine Basis mit gewissen Eigenschaften zu berechnen, wie zum Beispiel eine Basis mit kurzen, nahezu orthogonalen Vektoren. Der LLL-Algorithmus (nach Lenstra, Lenstra und Lovász) berechnet in polynomieller Zeit eine sogenannte LLL-reduzierte Basis, mit deren Hilfe man sehr kurze Gittervektoren erhält. In der Tat liegt die Länge des ersten Vektors einer LLL-reduzierten Basis sehr nah an der Länge des kürzesten nichttrivialen Gittervektors.
Der LLL-Algorithmus hat zahlreiche Anwendungen in der Kryptoanalyse von asymmetrischen Verschlüsselungsverfahren, wie dem RSA-Kryptosystem und dem Merkle-Hellman-Kryptosystem, gefunden.
Literatur
- John Horton Conway, Neil Sloane: Sphere packings, lattices and groups. Grundlehren der mathematischen Wissenschaften 290, Springer, 3. Auflage 1999, ISBN 0387985859.
- Daniele Micciancio, Shafrira Goldwasser: Complexity of lattice problems. A cryptographic perspective. Kluwer Academic & Springer 2002, ISBN 9780792376880.
- Phong Q. Nguyen, Brigitte Vallée (Hrsg.): The LLL algorithm. Survey and applications. Reihe Information Security and Cryptography, Springer 2010, ISBN 978-3-642-02294-4.
Weblinks
- Noam Elkies: Lattices, linear codes, and invariants. Part I Notices AMS 47 (2000), No. 10, S. 1238–1245 Part II Notices AMS 47 (2000), No. 11, S. 1382–1391
- Hendrik Lenstra: Flags and lattice basis reduction. in Carles Casacuberta et al. (Hrsg.): European Congress of Mathematics. Barcelona 2000, Vol. I. Birkhäuser 2002, ISBN 978-3-764-36417-5, S. 37–52. Online hier oder dort
- 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 (Hrsg.): Algorithmic Number Theory. MSRI Publications Vol. 44, Cambridge University Press 2008, ISBN 978-0-521-80854-5, S. 127–181. Online hier oder dort
- Daniel J. Bernstein: Bibliography on Lattice-based public-key cryptography
- Keita Xagawa: Bibliography on Lattice-based Cryptosystems
Siehe auch
- Raumgruppe
- Bravais-Gitter
- Spezielle Gitter werden nach Dedekind bei der Untersuchung algebraisch ganzer Zahlen verwendet. Siehe dazu Ordnung (algebraische Zahlentheorie)
Wikimedia Foundation.