Quadratic Sieve
二次ふるい法は、x^2≡y^2 (mod n) となるxを見つけ、gcd(x±y,n) が素因数を明らかにする可能性を利用する。100桁未満では最速の素因数分解法である。
目的
中規模（約100桁）の整数をできるだけ高速に素因数分解することである。
メカニズム
x_i^2 mod n がB-smoothとなるような多くのx_iを集め、GF(2)上の線形代数で組み合わせて平方数の積が完全平方になるようにする。この組み合わせが X^2≡Y^2 (mod n) を与え、gcd(X±Y,n) が自明でない因子になることがある。
ユースケース
- 整数のファクタリング
- クリプトアナリシスへの応用
- 数論アルゴリズムの研究