Gitter: Definition, Beispiel, SVP

• ein Gitter (lattice) L mit Basis B = [b₁,..., b_n]⊂$\mathbb {Z}$^d

  ist die Menge L(B) = $\left\{\vphantom{\sum_{k=1}^n c_kb_k}\right.$$\sum_{{k=1}}^{n}$c_kb_k$\left.\vphantom{\sum_{k=1}^n c_kb_k}\right\mid$∀k : c_k∈$\mathbb {Z}$}

• Beispiel: b₁ = [5, 3]^T, b₂ = [8, 5]^T, B = [b₁, b₂] = $\begin{pmatrix}5&8 \\ 3&5\end{pmatrix}$

  weitere Elemente von L(B) sind

  [13, 8]^T = b₁ + b₂, [3, 2]^T = - b₁ + b₂,...

• Shortest Vector Problem (SVP):
  • Eingabe B,
  • Ausgabe: ein kürzester Vektor in L(B) $\setminus$ {0}
• Lösungsverfahren: d = 2 exakt, d größer: genähert (LLL)
• Anwendungen: ganzzahlige Beziehungen, Kryptographie