【初心者歓迎】C/C++室 Ver.78【環境依存OK】

一般数体篩法のオープンソース GGNFS
素因数分解には試し割り法, モンテカルロ法, 楕円曲線法, 二次篩法など多数のアルゴリズムが存在するが，その中でも一般数体篩法は100 桁以上の数を分解するには現在知られる最速のアルゴリズムである．
2005年には 200桁の数(rsa200)が一般数体篩法で分解された．本研究では，オープンソースの一般数体篩法ソフトウェアGGNFSについて，性能測定を行なう．
http://cryptology.cocolog-nifty.com/blog/2008/01/ggnfs_b47a.html

ここでは、素因数分解のための各種アルゴリズムについて解説する。対象は、以下のとおり。
Brute force method
ρ method（Pollard, Brent）
p-1 method
p+1 method
連分数法
複数多項式二次ふるい法
楕円曲線法
http://www.asahi-net.or.jp/~kc2h-msm/mathland/math12/index.htm

まず、素因数分解のためのプログラムを入手する必要がある。
Windows PC 上で動作する主なものとしては、
factor (Windows (DOSプロンプト))
ppmpqs (Windows (DOSプロンプト), Linux)
UBASIC (Windows (DOSプロンプト))
SNFS (Windows (DOSプロンプト)) 等がある。
http://www.asahi-net.or.jp/~kc2h-msm/mathland/matha1/howto.htm


分解するにあたっての方針（戦略）について
まず、速いマシンを長時間利用できる場合、90桁以下の数をppmpqsで分解することを薦める。これは、時間さえかければ、確実に分解できるというメリットがある。
マシンがそれ程速くない場合、途中で中断しなければならない場合、90桁以上の数を対象とする場合は、GMP-ECMを使うことを薦める。
http://www.asahi-net.or.jp/~kc2h-msm/mathland/matha1/howto.htm