二次ふるい法

二次ふるい法（にじふるいほう）とは、素因数分解に関するアルゴリズムで、実用では一般数体篩法に次いで2番目に早い計算方法であるとされている^[1][2]。

10進数で100桁までなら計算は最速であり、一般数体篩法よりかなり単純である。

算法(アルゴリズム)

1. パラメータの選択
2. 篩
3. 有効式の選択
4. 分解

実装

• C Quadratic Sieve – C言語で書かれた二次ふるい法のパブリックドメイン実装。2022年に公開され、最大330ビットまでの数のバッチ因数分解をサポートし、JSONまたはCSV形式で出力可能。