SVP-Algorithmen (Ansatz)

• man bestimmt nicht nur einen kurzen Vektor in Γ ,

  sondern eine Basis aus kurzen Vektoren.

• Man transformiert die gegebene Basis schrittweise.

  In jedem Schritt wird ein Basisvektor b_i ersetzt durch b_i' = b_i - mb_j für ein geeignetes m∈$\mathbb {Z}$ mit | b_i'| < | b_i| .

zu untersuchen sind

• Korrektheit (Teil 1) -- trivial, jederzeit b_i∈Γ
• Strategie (Auswahl von i, j ) und Laufzeit
• Korrektheit (Teil 2) -- wenn so kein Vektor b mit | b| < D gefunden wird, gibt es dann überhaupt keinen?

Ziel: guter Trade-Off zw. Genauigkeit und Geschwindigkeit.