一般数体篩法

数論において、一般数体篩法（いっぱんすうたいふるいほう、テンプレート:Lang-en-short, GNFS）は、テンプレート:Mathより大きい整数を素因数分解する古典的アルゴリズムであり、現在知られている最もテンプレート:仮リンクなものである。ヒューリスティックに、整数 テンプレート:Mvar （ テンプレート:Math ビットで構成される）を素因数分解するための複雑性は、テンプレート:仮リンク(L-notation)を用いて以下のように表される。

$\exp ((\sqrt[3]{\frac{64}{9}}+o(1))(\ln n{)}^{\frac{1}{3}}(\ln \ln n{)}^{\frac{2}{3}})=L_n[\frac{1}{3},\sqrt[3]{\frac{64}{9}}]$

ここで、 テンプレート:Math は自然対数である。これはテンプレート:仮リンク(special number field sieve)の一般化である：特殊数体篩法は特定形式の数のみを素因数分解できるが、一般数体篩法は素数冪（根を求めることで素因数分解は容易である）以外の任意の数を素因数分解できる。

（特殊・一般）数体篩法の原理は、より単純なテンプレート:仮リンク(rational sieve)やテンプレート:仮リンク(quadratic sieve)の改良ととらえることができる。このようなアルゴリズムを用いて大きな数 テンプレート:Mvar を素因数分解する場合、 テンプレート:Math 次のテンプレート:仮リンク(smooth number)（つまり、小さな素因数を持つ数）を探す必要がある。これらの値の大きさは、 テンプレート:Mvar の大きさに対して指数関数的である（後述）。一方、一般数体篩法は、 テンプレート:Mvar の大きさに対して準指数関数的な滑らかな数を検索することができる。値が小さくなるため、上のアルゴリズムで調べられる値よりも滑らかである可能性が高くなる。これが一般数体篩法の効率性の鍵である。このスピードアップのためには、一般数体篩法は数体内で計算と素因数分解を行う必要がある。そのため、単純な有理篩法と比較して、アルゴリズムに複雑な部分が多くなる。

アルゴリズムへの入力のサイズは テンプレート:Math 、つまり テンプレート:Mvar の二進表現のビット数である。定数 テンプレート:Mvar について、 テンプレート:Math 次のどの要素も、テンプレート:Math の指数関数的である。数体篩法の実行時間は入力のサイズに対して超多項式的であるが、準指数関数的である。

数体

テンプレート:Mvar が テンプレート:Math （有理数体）上の テンプレート:Mvar 次多項式であり、テンプレート:Mvar がテンプレート:Mvar の複素数根であるとする。すると テンプレート:Math であるが、これは、 テンプレート:Math を テンプレート:Mvar の テンプレート:Mvar 乗未満の累乗の線形結合として表すように書き換えることができる。この方程式を用いて、指数 テンプレート:Math のテンプレート:Math のべき指数を減らすことができる。たとえば、 テンプレート:Math で テンプレート:Mvar が虚数単位テンプレート:Mvarである場合、 テンプレート:Math 、すなわち テンプレート:Math となる。これにより、複素積を定義できる。

$(a+bi)(c+di)=ac+(ad+bc)i+(bd)i^2=(ac-bd)+(ad+bc)i.$

一般に、これは代数体 テンプレート:Math に直接つながる。テンプレート:Math は、次の式で与えられる複素数の集合として定義できる。

$a_{k-1}{r}^{k-1}+...+a_1{r}^1+a_0{r}^0,\text{ where }{a}_0,...,a_{k-1}\text{ in }𝐐.$

このような2つの値の積は、積を多項式として取り、上記のように指数テンプレート:Math の テンプレート:Math のべき指数を書き換えて、同じ形式の値を求めることで計算できる。この数体が実際に テンプレート:Mvar 次元であり、さらに小さな数体に縮退(collapse)しないことを保証するには、 テンプレート:Mvar が有理数体上で既約多項式であれば十分である。同様に、整数環 テンプレート:Math は、整数係数のモニック多項式の根である テンプレート:Math の部分集合として定義できる。場合によっては、この整数環は環 テンプレート:Math と同等である。ただし、 テンプレート:Mvar ≡ 1 mod 4 の場合の テンプレート:Math など、多くの例外がある。

手法

それぞれ小さい次数 d, e の2つの多項式 f(x), g(x) を選ぶ。これらは整数係数であり、有理数に対して既約であり、 n を法として共通の整数根 m を持つように選ぶ。これらの多項式を選ぶための最適な方法は知られていない。簡単な方法の1つは、多項式の次数 d を設定し、 n^1/d 次の異なる m の数について、 n の m 進展開（各桁で-mからmの間の数を許可）を調べ、 f(x) に係数が最小の多項式を、 g(x) に x − m を選ぶ方法である。

数体環 Z[r₁] と Z[r₂] を考えてみよう。ここで、 r₁ と r₂ はそれぞれ多項式 f と g の根である。 f は整数係数の次数 d の多項式であるため、 a と b が整数ならば、 b^d・f(a/b) も同様に整数になる。これを r とする。同様に、 s = b^e・g(a/b) も整数である。目標は、選択した素数の基底に対して r と s を同時にテンプレート:仮リンクにする a と b の整数値を見つけることである。 a と b が小さい場合、 r と s も m 程度の大きさになり、同時に滑らかになる可能性が高くなる。この探索の現在最もよく知られているアプローチは、テンプレート:仮リンク(lattice sieve)である。適切な結果を得るには、大きな因子基底を使う必要がある。

ガウスの消去法を使うことで、このようなペアを十分にあれば、特定の r と対応する s の積を同時に平方数にすることができる。そのためには少し強い条件、つまり、それぞれの積は数体における平方数のノルムであるという条件が必要があるが、条件はこの手法でも達成できる。各 r は a − r₁b のノルムであり、したがって、対応する素因数 a − r₁b の積は Z[r₁] において平方数であり、（Z[r₁] の既知の素因数の積として）決定できる「平方根」を持つ。これは通常、無理数であるような代数的数として表される。同様に、素因数の積 a − r₂b はZ[r₂] において平方数であり、「平方根」も計算できる。なお、ガウスの消去法を使用しても、アルゴリズムは最適な実行時間とならないことに注意。代わりに、 テンプレート:仮リンクやテンプレート:仮リンクなどの疎行列ソルバーアルゴリズムが用いられる。

m は n を法として f と g の両方の根であるため、環 Z[r₁] と Z[r₂] から環 Z/nZ（n を法とする整数全体）への準同型がある。これらの準同型は、 r₁ と r₂ を m に写し、各「平方根」（通常は有理数として表されない）をその整数の代表元に写す。今、因数 a − mb mod n の積は準同型ごとに1つずつ、2つの方法で平方数として求められる。したがって、x² − y² が n で割り切れる2つの数 x, y を見つけることができる。また、少なくとも 1/2 の確率で、 n と x − y の最大公約数を求めることで n の素因数を求められる。

多項式選択の改善

多項式の選択は、アルゴリズムの残りの部分を行う時間に劇的な変化を与える可能性がある。上に示した テンプレート:Mvar の テンプレート:Mvar 進展開に基づいて多項式を選ぶ方法は、実際は多くの場合で最適ではなく、改善の余地がある。

改善方法の1つは、マーフィーとブレントによって提案されたものである。彼らは、小さな素数を法とする根の存在と、ふるい分け領域上の多項式のとる値の平均値に基づいて、多項式の2つの部分からなるスコアを導入した。

報告されている最良の結果は、Thorsten Kleinjungの方法によって達成された。これにより、 テンプレート:Math とすることができる。この方法は 2テンプレート:Math を法とする 1に合同な小さな素因数で構成される テンプレート:Mvar および、最高次係数が60で割り切れるテンプレート:Mvar を検索する。

実装

一部の実装では、特定の小さなクラスの数値に焦点を当てている。これらは、テンプレート:仮リンクで用いられているような、特殊数体篩法として知られる。 NFSNETと呼ばれるプロジェクトは、2002年から少なくとも2007年まで実行され、インターネット上でボランティアの分散コンピューティングを使用した。イギリスのポール・レイランドとテキサスのリチャード・ワッカーバースが関わっていた。

2007年まで、ゴールドスタンダードの実装は、オランダのテンプレート:仮リンク(CWI)によって開発および配布された一連のソフトウェアであり、比較的制限のあるライセンスの下でのみ利用可能だったテンプレート:要出典。2007年、Jason Papadopoulosは、パブリックドメインにあるmsieveの一部として、最終処理のより高速な実装を開発した。どちらの実装も、十分に高速に通信できるクラスタ内の複数のノードに分散できる機能を備えている。

多項式の選択は通常、Kleinjungによって作成されたGPLソフトウェア、またはmsieveによって実行され、格子篩はFrankeとKleinjungによって作成されたGPLソフトウェアによって実行される。これらはGGNFSで配布されている。

• NFS @ Home
• GGNFS
• gnfsによる素因数分解
• CADO-NFS
• msieve （最終処理コード、より小さな数に最適化された多項式選択、および線篩法の実装が含まれる）
• kmGNFS

関連項目

• テンプレート:仮リンク

参考文献

• Arjen K. Lenstra and H. W. Lenstra, Jr. (eds.). "The development of the number field sieve". Lecture Notes in Math. (1993) 1554. Springer-Verlag.
• Richard Crandall and Carl Pomerance. Prime Numbers: A Computational Perspective (2001). 2nd edition, Springer. テンプレート:ISBN2. Section 6.2: Number field sieve, pp. 278–301.

• Matthew E. Briggs: An Introduction to the General Number Field Sieve, 1998