一般番号フィールドふるい

数論において、一般数体篩法（GNFS ）は、 10¹⁰⁰より大きい整数を素因数分解するための最も効率的な古典的アルゴリズムとして知られています。経験的に、整数nを^素因数分解する際のその複雑さ（ ⌊log ₂ n ⌋ + 1ビットから構成される）は次の形式になります。

${\displaystyle {\begin{aligned}&\exp \left(\left((64/9)^{1/3}+o(1)\right)\left(\log n\right)^{1/3}\left(\log \log n\right)^{2/3}\right)\\[5pt]={}&L_{n}\left[1/3,(64/9)^{1/3}\right]\end{aligned}}}$

ビッグオー記法とL記法で表す。^{[ 1 ]}これは特殊数体篩の一般化である。特殊数体篩は特定の特殊形式の数しか因数分解できないのに対し、一般数体篩は素数のべき乗（根を取ることで簡単に因数分解できる）以外の任意の数を因数分解できる。

数体篩法（特殊篩法と一般篩法の両方）の原理は、より単純な有理篩法や二次篩法の改良版として理解できます。このようなアルゴリズムを用いて大きな数nを因数分解する場合、 n ^1/2のオーダーの滑らかな数（つまり、素因数が小さい数）を探す必要があります。これらの数の大きさはnの大きさに対して指数関数的に増加します（後述）。一方、一般的な数体篩法では、nの大きさに対して準指数関数的に増加する滑らかな数を探すことができます。これらの数は小さいため、以前のアルゴリズムで調べた数よりも滑らかである可能性が高くなります。これが数体篩法の効率性の鍵です。この高速化を実現するために、数体篩法は数体で計算と因数分解を実行する必要があります。このため、より単純な有理篩法と比較して、アルゴリズムには多くの複雑な側面が生じます。

アルゴリズムへの入力サイズはlog ₂ n  、つまりnの二進表現におけるビット数です。定数 c に対してⁿ cの次数を持つ任意の要素は、log n に対して指数関数的に増加します。数体篩法の実行時間は、入力サイズに対して超多項式的であり、準指数関数的です。

fがk次多項式であると仮定します。${\textstyle \mathbb {Q} }$(有理数)、rはfの複素根です。すると、f ( r )  =  0となり、これをr ^{k を}k未満のrのべき乗の線形結合として表すことができます。この式は、指数e ≥ kのrのべき乗を消去するために使用できます。たとえば、f ( x ) = x ² + 1でr が虚数単位iの場合、i ² + 1 = 0、つまりi ² = −1となります。これにより、複素積を定義できます。          

${\displaystyle {\begin{aligned}(a+bi)(c+di)&=ac+(ad+bc)i+(bd)i^{2}\\[4pt]&=(ac-bd)+(ad+bc)i.\end{aligned}}}$

一般的に、これは直接的に代数的数体へとつながる。${\textstyle \mathbb {Q} [r]}$これは、以下の式で定義される複素数の集合として表すことができます。

${\displaystyle a_{k-1}r^{k-1}+\cdots +a_{1}r^{1}+a_{0}r^{0},{\text{ただし}}a_{0},\ldots ,a_{k-1}\in \mathbb {Q} 。}$

このような値の任意の 2 つの積は、積を多項式として扱い、上記のように指数e ≥ kのrのべき乗を簡約することで計算でき、同じ形式の値が得られます。この体が実際にk次元であり、さらに小さな体に縮退しないことを保証するには、 fが有理数上の既約多項式であれば十分です。同様に、整数環を定義することもできます。${\textstyle \mathbb {O} _{\mathbb {Q} [r]}}$のサブセットとして${\textstyle \mathbb {Q} [r]}$これらは整数係数を持つ単多項式の根です。場合によっては、この整数環は環と等価です。${\textstyle \mathbb {Z} [r]}$しかし、多くの例外がある。^{[ 2 ]}

実装によっては、特定のより小さなクラスの数に焦点を当てるものもあります。これらは、カニンガム・プロジェクトなどで使用されているような、特殊数体篩（SNFS）技術として知られています。

2007年まで、ゴールドスタンダードとされていた実装は、オランダのCWIが開発・配布していたソフトウェア群であり、比較的制限の厳しいライセンスの下でのみ利用可能でした。 2007年、ジェイソン・パパドプロス氏が、パブリックドメインであるmsieveの一部として、より高速な最終処理実装を開発しました。どちらの実装も、十分な速度の相互接続を備えたクラスタ内の複数のノードに分散して使用できるという特徴を備えています。

• GGNFS (GNU GPL) はChris Monicoによって作成され、最終更新日は2005年です。すべての手順を実行できます。SNFSの場合は約160桁、GNFSの場合は約135桁を扱います。以下の部分もGNU GPLの下で含まれています。
  • pol5: クラインユングによる多項式選択（2005年）
  • lasieve4: Franke と Kleinjung による格子ふるい 2001 – 2004
• gnfs によるファクタリング、C++ コードは Chris DiBona と Chris Card によるもので、最終更新日は 2024 年です。GNU GPL ライセンス。
• CADO-NFSは、 INRIAの大規模チームによってすべてのステップがC/C++で実装されています。最終更新日は2025年（2025年時点）。ライセンスはGNU LGPLです。
• msieve。最終処理コード、より小さな数値に最適化された多項式選択、および線篩の実装が含まれています。パブリックドメイン。
• kmGNFS。すべての手順の基本実装はChristos BakogiannisとNikolaos Karapanosによって行われ、最終更新は2009年です。
• YAFU。すべての手順の実装はベン・ブーロウによるものです。最終更新日：2025年（2025年現在）。パブリックドメイン。

• マシュー・E・ブリッグス著：一般数体篩入門、1998年