LLL-reduzierte Basen (size condition)

Idee: reduziere b_i bzgl. b_j^* (nicht: b_j )

• Gitter Γ , Basis B in $\mathbb {Z}$^d , O-Basis B^* = GSO(B) in $\mathbb {Q}$^d .
• Def μ_{i, j} = 〈b_i, b_j^*〉/〈b_j^*, b_j^*〉 ,

• Def: B heißt größenreduziert, falls ∀i > j : | μ_{i, j}|≤1/2 .

• Algorithmus (size reduction)

  while (existiert i > j mit | μ_{i, j}| > 1/2 ) do b_i : = b_i - ⌊μ_{i, j}⌉⋅b_j

• Satz: diese Alg. liefert eine zu B äquivalente größenreduzierte Basis

  ...in Polynomialzeit (quadratisch)