一般数体ふるい

数論において、一般数体ふるい（GNFS ）は、 $10$ $100$ より大きい整数を因数分解する最も効率的な古典的アルゴリズムとして知られています。経験的に、整数 $n （$ $⌊log$ $2$ $n$ $⌋ + 1$ ビットからなる）を因数分解する複雑さは次のようになります。

{\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}}

O表記法とL表記法で。^[1]これは特殊数体ふるいの一般化です。特殊数体ふるいは特定の特殊な形式の数しか因数分解できませんが、一般数体ふるいは素数累乗（根を取ることで因数分解できる）以外の任意の数を因数分解できます。

数体ふるい (特殊および一般) の原理は、より単純な有理ふるいまたは二次ふるいの改良版として理解できます。このようなアルゴリズムを使用して大きな数 $n を因数分解する場合、$ $n$ $1/2$ の次数の滑らかな数(つまり、素因数が小さい数)を検索する必要があります。これらの値のサイズは、 $n$ のサイズに対して指数関数的です(以下を参照)。一方、一般的な数体ふるいは、 $n$ のサイズに対して指数以下の滑らかな数を検索することができます。これらの数は小さいため、以前のアルゴリズムで検査された数よりも滑らかである可能性が高くなります。これが数体ふるいの効率の鍵です。この高速化を実現するために、数体ふるいは数体で計算と因数分解を実行する必要があります。これにより、より単純な有理ふるいと比較して、アルゴリズムの多くのかなり複雑な側面が生じます。

アルゴリズムへの入力のサイズは、 $log 2 n$ $またはn$ のバイナリ表現のビット数です。定数 c の順序 n c の任意 $の$ $要素は$ 、 $log$ $n$ の指数関数です。数体ふるいの実行時間は、入力のサイズに対して 超多項式ですが、指数関数未満です。

数値フィールド

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

{\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]}$

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$ $\geq$ $k$ で $r$ の任意の累乗を上記のように減算することで計算でき、同じ形式の値が得られます。この体が実際に $k$ 次元であり、さらに小さい体に縮小されないことを保証するには、 $f$ が有理数上の既約多項式であれば十分です。同様に、整数の環を、整数係数を持つ単項多項式の根である部分集合として定義できます。場合によっては、この整数の環は環と同等です。ただし、多くの例外があります。^[2] ${\textstyle \mathbb {O} _{\mathbb {Q} [r]}}$ ${\textstyle \mathbb {Q} [r]}$ ${\textstyle \mathbb {Z} [r]}$

方法

小さい次数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 _{2 は}多項式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のサイズ程度になり、同時に滑らかになる可能性が高くなります。この検索に対する現在最もよく知られているアプローチは格子ふるい分けです。許容できる収量を得るには、大きな因数基数を使用する必要があります。

このようなペアが十分あれば、ガウス消去法を使用して、特定のrとそれに対応するsの積が同時に平方数になるよう取得できます。もう少し強い条件、つまりそれらが数体における平方数のノルムであることが必要ですが、その条件もこの方法で達成できます。各rはa − r ₁bのノルムであるため、対応する因数a − r ₁bの積はZ [ r ₁ ]の平方数であり、その「平方根」は ( Z [ r ₁ ]の既知の因数の積として) 決定できます。これは通常、無理代数数として表されます。同様に、因数a − r ₂bの積はZ [ r ₂ ]の平方数であり、その「平方根」も計算できます。ガウス消去法を使用しても、アルゴリズムの実行時間は最適にならないことに注意してください。代わりに、 Block LanczosやBlock Wiedemannなどの疎行列解法アルゴリズムが使用されます。

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

多項式選択の改善

$多項式の選択は、アルゴリズムの残りの部分を完了するのにかかる時間に劇的な影響を与える可能性があります。上記に示した、 m を$ 底とする $n$ の展開に基づいて多項式を選択する方法は、多くの実際の状況では最適ではないため、より優れた方法が開発されています。

そのような方法の1つは、マーフィーとブレントによって提案されました。^[3]彼らは、小さな素数を法とする根の存在と、ふるい分け領域で多項式が取る平均値に基づいて、多項式の2部構成のスコアを導入しました。

最も良い結果が報告されている^[4]は、Thorsten Kleinjungの方法^{[5]によって達成された。この方法では} $g (x) = ax + b$ を許容し、 $2d$ を法として1に合同な小さな素因数で構成される $a$ と、 60で割り切れる $f$ の主係数を探索する。

実装

いくつかの実装では、特定の小さな数のクラスに焦点を当てています。これらは、カニンガムプロジェクトで使用されているような特殊数体ふるい技法として知られています。NFSNETと呼ばれるプロジェクトは、2002年^[6]から少なくとも2007年まで実行されました。このプロジェクトでは、インターネット上のボランティア分散コンピューティングが使用されました。^[7]英国のポール・レイランドとテキサスのリチャード・ワッカーバースが関与しました。^[8]

2007 年まで、ゴールドスタンダード実装はオランダのCWIによって開発および配布されたソフトウェアスイートであり、比較的制限の厳しいライセンスの下でのみ利用可能でした。 ^[要出典] 2007 年に Jason Papadopoulos は、パブリックドメインの msieve の一部として、最終処理のより高速な実装を開発しました。両方の実装は、十分に高速な相互接続を持つクラスター内の複数のノードに分散できる機能を備えています。

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

NFS@ホーム
GGNFS
gnfs による因子
CADO-NFS
msieve (最終処理コード、小さい数値に最適化された多項式選択、および線ふるいの実装が含まれています)
kmGNFS

参照

特殊番号フィールドふるい

注記

^ ポメランス、カール(1996 年 12 月)。「2 つのふるいの物語」(PDF)。AMSの通知。第 43 巻、第 12 号。pp. 1473–1485。
^ リベンボイム、パウロ (1972)。代数的数。ワイリー・インターサイエンス。ISBN 978-0-471-71804-8。
^ マーフィー、B.; ブレント、RP (1998)、「数体ふるいの2次多項式について」、オーストラリアコンピュータサイエンスコミュニケーション、20：199–213
^ Franke, Jens (2006)、RSA 200 および大規模プロジェクトについて(PDF)
^ Kleinjung, Thorsten (2006 年 10 月). 「一般数体ふるいの多項式選択について」(PDF) .計算数学. 75 (256): 2037–2047. Bibcode :2006MaCom..75.2037K. doi : 10.1090/S0025-5718-06-01870-9 . 2007 年 12 月 13 日閲覧。
^ Paul Leyland (2003 年 12 月 12 日)。「NFSNET: 1 年目」。EIDMA -CWI ワークショップ「大きな数の因数分解」でのプレゼンテーション。2011年8 月 9 日閲覧。
^ 「NFSNETへようこそ」。2007年4月23日。2007年10月22日時点のオリジナルよりアーカイブ。2011年8月9日閲覧。
^ 「NFSNETについて」。2008年5月9日時点のオリジナルよりアーカイブ。2011年8月9日閲覧。

参考文献

Arjen K. LenstraおよびHW Lenstra, Jr. (編)。「数体ふるいの開発」。数学講義ノート (1993) 1554。Springer-Verlag。
Richard Crandall およびCarl Pomerance . 素数: 計算の観点 (2001)。第 2 版、Springer。ISBN 0-387-25282-7 .セクション 6.2: 数体ふるい、pp. 278–301。

マシュー・E・ブリッグス：一般数体ふるい入門、1998年

[1] ポメランス、カール(1996 年 12 月)。「2 つのふるいの物語」(PDF)。AMSの通知。第 43 巻、第 12 号。pp. 1473–1485。

[AlgNumbersRibenboim-2] リベンボイム、パウロ (1972)。代数的数。ワイリー・インターサイエンス。ISBN 978-0-471-71804-8。

[3] マーフィー、B.; ブレント、RP (1998)、「数体ふるいの2次多項式について」、オーストラリアコンピュータサイエンスコミュニケーション、20：199–213

[4] Franke, Jens (2006)、RSA 200 および大規模プロジェクトについて(PDF)

[5] Kleinjung, Thorsten (2006 年 10 月). 「一般数体ふるいの多項式選択について」(PDF) .計算数学. 75 (256): 2037–2047. Bibcode :2006MaCom..75.2037K. doi : 10.1090/S0025-5718-06-01870-9 . 2007 年 12 月 13 日閲覧。

[6] Paul Leyland (2003 年 12 月 12 日)。「NFSNET: 1 年目」。EIDMA -CWI ワークショップ「大きな数の因数分解」でのプレゼンテーション。2011年8 月 9 日閲覧。

[7] 「NFSNETへようこそ」。2007年4月23日。2007年10月22日時点のオリジナルよりアーカイブ。2011年8月9日閲覧。

[8] 「NFSNETについて」。2008年5月9日時点のオリジナルよりアーカイブ。2011年8月9日閲覧。