コンテンツにスキップ

一般数体篩法

出典: フリー百科事典『ウィキペディア（Wikipedia）』

数論において、一般数体篩法（いっぱんすうたいふるいほう、英: General number field sieve, GNFS）は、10100より大きい整数を素因数分解する古典的アルゴリズムであり、現在知られている最も効率的（英語版）なものである[1]。ヒューリスティックに、整数 n （ ⌊log2 n⌋ + 1 ビットで構成される）を素因数分解するための複雑性は、L表記（英語版）(L-notation)を用いて以下のように表される[2]。

ここで、 ln は自然対数である。これは特殊数体篩法（英語版）(special number field sieve)の一般化である：特殊数体篩法は特定形式の数のみを素因数分解できるが、一般数体篩法は素数冪（根を求めることで素因数分解は容易である）以外の任意の数を素因数分解できる。

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

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

数体

[編集]

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

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

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

手法

[編集]

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

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

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

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

多項式選択の改善

[編集]

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

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

報告されている最良の結果[5]は、Thorsten Kleinjungの方法[6]によって達成された。これにより、 g(x) = ax + b とすることができる。この方法は 2d を法とする 1に合同な小さな素因数で構成される a および、最高次係数が60で割り切れるf を検索する。

実装

[編集]

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

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

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

関連項目

[編集]

脚注

[編集]
  1. ^ 伊豆, 哲也、小暮, 淳、下山, 武司「近年の素因数分解について」『電子情報通信学会 基礎・境界ソサイエティ Fundamentals Review』第1巻第3号、電子情報通信学会、2008年、3_58–3_70、doi:10.1587/essfr.1.3_58。 
  2. ^ Pomerance, Carl (December 1996). “A Tale of Two Sieves” (PDF). Notices of the AMS 43 (12): pp. 1473–1485. https://www.ams.org/notices/199612/pomerance.pdf 
  3. ^ Ribenboim, Paulo (1972). Algebraic Numbers. Wiley-Interscience. ISBN 978-0-471-71804-8 
  4. ^ Murphy, Brian and Brent, Richard P and others (1997). On quadratic polynomials for the issue field sieve. The Australian National University. hdl:1885/40747. http://digitalcollections.anu.edu.au/handle/1885/40747. 
  5. ^ Franke, Jens (2006), On RSA 200 and larger projects, http://www.hyperelliptic.org/tanja/SHARCS/talks06/Jens_Franke.pdf 
  6. ^ Kleinjung, Thorsten (October 2006). “On polynomial selection for the general number field sieve”. Mathematics of Computation 75 (256): 2037–2047. doi:10.1090/S0025-5718-06-01870-9. https://www.ams.org/mcom/2006-75-256/S0025-5718-06-01870-9/S0025-5718-06-01870-9.pdf 2007年12月13日閲覧。. 
  7. ^ Paul Leyland (December 12, 2003). “NFSNET: the first year”. Presentation at EIDMA-CWI Workshop on Factoring Large Numbers. August 9, 2011閲覧。
  8. ^ “Welcome to NFSNET” (April 23, 2007). October 22, 2007時点のオリジナルよりアーカイブ。August 9, 2011閲覧。
  9. ^ “About NFSNET”. May 9, 2008時点のオリジナルよりアーカイブ。August 9, 2011閲覧。

参考文献

[編集]
  • 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. ISBN 0-387-25282-7. Section 6.2: Number field sieve, pp. 278–301.
  • Matthew E. Briggs: An Introduction to the General Number Field Sieve, 1998
「https://ja.wikipedia.org/w/index.php?title=一般数体篩法&oldid=95777045」から取得