Lattice Reduction
格子基底簡約（Lattice Reduction）は、n 次元格子の中で短くほぼ直交する基底ベクトルを見つける。弱い RSA や NTRU などの暗号方式を破るのに使われる。
目的
格子の中の短いベクトルを見つける。暗号解読や最適化で使われる。
メカニズム
格子は線形変換のもとでの Z^n の離散部分集合である。簡約は、ベクトル長が連続最短ベクトル（ミンコフスキー境界）に近い短い基底を見つける。LLL アルゴリズムは近似的な簡約を行い、厳密な SVP/CVP は NP 困難である。
ユースケース
- クリプトの解読
- CVP/SVP の求解
- 信号処理（シグナルプロセッシング）