Lenstra–Lenstra–Lovász lattice basis reduction algorithm とは

Lenstra-Lenstra-Lovász(LLL)格子基底縮小アルゴリズムは、1982年にArjen Lenstra、Hendrik LenstraおよびLászlóLovászによって考案された多項式時間格子縮小アルゴリズムである。格子Lに対してn次元の整数座標を持つ基底 B = { b 1 , b 2 , , b d } {\displaystyle \mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\}} (Rnの離散的なサブグループ)を   d n {\displaystyle \ d\leq n} と置き換えると、LLLアルゴリズムはLLLで短縮された(短い、ほぼ直交する)格子ベースを時間的に計算する
O ( d 5 n log 3 B ) {\displaystyle O(d^{5}n\log ^{3}B)\,}
Bはユークリッド標準の下での b i {\displaystyle b_{i}} の最大長である。
元のアプリケーションは、有理係数を有する多項式を因数分解するための多項式時間アルゴリズムを与え、実数への有理近似を同時に求め、固定次元における整数線形計画問題を解くことであった。