一般数体篩法のソースを表示

[[数論]]において、'''一般数体篩法'''（いっぱんすうたいふるいほう、{{Lang-en-short|General number field sieve}}, GNFS）は、{{Math|10<sup>100</sup>}}より大きい整数を[[素因数分解]]する古典的[[アルゴリズム]]であり、現在知られている最も{{仮リンク|アルゴリズムの効率性|en|label=効率的|algorithmic efficiency}}なものである<ref>{{Cite journal|和書|last=伊豆|author=|first=哲也|last2=小暮|first2=淳|last3=下山|first3=武司|date=2008|title=近年の素因数分解について|url=https://doi.org/10.1587/essfr.1.3_58|journal=電子情報通信学会 基礎・境界ソサイエティ Fundamentals Review|volume=1|issue=3|pages=3_58–3_70|doi=10.1587/essfr.1.3_58|publisher=電子情報通信学会}}</ref>。[[ヒューリスティック]]に、整数 {{Mvar|n}}  （ {{Math|⌊log<sub>2</sub> {{mvar|n}}⌋ + 1}} ビットで構成される）を素因数分解するための[[計算複雑性理論|複雑性]]は、{{仮リンク|L表記|en|L-notation}}(L-notation)を用いて以下のように表される<ref>{{Cite news|last=Pomerance|first=Carl|authorlink=Carl Pomerance|date=December 1996|title=A Tale of Two Sieves|newspaper=Notices of the AMS|volume=43|issue=12|pages=1473–1485|url=https://www.ams.org/notices/199612/pomerance.pdf|format=PDF}}</ref>。

: <math>\exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\ln n)^{\frac{1}{3}}(\ln \ln n)^{\frac{2}{3}}\right) =L_n\left[\frac{1}{3},\sqrt[3]{\frac{64}{9}}\right]</math>

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

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

アルゴリズムへの入力のサイズは {{Math|log<sub>2</sub>&nbsp;''n''}} 、つまり {{Mvar|n}} の二進表現のビット数である。定数 {{Mvar|c}} について、 {{Math|''n''<sup>''c''</sup>}} 次のどの要素も、{{Math|log&nbsp;''n''}} の指数関数的である。数体篩法の実行時間は入力のサイズに対して超多項式的であるが、準指数関数的である。

== 数体 ==
{{Mvar|f}} が {{Math|'''Q'''}} （有理数体）上の {{Mvar|k}} 次多項式であり、{{Mvar|r}} が{{Mvar|f}} の複素数根であるとする。すると  {{Math|''f''(''r'')&nbsp;{{=}}&nbsp;0}} であるが、これは、  {{Math|''r''<sup>''k''</sup>}} を {{Mvar|r}} の {{Mvar|k}} 乗未満の累乗の線形結合として表すように書き換えることができる。この方程式を用いて、指数 {{Math|''e'' ≥ ''k''}} の{{Math|''r''}} のべき指数を減らすことができる。たとえば、 {{Math|''f''(''x'')&nbsp;{{=}}&nbsp;''x''<sup>2</sup>&nbsp;+&nbsp;1}} で {{Mvar|r}} が虚数単位{{Mvar|i}}である場合、 {{Math|''i''<sup>2</sup>&nbsp;+&nbsp;1&nbsp;{{=}}&nbsp;0}} 、すなわち {{Math|''i''<sup>2</sup>&nbsp;{{=}}&nbsp;−1}} となる。これにより、複素積を定義できる。

: <math>(a+bi)(c+di) = ac + (ad+bc)i + (bd)i^2 = (ac - bd) + (ad+bc)i.</math>

一般に、これは[[代数体]] {{Math|'''Q'''(''r'')}} に直接つながる。{{Math|'''Q'''(''r'')}} は、次の式で与えられる複素数の集合として定義できる。

: <math>a_{k-1}r^{k-1} + ... + a_{1}r^{1} + a_{0}r^{0}, \text{ where } a_0,...,a_{k-1} \text{ in } \mathbf{Q}.</math>

このような2つの値の積は、積を多項式として取り、上記のように指数{{Math|''e'' ≥ ''k''}} の {{Math|''r''}} のべき指数を書き換えて、同じ形式の値を求めることで計算できる。この数体が実際に {{Mvar|k}} 次元であり、さらに小さな数体に縮退(collapse)しないことを保証するには、 {{Mvar|f}} が有理数体上で[[既約多項式]]であれば十分である。同様に、[[整数環]] {{Math|'''O'''<sub>'''Q'''(''r'')</sub>}} は、整数係数の[[モニック多項式]]の根である {{Math|'''Q'''(''r'')}} の部分集合として定義できる。場合によっては、この整数環は環 {{Math|'''Z'''[''r'']}} と同等である。ただし、 {{Mvar|d}} ≡ 1 mod 4 の場合の {{Math|'''Q'''({{sqrt|''d''}})}} など、多くの例外がある。 <ref name="AlgNumbersRibenboim">{{Cite book|title=Algebraic Numbers|publisher=Wiley-Interscience|last=Ribenboim, Paulo|year=1972|isbn=978-0-471-71804-8}}</ref>

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

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

[[ガウスの消去法]]を使うことで、このようなペアを十分にあれば、特定の ''r'' と対応する ''s'' の積を同時に平方数にすることができる。そのためには少し強い条件、つまり、それぞれの積は数体における平方数の[[ノルム (体論)|ノルム]]であるという条件が必要があるが、条件はこの手法でも達成できる。各 ''r'' は ''a''&nbsp;−&nbsp;''r''<sub>1</sub>''b'' のノルムであり、したがって、対応する素因数 ''a''&nbsp;−&nbsp;''r''<sub>1</sub>''b'' の積は '''Z'''[''r''<sub>1</sub>] において平方数であり''、''（'''Z'''[''r''<sub>1</sub>] の既知の素因数の積として）決定できる「平方根」を持つ。これは通常、無理数であるような[[代数的数]]として表される。同様に、素因数の積 ''a&nbsp;−&nbsp;r<sub>2</sub>b'' は'''Z'''[''r''<sub>2</sub>] において平方数であり、「平方根」も計算できる。なお、ガウスの消去法を使用しても、アルゴリズムは最適な実行時間とならないことに注意。代わりに、 {{仮リンク|ブロックランチョスアルゴリズム|en|Block Lanczos algorithm}}や{{仮リンク|ブロックヴィーデマンアルゴリズム|en|Block Wiedemann algorithm}}などの疎行列ソルバーアルゴリズムが用いられる。

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

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

改善方法の1つは、マーフィーとブレントによって提案されたものである<ref>{{cite journal|title=On quadratic polynomials for the issue field sieve |author=Murphy, Brian and Brent, Richard P and others |year=1997 |publisher=The Australian National University |hdl=1885/40747 |url=http://digitalcollections.anu.edu.au/handle/1885/40747}}</ref>。彼らは、小さな素数を法とする根の存在と、ふるい分け領域上の多項式のとる値の平均値に基づいて、多項式の2つの部分からなるスコアを導入した。

報告されている最良の結果<ref>{{Citation|title=On RSA 200 and larger projects|last=Franke|first=Jens|year=2006|url=http://www.hyperelliptic.org/tanja/SHARCS/talks06/Jens_Franke.pdf}}</ref>は、Thorsten Kleinjungの方法<ref>{{Cite journal|last=Kleinjung|first=Thorsten|date=October 2006|title=On polynomial selection for the general number field sieve|url=https://www.ams.org/mcom/2006-75-256/S0025-5718-06-01870-9/S0025-5718-06-01870-9.pdf|journal=Mathematics of Computation|volume=75|issue=256|pages=2037–2047|accessdate=2007-12-13|DOI=10.1090/S0025-5718-06-01870-9}}</ref>によって達成された。これにより、 {{Math|''g''(''x'') {{=}} ''ax''&nbsp;+&nbsp;''b''}} とすることができる。この方法は 2{{Math|''d''}} を法とする 1に合同な小さな素因数で構成される {{Mvar|a}} および、最高次係数が60で割り切れる{{Mvar|f}} を検索する。

== 実装 ==
一部の実装では、特定の小さなクラスの数値に焦点を当てている。これらは、{{仮リンク|カニンガムプロジェクト|en|Cunningham project}}で用いられているような、特殊数体篩法として知られる。 NFSNETと呼ばれるプロジェクトは、2002年<ref>{{Cite web |title=NFSNET: the first year |author=Paul Leyland |website=Presentation at EIDMA-CWI Workshop on Factoring Large Numbers |date=December 12, 2003 |url=http://homepages.cwi.nl/~herman/Leyland.ppt |access-date=August 9, 2011}}</ref>から少なくとも2007年まで実行され、[[インターネット]]上でボランティアの分散コンピューティングを使用した<ref>{{Cite web |title=Welcome to NFSNET |date=April 23, 2007 |url=http://www.nfsnet.org/ |archive-url=https://web.archive.org/web/20071022032617/http://www.nfsnet.org/ |archive-date=October 22, 2007 |access-date=August 9, 2011}}</ref>。[[イギリス]]の[[ポール・レイランド]]とテキサスのリチャード・ワッカーバースが関わっていた<ref>{{Cite web |title=About NFSNET |url=http://www.nfsnet.org/aboutus.html |archive-url=https://web.archive.org/web/20080509131653/http://www.nfsnet.org/aboutus.html |archive-date=May 9, 2008 |access-date=August 9, 2011}}</ref>。

2007年まで、ゴールドスタンダードの実装は、オランダの{{仮リンク|国立数学・情報科学研究所|en|Centrum Wiskunde & Informatica}}(CWI)によって開発および配布された一連のソフトウェアであり、比較的制限のあるライセンスの下でのみ利用可能だった{{要出典|date=March 2017}}。2007年、[[ジェイソン・パパドプロス|Jason Papadopoulos]]は、パブリックドメインにあるmsieveの一部として、最終処理のより高速な実装を開発した。どちらの実装も、十分に高速に通信できるクラスタ内の複数のノードに分散できる機能を備えている。

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

* [http://escatter11.fullerton.edu/nfs/ NFS @ Home]
* [http://www.math.ttu.edu/~cmonico/software/ggnfs/ GGNFS]
* [[sourceforge:projects/factor-by-gnfs/|gnfsによる素因数分解]]
* [http://cado-nfs.inria.fr/ CADO-NFS]
* [http://sourceforge.net/projects/msieve/ msieve] （最終処理コード、より小さな数に最適化された多項式選択、および線篩法の実装が含まれる）
* [http://kmgnfs.cti.gr kmGNFS]

== 関連項目 ==
* {{仮リンク|特殊数体篩法|en|special number field sieve}}

== 脚注 ==
{{Reflist}}

== 参考文献 ==
{{Refbegin}}
* [[Arjen Lenstra|Arjen K. Lenstra]] and [[Hendrik Lenstra|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|0-387-25282-7}}. Section 6.2: Number field sieve, pp.&nbsp;278–301.
{{Refend}}
* Matthew E. Briggs: An Introduction to the General Number Field Sieve, 1998

{{DEFAULTSORT:いつはんすうたいふるいほう}}
[[Category:素因数分解アルゴリズム]]
[[Category:ヒューリスティック・アルゴリズム]]
[[Category:未査読の翻訳があるページ]]
[[Category:数学に関する記事]]
[[Category:数論]]