Number Field Sieve
数体ふるい（ NFS）は、既知で最速の古典的素因数分解アルゴリズムである。代数体を用いて平方合同を構成し、劣指数的な計算量で動作する。
目的
大きな整数（100桁超）を最速で素因数分解し、RSAのセキュリティ境界を定義する。
メカニズム
f(m)≡0 (mod n)となる多項式fと整数mを選び、代数体Q(α)の中で滑らかな要素を見つける。線形代数でそれらを組み合わせてノルムを平方にし、x^2≡y^2 (mod n)を得る。計算量はL_n[1/3, (64/9)^(1/3)]である。
ユースケース
- RSA安全性の分析
- 大きな整数の素因数分解（factoring）
- クリプトグラフィへの応用