LLL-reduzierte Basen (Lovasz condition)

• Def. Lovasz-Bedingung (mit Parameter δ ) an Stelle i :

  | π_{span(b1,…, bi-1)}(b_i)|²≤δ⋅| π_{span(b1,…, bi-1)}(b_i+1)|²

  equiv. (Ü) | b_i^*|²≤δ⋅| b^*_i+1 + μ_{i+1, i}b^*_i|²

• alternativ: | b_i^*|²≤2| b_i+1^*|²

  (nach V. Shoup, siehe v.z.Gathen: MCA, Notes 16.2)

• Algorithmus (LLL): do { größenreduktion;

  wenn ∃i : ¬Lovasz_δ(i) , dann b_i↔b_i+1 ; continue }

• liefert (1.) Basis mit kurzen Vektor (2.) in Polynomialzeit