素因数分解プロジェクトへの参加方法

この頁では、当Webサイトでデータ管理を行っている、以下の２つの素因数分解プロジェクト、

1. 円分数
2. その他のいろいろな数

への参加方法について説明する。

素因数分解プログラムの入手方法

まず、素因数分解のためのプログラムを入手する必要がある。
Windows PC 上で動作する主なものとしては、

• factor (Windows (DOSプロンプト))
• ppmpqs (Windows (DOSプロンプト), Linux)
• GMP-ECM (Windows (DOSプロンプト), 各種ＯＳ)
• UBASIC (Windows (DOSプロンプト))
• SNFS (Windows (DOSプロンプト))

等がある。それ程大きなプログラムではないので、全て入手しておいた方がよい。
Windows上で動作するものがほとんどだが、一部のものは、Linux上でも動作する。

各プログラムの使い方

ここでは、主に使用する３つのプログラム、GMP-ECM、factor、ppmpqs の使用方法について解説する。

2.1 GMP-ECM（楕円曲線法による素因数分解）

1. 分解する対象の数をファイルに書き込んでおく

例．ファイル名 : factor.in

8624
136550853352821811366253623656516073112302676378311560842973907592252962763687083923452657
8764
152195707403437912897406545454458092776403602061547959775141647424210884585390426678591103
8879
158249565224375432199357132722329795501963539776390956783312994123005440892475715810884327

......

この例は、8624、8764、8879 の分割数の未解決の合成数 1365…、1521…、1582…、
を分解するためのものである。8624、8764、8879 自身は分解対象ではないので記入は不要だが、
分解結果を見るときのための目印として、入れておく。
ファイル名は任意。

2. DOSプロンプトから以下のように入力する

（プログラム ecm4c.exe をディレクトリ C:\tmp に置いている場合。
分解対象の数を格納したファイル factor.in も同一ディレクトリにあるものとする。）

C:\tmp>ecm4c 250000 < factor.in >> factor.out

250000は、楕円曲線法におけるB1の値を表す。とりあえず、固定値と思ってよい。
この他に、内部的に乱数が取られるため、実行結果は毎回異なる。

これを実行すると、factor.in のデータを全部処理した時に、素因数が見つかる／見つからない、
に関わらず終了してしまうので、以下のようなバッチファイルを作成し、起動するとよい。

ファイル名：ecm.bat

＜中身＞

:L1
ecm4c 250000 < factor.in >> factor.out
goto L1


3. factor.outに以下のようなものが出力される

（この例では、B1=400000としている）

GMP-ECM 4c, by P. Zimmermann (Inria), 16 Dec 1999, with contributions from
T. Granlund, P. Leyland, C. Curry, A. Stuebinger, G. Woltman, JC. Meyrignac,
A. Yamasaki, and the invaluable help from P.L. Montgomery.
Input number is 8624 (4 digits)
Found probable prime factor of 1 digits: 2
Composite cofactor 4312 has 4 digits
Input number is 136550853352821811366253623656516073112302676378311560842973907592252962763687083923452657 (90 digits)
Using B1=400000, B2=85072680, polynomial x^6, sigma=2072540533
Step 1 took 82880ms for 5182971 muls, 3 gcdexts
Step 2 took 46580ms for 2568314 muls, 11119 gcdexts
********** Factor found in step 2: 789163804885016259005100583
Found probable prime factor of 27 digits: 789163804885016259005100583
Probable prime cofactor 173032331827126455948910914726285190972740665404807018076330279 has 63 digits
Input number is 8764 (4 digits)
Found probable prime factor of 1 digits: 2
Composite cofactor 4382 has 4 digits
Input number is 152195707403437912897406545454458092776403602061547959775141647424210884585390426678591103 (90 digits)
Using B1=400000, B2=85072680, polynomial x^6, sigma=1066864455
Step 1 took 83160ms for 5182971 muls, 3 gcdexts
Step 2 took 47070ms for 2568314 muls, 11119 gcdexts
Input number is 8879 (4 digits)
Using B1=400000, B2=85072680, polynomial x^6, sigma=5521
Step 1 took 5000ms for 5182971 muls, 3 gcdexts
********** Factor found in step 1: 8879
Found input number N
Input number is 158249565224375432199357132722329795501963539776390956783312994123005440892475715810884327 (90 digits)
Using B1=400000, B2=85072680, polynomial x^6, sigma=2129199313
Step 1 took 82880ms for 5182971 muls, 3 gcdexts
Step 2 took 47180ms for 2568314 muls, 11119 gcdexts

素因数が見つかると、11行目の、

********** Factor found in step 2: 789163804885016259005100583

ように出力される。
この例では、見つかった 7891...が27桁の素数であり、 残った因子 1730...が63桁の素数となっている。
もちろん、見つかった因子及び残った因子が合成数となる場合もある。

2.2 factor

ρ法、p-1法、楕円曲線法、複数多項式２次ふるい法を順に適用して、分解する。
プログラム実行中にエスケープキーを叩くと、楕円曲線法の処理をスキップして、
複数多項式２次ふるい法の処理に移ることができる。

使い方は、GMP-ECM のようにファイルの中に分解対象の数を書き込んでおき、

C:\tmp>factor < factor.in

とする。出力結果は、factor.out に追加書き込みされる。
85桁ぐらいまでの数を分解するのに適している。

2.3 ppmpqs

上記 factor の、複数多項式２次ふるい法の部分のみを抜き出したもの。

使い方は、 factor と同じく、ファイルの中に分解対象の数を書き込んでおき、

C:\tmp>ppmpqs 64 < factor.in

とする。64 は２次キャッシュのサイズであり、Pentium、Pentium MMX クラスのCPUなら、
64または、32程度にしておくとよい。デフォルトは128（現時点では、この値を使うと遅くなる）。
出力結果は、mpqs.log に追加書き込みされる。

factorとの相違点は、

• 中断・再開始ができる。
  処理の途中で、Break (Ctrl + Pause) を押すことにより、中間結果がファイルに出力される。
  （電源を切ってもよい）
  再開始は、起動時と同じコマンド、

  C:\tmp>ppmpqs 64 < factor.in

  を入力する。

• ppmpqsは、小さい数の素因数分解ができない。
  30桁ぐらいまでの数を入力すると、abend する。
  また、分解結果に10桁以下程度の数が含まれていると、abend する。

80桁〜93桁の数の分解にかかる時間についての詳細データはこちら。

対象となる数の選び方

3.1 円分数

円分数とは、円分多項式 Φn(x) に、適当な n, x を代入した値のことである。
大雑把に云うと、xⁿ - 1 のことである（というか、この式を因数分解したときの、各既約因子）。
円分数 Φn(x) の計算方法については、こちらに UBASIC 用のプログラムを載せている。

まず、現在未解決のものは、Factorizations of Cyclotomic Numbers の表から辿ることができる。
例えば、n=75 の系列を見ると、

(75 300 (1201 47701) (P 92))
(75 301 (4951 47932201 130242047851) (P 77))
(75 302 (601 82351 437401 74507101 1762578999901) (P 66))
(75 303 (4051 599551) (C 90))
(75 304 (60606151) (C 92))
(75 305 (601) (P 97))
...

となっている。(P nn) は nn桁の素数、 (C nn) は nn桁の合成数を表す。
例えば、

(75 303 (4051 599551) (C 90))

は、n=75、x=303 のときの円分数が、素因数 4051、599551を持ち、残りが90桁の合成数である、
ということを表している。
よって、この数を分解したいときは、

1. 上記プログラムにより、n=75、x=303 のときの円分数を求める
2. それを、素因数 4051、599551で割る
3. 割った結果（90桁の合成数）をファイルに書いておき、上記素因数分解プログラムにかける

とすればよい。

3.2 その他のいろいろな数

Appendix 1. 素因数分解結果から辿ることができる。
こちらの方は、各ファイル内に具体的な数字で表記しているので、それをそのまま入力ファイルとすればよい。

その他

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

• 今のパソコンの性能を考えるなら、プロンプトが１回点滅する間に、
  CPU が 10,000,000回ぐらいは、空回りしているはずである。
  自宅、学校、会社のパソコンを単なるスクリーンセーバーマシン、
  或いはフリーセルマシンにするぐらいなら、バックグラウンドでGMP-ECMを流して欲しい。

• 新しい素因数が見つかったら、三島　久典 まで連絡して下さい。