数体篩法

数論において、一般数体篩法（いっぱんすうたいふるいほう、英: General number field sieve, GNFS）は、10100より大きい整数を素因数分解する古典的アルゴリズムであり、現在知られている最もなものである。ヒューリスティックに、整数 n （ ⌊log2 n⌋ + 1 ビットで構成される）を素因数分解するための複雑性は、(L-notation)を用いて以下のように表される。 ここで、 ln は自然対数である。これは(special number field sieve)の一般化である：特殊数体篩法は特定形式の数のみを素因数分解できるが、一般数体篩法は素数冪（根を求めることで素因数分解は容易である）以外の任意の数を素因数分解できる。 （特殊・一般）数体篩法の原理は、より単純な(rational sieve)や(quadratic sieve)の改良ととらえることができる。このようなアルゴリズムを用いて大きな数 n を素因数分解する場合、 n1/2 次の(smooth number)（つまり、小さな素因数を持つ数）を探す必要がある。これらの値の大きさは、 n の大きさに対して指数関数的である（後述）。一方、一般数体篩法は、 n の大きさに対して準指数関数的な滑らかな数を検索することができる。値が小さくなるため、上のアルゴリズムで調べられる値よりも滑らかである可能性が高くなる。これが一般数体篩法の効率性の鍵である。このスピードアップのためには、一般数体篩法は数体内で計算と素因数分解を行う必要がある。そのため、単純な有理篩法と比較して、アルゴリズムに複雑な部分が多くなる。 アルゴリズムへの入力のサイズは log2 n 、つまり n の二進表現のビット数である。定数 c について、 nc 次のどの要素も、log n の指数関数的である。数体篩法の実行時間は入力のサイズに対して超多項式的であるが、準指数関数的である。