Bsp: 〈(12, 2),(13, 4)〉 Def: B = [b1, b2] ist Lagrange-Gauß-reduziert, falls ∀q∈ : | b1|≤| b2|≤| b2 + qb1| . Satz: [b1, b2] LG-reduz. B. für Γ ⇒ b1 ist kürzester V. in Γ . Algorithmus: do { μ = 〈b2, b1〉/〈b1, b1〉 ; (b2, b1) : = (b1, b2 - ⌊μ⌉b1) } while (| b1| > | b2|) Satz: ...erzeugt LG-reduzierte Basis in poly. Zeit. Korrektheit offensichtlich, Laufzeit: folgt aus | b1'|2 < | b1|2/3 . Johannes Waldmann 2015-12-11
do { μ = 〈b2, b1〉/〈b1, b1〉 ; (b2, b1) : = (b1, b2 - ⌊μ⌉b1) } while (| b1| > | b2|)
Korrektheit offensichtlich,
Laufzeit: folgt aus | b1'|2 < | b1|2/3 .