About these numbers

(1997/08/07, 2008/04/23 更新)

この章では大きな数の素因数分解データを掲載する。

平成元年 (1989年) 頃、

ハード:NEC PC-9801VX2 + PC386D (ボード i80386 16MHz)
ソフト:UBASIC (Ver 8.2)

の環境でスタートしたが、その後、ハード・アルゴリズムの進歩に伴い、 その時点での最良のハード・アルゴリズムで、現在も計算が進んでいる。
また当初は個人で得られた結果を公開していたが、Web公開後、全世界からデータが集まるようになり、 現在では、現時点での最新の結果の公開し、共有することを目的としている。

ここに掲載しているデータに関しては、(原理的に誰でも発見可能なものなので)著作権・所有権はないが、
転載・引用にあたっては(発見者に対して敬意を払う意味で)出典元の明記をお願いしたい。


素数探査・素因数分解に関しては、以下の2つの方針がある。

ある数 An に対し、An を素数とするようなnを求めていく。

例.メルセンヌ素数の探査、等

ある上限値Mに対し、M以下の全ての An に対し素因数分解を行う。

例.円分数の素因数分解、Cunningham Project 等

ここでは、2番目の方針を取り、

255桁以下の全ての数についての素因数分解の表作成

を行うこととした。

基礎考察 …… brute force method (しらみつぶし法)で何桁ぐらいまでが分解可能か

(1999年に書いたものなので、計算環境等がかなり古いが、 計算量見積もりのロジックについては現在でも使える。 実際に当時に比べて CPU性能は1桁以上あがっているが、 しらみつぶし探査の場合、10倍速くなっても、1桁しか探査範囲が増えない、 という事実を噛みしめて欲しい。)

素因数分解の最も primitive な方法は brute force method (しらみつぶし法)である。
即ち、素因数分解したい数nに対して、nの平方根以下の数でしらみつぶし的に割ってみることにより、
素因数を求める方法である。この方法で何桁の数まで分解可能かを見積もってみる。

<前提条件>

この条件のもとでは、1秒間に

400×106×(4+4+2)= 4×109

のループが可能。このマシン上でプログラムを1日24時間、10日間に渡り無停止で動作させると、
ループ回数は、

4×109×60×60×24×10 = 3.456×1015

のループが可能。素数定理によりn番目の素数を

prm(n) ≒ n * log(n)

で近似すると、割る候補の最大数は、

107.7364×1015= 1.1×1017

これ以下を平方根とする数が分解可能となるので、最大数は

(1.1×1017)2= 1.21×1034= 35桁

となる。

パーソナルな環境で実行する場合は、使えるマシンのMIPS値はせいぜい20MIPSぐらいであろう。
また、プログラムのメインループは控えめに見積もっても上記の10倍は確実に越す。
この条件で上記の値を修正すると分解可能な最大数は、27桁ぐらいとなる。

逆にハードの性能が10倍に上がったとしても、分解可能な桁数は2桁しか上がらない。

要するにbrute force methodはlog(n)のオーダでしか処理向上は望めないため、大きな数の分解には向かない。

以上の議論により、

ということを理解して欲しい。

素因数分解今回使用したアルゴリズム

ρ Method (ρ法)

UBASICでは RHO(RHOX) の名称でインプリメントされている。
基本的にはモンテカルロ法であり、算出される因数はN,pの大きさには無関係であるが、
経験的には10桁以下程度の大きさの因数pを算出することが多いため、
素因数分解の初期フェーズとして使われることが多い。

P−1 method(P−1法)

以前のUBASICでは ECMXの初期フェーズで、これがインプリメントされていた。
数学的にはフェルマーの小定理を根拠としており、最も理解しやすいアルゴリズムである。
算出される因数pに対し、p−1が小さい素因数の積で構成されているものを対象とするため、
20桁以下ぐらいの素因数pの算出が可能であり、値によってはもっと大きな素因数も算出されることがある。
(筆者の経験では29桁の素因数を算出したことがある)。
ρ法の次のフェーズとして、20桁程度までの素因数をたたき出す時に使用することが多い。

Elliptic Curve Method (楕円曲線法)

UBASICでは ECMX の名称でインプリメントされている。
数学的には、楕円曲線 y2=x3+ax+b 上の有理点が、
mod N で考えた場合のある演算に対してアーベル群を作るため、
Nよりも小さい位数で0(mod N)となる場合があり、
その時の位数mとNのgcd をとることにより、Nの素因数を算出する方法である。
複数多項式2次ふるい法で分解できない桁数の数に対して用いる。
30桁以下程度の素因数を算出する。

Multiple Polynomial Quardratic Sieve(複数多項式2次ふるい法)

UBASICでは MPQSX の名称でインプリメントされている。
数学的には、フェルマーの方法の拡張版であり、

2−y2≡0(mod N)

の解を多数構成し、求める。
ある桁数以下の数を確実に分解するため、小さい数についての素因数を求める場合、
または、p−1法、楕円曲線法で小さい因数は出しきったと思われる数について、 完全分解を求めたい時に適用する。

Number Field Sieve(数体ふるい法)

2005年頃から、プログラムが公開されるようになった。
一般の数に関して、100桁を越えると、複数多項式2次ふるい法で分解するよりも、 一般数体ふるい法でやった方が速い。 また、分解対象の数が、係数の小さい6次以下の多項式で表現できる場合、 特殊数体ふるい法が絶大な威力を発揮し、Pentium 4 マシンで、 160桁ぐらいまでの分解が可能である。


戻る (12章
 素因数分解アルゴリズム)
目次 (日本語)  
  index (English) What's new

E-mail : kc2h-msm@asahi-net.or.jp
三島 久典