LLL Algorithm
LLLアルゴリズムは、格子基底を多項式時間でほぼ直交する基底に簡約する。得られた最初のベクトルの長さは最短ベクトルの 2^((n-1)/2) 倍以下である。
目的
多項式時間で近似的な格子簡約（lattice reduction）を行い、暗号解読や数論で広く使われる。
メカニズム
グラム・シュミットの直交化を行った後、Lovász 条件（|μ_{i,i-1}|≤1/2 かつ B_i≥(3/4-μ^2)B_{i-1}）を検査し、満たさなければ交換と縮約を繰り返す。出力基底の最初のベクトルの長さは 2^((n-1)/2) * λ_1 以下となる。
ユースケース
- 格子（lattice）を用いた暗号解読
- 多項式の因数分解（factoring）
- CVPの近似解法