素因数分解問題評価報告書

２００４年１月２３日

日本電信電話株式会社
青木 和麻呂植田広樹
内山成憲

素因数分解問題評価報告書

日本電信電話株式会社

2004 年 1 月 23 日

1

前書き

RSA 暗号の安全性は素因数分解の困難性に基づいている。素因数分解の実験
はいろいろと行われているが、単発的であり系統だったものがほとんどない。そのため実際に RSA 暗号に使われるような大きさの数を分解するために必要な時
間やハードウェアの規模について予測することが困難であった。そこで本報告書ではひとつのハードウェア環境及び同一のソフトウェアで一連の数を同一の方法
で素因数分解することによって各種のパラメータを決定することを目的とする。
なお本稿では、数体ふるい法の詳細については文献 [LL93, IK03] に譲ることとし、詳細には立ち入らない。

2

分解する対象RSA Data Security 社が提供していた旧 RSA factoring challenge の問題から
100, 110, 120, 130, 140, 150 桁の数を扱うことする1 。これらに 90 桁の数を一つ加えたものは次の通りである。
GNFS-90 =
15790232388367774953515652666819452783828744007661\
0848955946406020423172714525170482706767
RSA-100 =15226050279225333605356183781326374297180681149613\
80688657908494580122963258952897654000350692006139
RSA-110 =35794234179725868774991807832568455403003778024228\
22619353290819048467025236467741151351611120450406\
0317568667
RSA-120 =22701048129543736333425996094749366889587533646608\
47800381732582470091626757797353897911515740491667\
47880487470296548479
RSA-130 =
18070820886874048059516561644059055662781025167694\
01349170127021450056662540244048387341127590812303\
371781887966563182013214880557
RSA-140 =21290246318258757547497882016271517497806703963277\
21627823338321538194998405649591136657385302191831\
6783107387995317230889569230873441936471
RSA-150 =15508981247834844050960675437001186177065454583099\
54306554669457743126327034634659543633350275777290\
25391453996787414027003501631772186840890795964683
1

ただし現 RSA 社は現在では別の系統の数を challenge 問題としている。

1

以下では、上記 90 桁から 150 桁の数を実際に分解することにより適切なパラメー
タを選択することを試みる。

3

使用するハードウェア
今回の実験では、全て次の構成の PC を用いた。

Pentium 4 (Northwood), 2.53GHz, FSB 533MHz, Intel Desktop Boards
D850EMV2, i850e chip set, 1GB RDRAM, PC800, FreeBSD 4.7RELEASE-p13, Intel Compiler 7.1 (Build 20030617Z)
以下のデータで、ふるい処理は単純に台数による並列化が可能なので、時間は1 台に積算した値を提示した。線形代数処理は 16 台の PC を 100baseT 全二重のswitching HUB で接続を行なった場合の実測を実行時間とした。その他の処理については、全体に占める割合が少ないので、特に算出していない。

4

記号n: 分解する数。RSA-100 など。
f (x): 数体を定義する多項式 (∈ Z[x])d: deg f
M : f (M ) ≡ 0 (mod n)(M ∈ Z)s: 傾斜 (skew)
rp: rational 側の factor base の上限
rlp: rational 側の large prime の上限
ap: algebraic 側の factor base の上限
alp: algebraic 側の large prime の上限
nq : special-q の個数
qs: 最小の special-q (およそ π(ap) = π(qs) + nq )(a, b): line sieve におけるふるい領域 (|a| ≤ ha , 0 < b ≤ hb )(c, d): lattice sieve におけるふるい領域 (|c| ≤ hc, 0 < d ≤ hd)

5

GNFS の多項式選択

ここでは RSA-100 を例として多項式の作り方を具体的に述べる。他の数については、ほぼ同様の処理を行なった。多項式選択には、PC 1 台で分解対象が小さいものから大きいものにかけて数分から 1 日程度の時間をかけた。
今回用いた方法は、基本的に Montgomery-Murphy の方法 [M99] を用いるが細部についてはかなり省略している。

2

5.1

ノルムの大きさの判定基準
f (M ) ≡ 0 (mod n)となる d 次多項式 f と自然数 M が与えられたときこの多項式に対して領域

S = {(a, b)| − ha ≤ a ≤ ha , 1 ≤ b ≤ hb }における f の大きさ SIZE(f, S) を

1
SIZE(f, S) = log(hb M ) + log
2

µZ

¶
d 2

S

|f (−a/b)(−b) | dadbと定義する。これが小さいほど S において |a + bM | も |f (−a/b)(−b)d | も小さ
い傾向があることを示すと考えられる。

5.2

最高次係数の動く範囲

d = 5 としf (x) = a5 x5 + a4 x4 + a3 x3 + a2 x2 + a1 x + a0とする。
d = 5 の場合は a5 は 1 から n1/6 までを動きうる。S をこれまでの実験結果から妥当と思われる値に定め、SIZE 評価によるいくつかの実験の結果 n0.090 付近に最適な値が多い傾向があることがわかった2 。そこでこれを中心として前後を調べることにする。RSA-100 では n0.085 から n0.095 までを調べた。つまり a5 の範囲は次の通りである。

(amin=) 269475891 ≤ a5 ≤ 2644513508 (= amax)
55
さらに射影根が多くなるようにするため a5 が小さな素数のべき乗で割れるよ
うにしておく。RSA-100 では、多項式選択の時間3 を考え

23 · 32 · 5 · 7 = 2520 (= astep
5 )の倍数とする。したがって a5 は
step
(amax
− amin= 942475
55 )/a5

個を動くことになる。

5.3

ノルムの小さな多項式の選択

a5 を決めても M には自由度があるので a4 以下は変化する。その中で algebraic
側が最小になるものを探す。後に 1 次係数が M 程度の大きさの 2 次式を加える
24 次式では 0.127 近辺が良く、6 次式では 0.085 近辺が良いようである。ただし、理論的な裏づけがあるわけではないので一般的なことは何も言えない。
3
小さくとると、より多くの多項式を試せ、より良い多項式を生成できる可能性があるが、時間がかかる。

3

ことを考慮すると a1 は M 程度の大きさであることが適当である。係数の傾斜(skew) を s とすると
a1 ≈ a5 s4 ≈ Mである。よって s はs ≈ (M/a5 )1/4を満たす。この s によっておおよそ|a4 | ≤ a5 sとなることが要請される。
ここで a4 の調整は M の平行移動によって行われる。M を M + k に平行移動
すると a4 は a4 + 5ka5 に変わる。最初の a4 は 0 に近いから −s ≤ 5k ≤ s である。
すなわち −s/5 ≤ k ≤ s/5 となるが余裕をみて−s ≤ k ≤ sとする。まとめるとM0 = round((n/a5 )1/5 )とし

M = M0 + k,−s ≤ k ≤ s

で M を動かすことにする。
そして各 M に対し n を M -進展開して a4 以下を決める。この多項式 f に対して
SIZE(f, S) を計算する。ただし領域 S は面積 2ha hb を一定とし ha /hb を SIZE(f, S)が最小になるようにとるものとする。RSA-100 の場合 S の面積は過去の結果から242 とした。
このように a5 , M を動かして SIZE(f, S) が小さなものをいくつか (10 個から100 個) 探す。

RSA-100 の場合 SIZE の一番小さな多項式は次のものであった。
f (x) =

5.4

2218671000+722975049906−113835927498852−13938430864062173+248440408936881498+419147805253061235

x5
x4
x3
x2
x

Murphy の α 関数

α 関数は (−b)5 f (−a/b) が同じ大きさの平均的な数よりもどのくらい smooth になっているかを判定するものである。値が 0 ならば普通であり、小さい (つまり負の値) ほど smooth であることを示す。
次のようにして計算される。まず (−b)5 f (−a/b) が p の何乗で割れるかの平均
vp (f ) は4

計算法 1) p が g の判別式を割らなければ射影型を含めて f (x) ≡ 0
異なる解の個数を qp とすれば平均しておよそ(mod p) のp
vp (f ) = qp 2
p −1
である。
計算法 2) p が g の判別式を割る場合は領域内のランダムな点 (a, b) を選んで実際に (−b)5 f (−a/b) の p べき指数を計算して平均を求める。RSA-100 の場
合は 20000 個の点 (a, b) について計算した。
普通のランダムな数は素数 p で平均してstdp =

1p−1回割れる。この 2 つのべき指数の差の分、つまり pstdp −vp (f ) だけ大きい約数を(−b)d f (−a/b) は普通のランダムな数よりも持つことになる。そこで log をとって和を作ったものをX
α(f ) =
log p (stdp − vp (f ))pと定義する。
RSA-100 の計算では最初の 20 個の素数に対しては計算法 2 を用い、それ以上では計算法 1 を 1000 番目の素数まで用いて和をとった。

5.5

一次式を加えて α 関数が最小となる多項式を選択する

f , M が与えられたとき f (x) に 2 次式 (j1 x + j0 )(x − M ) を加えた多項式
g(x) = f (x) + (j1 x + j0 )(x − M )を作る。g(M ) ≡ 0 (mod n) でもあるので g, M も n に対する GNFS 用の多項式として使える。
ここで (−b)5 g(−a/b) が小さな素数 p で多くの約数を持つようにする。その判定基準は上記の α 関数である。
RSA-100 では −20 ≤ j1 ≤ 20, −212 ≤ j0 < 212 の範囲で調べた。
t mod p を固定するとき

f (t) + (j1 t + j0 )(t − M ) ≡ 0(mod p)となる j1 , j0 は mod p で定まるので j1 を固定して j0 の最小の値を決めればそこか
ら step p での “ふるい” で調べることができる。具体的には log p を加えて行く。
RSA-100 では最初の 50 個の素数について “ふるい” を行った後で値が一番大きいところから j1 , j0 を決定した。この g に対して α(g) を計算する。

5

5.6

ノルムを最小にする

g, M に対して M を微小変化 (±200) させて SIZE(g, S) が最小となるようにする。変化があればこの g を新たな f として前節から繰り返す。変化がなければ g,
M を出力して終了する。
RSA-100 の場合は 2 回の繰り返しで次の多項式を得た。
g(x) =

476148960+33466236556−95242541476020+24540020572973215−3475579183967599680−2599927782355220688836

x5
x4
x3
x2
x

これは SIZE のみによる順位で第 5 位であった多項式に−(x + 2112)(x − M )を加え、M を 1261737131078349311 から 1261737131078349405 へ 94 だけ平行移動したものである。

6

GNFS の factor base およびそれに関連するパラメータの選択

今回のパラメータ選択において、ap については、qs = rp とし、およそ π(ap) =π(qs) + nq とした。また、ある special-q に対する algebraic 側の factor base の上
限は、小さい方から i 番目の special-q を qi とおいたとき、q0.95i とした。

6.1

方針

ここではすべてを lattice sieve で行うことにする。RSA-100, RSA-110 等ではline sieve を併用した方が短時間で終えることができるがより大きな数に対しては line sieve はほとんど役に立たず、より大きな数に対する実行時間を類推するには小さな数に対しても lattice sieve のみでの実行時間を計測することが適切な結論を出すものと考えられる。以下、この節では lattice sieve のみを用いること
とする。

6.2

パラメータのとり方

信頼できるデータを下にして、未知の部分は単純な補間による。

RSA-100 については先行して、かなり大規模にパラメータを変化させる実験から最適と思われるパラメータが得られているので、その結果
rp = 0.25e6, ap = 3.75e6, nq = 0.15e6, rlp = 17e6, alp = 38e6,
hc = hd = 211
6

を基礎にする。もちろん今回生成の多項式とは異なるものを利用しており、ほかのパラメータも違うのでこれをそのまま使うことは必ずしも適当ではない。

RSA-140 CWI のレポート [CDL+ 99] によると
rp = 3.5e6, ap = 12.17e6, nq = (0.51e6?), rlp = 500e6, alp =
1e9, hc = hd = 213である。ただし、lattice sieve で 55%の relation を、line sieve で 45%の relation を得ているので、lattice sieve のみにするには nq を 1.0e6 にする必要がある。それには

rp = 3.5e6, ap = 20.08e6, nq = 1.0e6とすれば良い。必要な relation の個数は 67e6 個である。
これを補間する。ただし安全を見てやや多めにする。

rp
0.3e6
4.0e6

RSA-100
RSA-140

この間を単純に対数比例配分する (=1.91 倍/10 桁)

RSA-100
RSA-110
RSA-120
RSA-130
RSA-140rp
0.3e6
0.57e61.01e62.09e6
4.0e6

同じく rlp は 2.33 倍し、alp はその 2 倍。

RSA-100
RSA-110
RSA-120
RSA-130
RSA-140

rp
rlp
alp
0.3e6
17e6 34e6
0.57e6 40e6 80e6
1.01e6 92e6 184e6
2.09e6 215e6 430e6
4.0e6 500e6
1e9special-q の個数について
nq = 必要な relation の個数/1 つの q で得られる relation の個数であるが分母は hc, hd のとり方によっても変化するのでここまでのところでは決められない。
必要な relation の個数は RSA-140 では 67e6 個である。RSA-100 では記述がな
いが実験してみると 1 つの q で平均 23 個の relation がえられるので 23 × 150e3 =
3.5e6 個とする。少し多めにとって対数比例配分する。

7

RSA-100
RSA-110
RSA-120
RSA-130
RSA-140

6.3

rp
rlp
alp
0.3e6
17e6 34e6
0.57e6 40e6 80e6
1.01e6 92e6 184e6
2.09e6 215e6 430e6
4.0e6 500e6
1e9

relation
4.0e6
8.2e6
16.7e634.2e670.0e6log2 hc
11
12?
12?
13?
13

log2 hd
11
11?
12?
12?
13

relation/1q
23

nq
174e3

67

1.04e6

RSA-150 の戦略

このまま RSA-150 の類推をしたいところだが 158 桁 (以下 GNFS-158 と書く) の
分解 [BFK02] のパラメータがこれまでのものと著しく異なるので両者の折衷にならざるを得ない。実験で補正するしかないであろう。

rp
rlp alp relation log2 hc log2 hd relation/1q nq
RSA-150 12.0e6 2e9 2e9 140e6? 13
13
67 2.0e6?
GNFS-158 30.0e6 4e9 4e9 309e6
13
13
59 5.2e6(a)GNFS-164 40.0e6 4e9 4e9 458e6
1413
50 9.1e6(a)注 (a) line sieve の分も lattice sieve で行った場合の補正を加えた。
なお、GNFS-164 の結果は [AUK+ 04] にある。
実験の結果 rp を補正する。RSA-140 の値はあくまで line sieve と lattice sieveを併用することを前提に決定されているものなので最適ではなくても不思議はな
い。RSA-130 までの実験結果によっては後で RSA-140 を修正する。

RSA-100
RSA-110
RSA-120
RSA-130
RSA-140

6.4

rp
rlp
alp
0.3e6 18e6 40e6
0.8e6 40e6 80e6
1.6e6 92e6 184e6
3.0e6 215e6 430e6
4.0e6 500e6
1e9

relation
4.0e6
8.2e6
16.7e634.2e670.0e6log2 hc
11
12?
12
13?
13

log2 hd
11
11?
11
12?
13

relation/1q
23

nq
174e3

25

668e3

67

1.04e6

RSA-130 の hc, hd の決定

hc, hd を大きくするとひとつの special-q においてふるいの時間は増えるが、得られる relation の個数も増える。この最適値を求めたい。なお、この節での計算機実験は Pentium 4 [3.0GHz] での実行時間であることに注意せよ。
6.4.1

hc = 212 , hd = 211 の場合

最初の 100 個の q での効率は2202 relation/96 秒 = 22.94と高い。しかし得られた個数が少ないので 34.2e6/22 = 1.55e6 個の q を用いるこ
とになる。

8

1550001 番目の q から 100 個の q に対する効率は 2233/171 = 13.06 とかなり下がる。
中間点 (750001 ∼ 750100 番目の q) では 133 秒で 2285 個の relation が得られているので、これらを平均して(2202 + 2285 + 2233)/(96 + 133 + 171) = 16.8
が全体の効率である。

6.4.2

hc = 212 , hd = 212 の場合それぞれ最初、560001 番目、1120001 番目から 100 個の q では

1
5600011120001

生成 relation 数
3046
3492
3471

実行時間 [秒]
159
195
223

となるので効率は (3046 + 3492 + 3471)/(159 + 195 + 223) = 17.35 となる。

6.4.3

hc = 213 , hd = 212 の場合
1371701743401

生成 relation 数
4617
5136
5343

実行時間 [秒]
281
317
344

となるので効率は (4617 + 5136 + 5343)/(281 + 317 + 344) = 16.03 である。
結論として hc = hd = 212 を採用する。

RSA-100
RSA-110
RSA-120
RSA-130
RSA-140

7

rp
rlp
alp
0.3e6 18e6 40e6
0.8e6 40e6 80e6
1.6e6 92e6 184e6
3.0e6 215e6 430e6
4.0e6 500e6
1e9

relation
4.0e6
8.2e6
16.7e634.2e670.0e6log2 hc
11
12
12
12
13

log2 hd
11
11
11
12
13

relation/1q nq
23 174e3
25 330e3
25 668e3
33 1.03e6
67 1.04e6

実験データの報告対象となる数に対しては 5 次式がもっとも有効であると考えられる。この実験
で最適な値を絞り込むことにする。また、対象とした数に対しては 4 次式はまだ有効であるが大きくなるにつれて 5 次式との差が大きくなるはずである。実験によってこのことを確認する。さらに、対象とした数に対しては 6 次式は有効ではない。しかし数が大きくなるにつれてその効率は 5 次式に近づいて行くはずである。実験によってこのことを確認する。但し、評価期間の制約から 4 次式と 6 次
式は 90, 100, 110, 120 桁のみの実験となった。

9

7.1

多項式

以下に、実験に用いた多項式 gnfs90 から rsa150 およびそれに対応する M を示す。5 次多項式で RSA-100 及び RSA-110 については、最初に生成した多項式での実験結果から、明らかに性能が悪そうなので生成し直した。生成し直した多項式を、それぞれ rsa100f、rsa110g と表記する。なお、rsa140 は今回新たに生成することはなく文献 [CDL+ 99] の多項式をそのまま使った。

7.1.1

GNFS-90
gnfs90d4 =230700960− 1126041076− 2800530116008+ 361291922417541− 19404936952585372− 8090459983574955158
M = 14691556985141025

x5
x4
x3
x2
x

gnfs90d6 =
gnfs90d4 =
x4
x3
x2
x

384095471760− 241081261647426− 4687866717940381+ 268017730716567141252− 93491312408300772778865
M = 25321377834100183152

7.1.2

34739040− 700184704− 40151123010− 333940064067+ 8190990388272+ 241490187216714− 581408893208572
M = 40700066437843

x6
x5
x4
x3
x2
x

RSA-100
rsa100f =rsa100 =162177120+ 28143053314+ 23324146463349− 37091958614999369− 38913224302195502499+ 6320108185403991362425
M = 1565018714315923398

5

x
x4
x3
x2
x

10

476148960+ 33466236556− 95242541476020+ 24540020572973215− 3475579183967599680− 2599927782355220688836
M = 1261737131078349405

x5
x4
x3
x2
x

rsa100d6 =rsa100d4 =
x4
x3
x2
x

11280637368000+ 1297331842676166− 6398231616999999973− 3867985592992020706164− 5029809154814976597919529
M = 3408500839386006478662

7.1.3

54885600− 6171978062− 279021830192+ 7107344769942+ 230170783897105+ 12995121899819102− 1211347205408698220
M = 1739888725534017

x6
x5
x4
x3
x2
x

RSA-110

rsa110 =rsa110g =8806117320− 6602302439733− 10418783160743424+ 2509093800839550332+ 2444993039496642448884− 484899833751348621692744
M = 83522930105029420917

5

x
x4
x3
x2
x

2186636760+ 7090231275050− 7779420006796361− 7338302252559380692+ 2945060505193947891936+ 528370695182871756215992
M = 110358880444076439675

x5
x4
x3
x2
x

rsa110d6 =rsa110d4 =
63063320720400− 108858128876245362− 333714480816166136741+ 2151401060734002095936690− 1855021161851883623239525160
M = 867978684105357920487813

7.1.4

x4
x3
x2
x

3356406900− 129410945870+ 8416221526418+ 87105425158528− 5730778027746978+ 19623529153740031+ 1160691112322070568
M = 46916226934871871

RSA-120
rsa120 =1554355923120+ 279300728665360+ 235068853764040024− 366715788836593094− 19671660878164914170531− 6942209761632534501172599
M = 2709561965307563001574

11

x5
x4
x3
x2
x

x6
x5
x4
x3
x2
x

rsa120d6 =rsa120d4 =895498088284800+ 3413868460618755900− 24034697186813319912433− 284653018467662477380306552− 374222159601896067445067401260
M = 126181391268425470300909327

7.1.5

x4
x3
x2
x

6201111840+ 65538566248+ 69773963135376− 578627837775246− 345217686788156398+ 1982291106588495261− 73006857823750108920
M = 1822200063999191027

RSA-130
rsa130 =147039132240+ 871623037904469+ 3086117472198489675− 7719799519497061434782− 9743342795049257456352467+ 11536315812200841021988194190
M = 414867094746941900457767

7.1.6

x5
x4
x3
x2
x

RSA-140
rsa140 =439682082840+ 390315678538960− 7387325293892994572− 19027153243742988714824− 63441025694464617913930613+ 318553917071474350392223507494
M = 34435657809242536951779007

7.1.7

x5
x4
x3
x2
x

RSA-150
rsa150 =39579179880240+ 118091572936301268+ 99882037492763164770− 5644711233991594133565451− 17749003945730989474189029270+ 14495606942348552079748145328451
M = 1314084509932138154491813836
12

x5
x4
x3
x2
x

x6
x5
x4
x3
x2
x

7.2

factor base のパラメータ

今回利用した factor base に関するパラメータを表 1 に示す。RSA-140, RSA-150
は line sieve を併用した実験も行なったので、それを表 2 に示す。

gnfs90
gnfs90d4
gnfs90d6
rsa100rsa100f
rsa100d4
rsa100d6
rsa110rsa110g
rsa110d4
rsa110d6
rsa120rsa120d4
rsa120d6
rsa130rsa140rsa150

表 1: factor base のパラメータrp rlpap alps
qs
備考
300e3 9e6 833669 20e6 192 206951
800e3 10e6 823003 19e6 716 330859
150e3 6e6 2142353 80e6 20 836161
300e3 18e6 2746739 40e6 591 468109
300e3 18e6 1981711 40e6 369 424247
1200e3 18e6 12474757 40e6 1200 282797
300e3 12e6 4992019 160e6 53 1422221
800e3 40e6 6243553 80e6 600 1133857
800e3 40e6 3995743 80e6 848 1069603
2400e3 40e6 3773773 80e6 2812 589759
600e3 20e6 8072513 320e6 23 1496549
1600e3 92e6 12474757 184e6 321 2264707
4800e3 100e6 10322033 140e6 5886 1363513
1200e3 48e6 13379207 640e6 58 2060059
3e6 215e6 20319361 430e6 1882 4107643
4e6 1e9 20761397 1e9 3992 4505773 line sieve 併用
6e6 500e6 22960397 1e9 3992 4505773
19153333
空欄は上行と同一
12e6 2e9 49312987 2e9 4049 14830997 line sieve 併用
52864993
空欄は上行と同一

表 2: line sieve の factor base のパラメータrp rlpap alphahb
rsa140 8e6 1e9 16777216 1e9 335544320 32768
rsa150 12e6 2e960e6 2e9 335544320 80000

さらに得られた様々なデータを次に示す。

13

hc

hd

q_end
48 00037 00092 000

line
で得た
rel 数
0
0
0

lattice
で得た
rel 数
1 422 465
1 422 612
2 551 165

gnfs90
gnfs90d4
gnfs90d6

2 048
2 048
2 048

1 024
1 024
2 048

rsa100rsa100f
rsa100d4
rsa100d6

2 048
2 048
2 048
2 048

rsa110rsa110g
rsa110d4
rsa110d6

1 422 465
1 422 612
2 551 165

2 048
2 048
2 048
2 048

160 000
112 000
95 000240 000

000
0

3 879 533
3 053 728
2 736 929
5 329 204

3 879 533
3 053 728
2 736 929
5 329 204

2 048
2 048
4 096
4 096

2 048
2 048
2 048
2 048

340 000
200 000
220 000
430 0000000

7 425 275
6 752 059
6 185 022
10 228 570

7 425 275
6 752 059
6 185 022
10 228 570

rsa120rsa120d4
rsa120d6

4 096
4 096
4 096

2 048
4 096
4 096

650 000
580 000
720 000000

14 225 875
13 145 521
19 304 631

14 225 875
13 145 521
19 304 631

rsa130

4 096

4 096

1 000 000

026 975 303

26 975 303

rsa140rsa140g
rsa140g

8 192
8 192
8 192

8 192
8 192
8 192

1 000 000
1 130 000
904 000

10 168 552
00

69 296 581
65 393 900
51 340 137

79 465 133
65 393 900
51 340 137

rsa150rsa150

8 192
8 192

8 192
8 192

2 000 000
2 200 000

20 159 340
0

113 240 317
124 804 557

133 399 657
124 804 557

(s)

dup
rel 数

残
lost
rel 数 rel 数

total
rel 数

line
時間 (s)

lattice
時間 (s)

total
時間

gnfs90
gnfs90d4
gnfs90d6

186 588
136 101
228 736

1 235 877
1 286 507
2 322 429

0
0
0

0
0
0

14 35013 57046 62114 35013 57046 621

rsa100rsa100f
rsa100d4
rsa100d6

587 798391 235357 714584 401

3 291 735
2 662 493
2 379 215
4 744 803

0
0
0
0

0
0
0
0

79 63154 27155 155145 247

79 63154 27155 155145 247

rsa110rsa110g
rsa110d4
rsa110d6

1 271 941
948 123956 470
1 273 191

6 153 328
5 803 935
5 228 552
8 955 379

0
0
0
0

0
0
0
0

328 949
193 676
250 945461 685328 949
193 676
250 945461 685rsa120rsa120d4
rsa120d6

2 389 912
2 088 586
2 370 817

11 835 963
11 056 935
16 933 814

0
0
0

0
0
0

790 138
1 320 933
1 517 888

790 138
1 320 933
1 517 888

rsa1303 407 897

23 567 406

002 315 347

2 315 347

rsa140rsa140g
rsa140g

12 378 307
7 186 499
4 982 485

67 086 826
58 207 401
46 357 652

000838 45200

7 889 757
8 577 408
6 726 258

8 728 209
8 577 408
6 726 258

rsa150rsa15019 986 659
12 666 924

113 412 693
112 137 633

305
305

2 128 0890

18 642 834
20 597 260

20 770 923
20 597 260

14

free
rel 数

sc 前
rel 数

sc 前
FB 数

alprime0
要素数

rlprime0
要素数

gnfs90
gnfs90d4
gnfs90d6

2 363
13 750540

1 238 240
1 300 257
2 322 969

1 325 906
1 368 708
2 545 100

844 320818 391
2 146 731

481 593
550 316398 905rsa100rsa100f
rsa100d4
rsa100d6

6 411
5 273
24 960954

3 298 146
2 667 766
2 404 175
4 745 757

2 846 258
2 664 811
2 557 942
5 233 152

1 839 545
1 713 274
1 580 867
4 468 920

1 006 709
951 535
977 074765 319

rsa110rsa110g
rsa110d4
rsa110d6

12 286
11 44255 263
1 574

6 165 614
5 815 377
5 283 815
8 956 953

5 518 625
5 443 581
5 365 601
9 784 707

3 451 808
3 407 556
3 281 038
8 534 027

2 066 813
2 036 022
2 084 611
1 251 490

rsa120rsa120d4
rsa120d6

24 169126 435
3 524

11 860 132
11 183 370
16 937 338

11 738 886
10 928 533
18 512 122

7 463 338
6 178 137
15 707 493

4 275 555
4 750 423
2 805 427

rsa13047 43323 614 839

24 521 904

15 300 885

9 221 041

rsa140rsa140g
rsa140g

123 809
107 386
85 61367 210 635
58 314 787
46 443 265

68 974 717
55 664 003
50 556 075

36 705 191
34 607 162
31 063 425

32 269 518
21 056 835
19 492 644

rsa150rsa150210 243207 286

113 622 936
112 344 614

126 224 606
125 001 514

67 309 955
66 430 003

58 914 643
58 571 503

1-pass 後

1-pass 後

sc 後

sc 後

sc 後

sc 後

rel 数

FB 数

rel 数

FB 数

total wave. w

gnfs90
gnfs90d4
gnfs90d6

798 835
875 758
1 243 916

791 694859 333
1 232 301

331 876374 083
515 742330 872
373 082514 740

5 623 433
6 482 139
8 800 410

16.94417.32817.064rsa100rsa100f
rsa100d4
rsa100d6

2 519 116
1 850 290
1 594 376
2 552 375

1 971 985
1 704 727
1 585 057
2 545 446

424 478574 926
724 636
1 092 722

423 480
573 925723 634
1 091 719

7 356 036
10 087 790
12 848 598
18 881 757

17.33017.54617.73117.280rsa110rsa110g
rsa110d4
rsa110d6

4 606 507
4 207 271
3 688 857
4 776 194

3 731 140
3 581 036
3 481 925
4 729 413

893 009891 802
1 271 853
1 884 183892 011890 801
1 270 846
1 883 182

16 142 280
16 518 559
23 381 040
34 029 045

18.07618.52718.38318.060rsa120rsa120d4
rsa120d6

8 302 289
8 207 377
9 089 129

7 540 430
7 471 071
9 053 515

2 279 188
2 455 106
3 530 459

2 278 185
2 454 102
3 529 458

43 910 886
45 839 280
64 431 664

19.26618.67118.250rsa13015 596 081

14 838 636

4 563 119

4 562 121

87 722 757

19.224rsa140rsa140g
rsa140g

43 191 800
40 267 856
28 512 843

39 443 255
34 396 120
28 193 867

6 116 250
5 941 114
7 789 491

6 115 247
5 940 116
7 788 488

125 097 698
121 776 953
158 573 057

20.45320.49720.357

rsa150rsa15067 846 880
66 795 889

67 813 102
66 782 788

16 593 213
16 361 279

16 592 212
16 360 278

335 877 843
332 343 491

20.241
20.31215

lprimealprimerlprime cprime

20way
20way
merge 後 merge 後

20way
merge 後要素数

要素数

要素数 要素数

rel 数

FB 数

total w

gnfs905
gnfs90d4 11
gnfs90d6 5

203 034
207 051367 820

127 835
166 022146 91764
64
64

105 898
119 970
174 649

104 878
118 956
173 642

7 872 377
9 246 510
13 696 162

rsa100rsa100f
rsa100d4
rsa100d6

658
5272 978365 142403 691
789 496

150 496
208 778
319 937
302 222

64
64
64
64

163 437
190 616215 271
336 137

162 435
189 614214 257
335 114

13 487 097
16 664 599
20 079 506
33 891 248

rsa110rsa110g
rsa110d4
rsa110d6

7797571 425565 076714 237
1 366 085

320 579
325 720556 602517 090

64
64
64
64

318 428
304 917384 185528 397

317 427
303 916383 169
527 389

34 100 158
31 889 185
42 320 324
67 209 440

rsa120rsa120d4
rsa120d6

986

1 460 541
1 375 986
2 509 741

817 635
1 078 108
1 019 711

64
64
64

687 247741 068904 269

686 239740 055903 253

101 496 903
103 481 516
139 815 927

rsa1308

2 868 381

1 693 732

64

1 249 886

1 248 880

209 107 002

rsa140rsa140g
rsa140g

88
8

3 782 325
3 693 767
4 734 617

2 332 914
2 246 341
3 053 863

64
64
64

1 611 769
1 651 577
1 842 573

1 610 763
1 650 572
1 841 554

294 459 963
293 205 775
348 263 555

rsa150rsa1508
8

10 062 946
9 898 427

6 529 261
6 461 843

64
64

4 009 552
4 061 097

4 008 542
4 060 083

761 332 214
749 694 248

20way
merge 後ave. w

cut96 後rel 数

cut96 後FB 数

gnfs90
gnfs90d4
gnfs90d6

74.33977.07478.421

105 898
119 970
174 649

104 782
118 860
173 546

6 063 318
7 110 371
10 716 688

57.26
59.27
61.36

rsa100rsa100f
rsa100d4
rsa100d6

82.52287.42593.275100.826

163 437
190 616215 271
336 137

162 339
189 518
214 161335 018

10 648 753
13 181 907
16 089 914
27 513 589

65.16
69.15
74.74
81.85

rsa110rsa110g
rsa110d4
rsa110d6

107.089104.583
110.156
127.195

318 428
304 917384 185528 397

317 331303 820383 073527 293

27 768 070
25 682 013
34 490 578
55 904 354

87.20
84.23
89.78
105.80rsa120rsa120d4
rsa120d6

147.686139.638
154.6168687 247741 068904 269

686 143739 959903 157

84 825 348
87 282 307
120 238 399

123.43117.78132.97

rsa130167.301

1 249 886

1 248 784

178 678 686

142.96rsa140rsa140g
rsa140g

182.694177.630
189.108

1 611 769
1 650 654
1 841 611

1 610 667
1 649 553
1 840 496

253 592 913
251 695 742
302 854 189

157.34152.48164.45rsa150rsa150189.880184.604

4 009 552
4 061 097

4 008 446
4 059 987

665 517 429
653 770 042

165.98160.9816

cut96 後 cut96 後
total wave. w

block Lanczos (block 長 128) の処理時間 (16 台での並列処理)
rsa100rsa110rsa120rsa130rsa140rsa15000:07:19
00:28:49
02:24:15
08:47:28
15:07:39
101:31:17

表中の記号は次の通りである。

q end nq
dup rel 数 一意性処理で捨てた relation 数
rel 残数 total rel 数から dup rel 数を減じたもの
lost rel 数 本来あってはならないものだが、作業中に disk full などの理由で失ってしまった relation 数
sc 前 rel 数 一意性処理後の relation に、free relation を加えた relation の数
sc 前 FB 数 一意性処理後の relation で使われている large prime を含む factor baseの数
alprime0 要素数 sc 前 FB 数のうち、algebraic 側で使われている factor base の数
rlprime0 要素数 sc 前 FB 数のうち、rational 側で使われている factor base の数
1-pass 後 rel 数 singleton 処理で、singleton を 1 回落したあとの relation 数
1-pass 後 FB 数 singleton 処理で、singleton を 1 回落したあとの relation で使われている factor base 数
sc 後 rel 数 singleton 及び clique 処理により、残った relation 数
sc 後 FB 数 singleton 及び clique 処理後に残った relation で使われている factor
base 数sc 後 total w singleton 及び clique 処理後に残った relation で行列を構成した際の weight
sc 後 ave. w singleton 及び clique 処理後に残った relation で構成された行列の 1
relation 辺りの weightlprime 要素数 数体定義多項式の最高次係数の約数の個数 (factor base に含まれる)
alprime 要素数 sc 後 FB 数のうち、algebraic 側で使われている factor base の数
rlprime 要素数 sc 後 FB 数のうち、rational 側で使われている factor base の数
cprime 要素数 線形代数処理後の二次指標の調整で使うために algebraic 側の factor base から抜き出した素イデアルの個数で、常に 64 固定
1720way merge 後 rel 数 20-way merge を実施した後に残っている relation-set 数
20way merge 後 FB 数 20-way merge を実施した後に残っている relation-set で使われている factor base の個数
20way merge 後 total w 20-way merge を実施した後に構成した行列の weight
20way merge 後 ave. w 20-way merge を実施した後に構成される行列の 1 relationset 辺りの weightcut96 後 rel 数 20-way merge を実施した後に構成される行列から weight の重い
factor base を 96 個除いた後の relation 数であり、20way merge 後 rel 数に一致
cut96 後 total w 20-way merge を実施した後に構成される行列から weight の重
い factor base を 96 個除いた後の合計 weight 数
cut96 後 ave. w 20-way merge を実施した後に構成される行列から weight の重
い factor base を 96 個除いた後の 1 relation-set 辺りの weight

参考文献[AUK+ 04] K. Aoki, H. Ueda, Y. Kida, T. Shimoyama, and Y. Sonoda. A trialof GNFS implementation (Part I) — Summary. In 2004 Symposium on Cryptography and Information Security, number 2B1-3 in
SCIS’04. Technical Group on Information Security (IEICE), 2004. (inJapanese).
[BFK02]

F. Bahr, J. Franke, and T. Kleinjung. Factorization of 158-digit
cofactor of 2953 + 1. (available at http://www.crypto-world.com/
announcements/c158.txt), 2002.

[CDL+ 99] S. Cavallar, B. Dodson, A. K. Lenstra, P. Leyland, W. Lioen, P. L.
Montgomery, B. Murphy, H. te Riele, and P. Zimmermann. Factorization of RSA-140 Using the Number Field Sieve. In K. Y. Lam,
E. Okamoto, and C. Xing, editors, Advances in Cryptology — ASIACRYPT’99, Volume 1716 of Lecture Notes in Computer Science,
pp. 195–207. Springer-Verlag, Berlin, Heidelberg, New York, 1999.
[IK03]

T. Izu and Y. Kida. A Status Report of Integer Factorization. Transactions of the Japan Society for Industrial and Applied Mathematics,
Vol. 13, No. 2, pp. 151–165, 2003. (in Japanese).

[LL93]A. K. Lenstra and H. W. Lenstra, Jr., editors. The development of
the number field sieve, Volume 1554 of Lecture Notes in Mathematics.
Springer-Verlag, Berlin, Heidelberg, 1993.

18

[M99]B. A. Murphy. Polynomial Selection for the Number Field Sieve Integer Factorisation Algorithm. PhD thesis, Australian National University, 1999. (http://web.comlab.ox.ac.uk/oucl/work/richard.
brent/ftp/Murphy-thesis.p%s.gz).

19