GNFS176
2005年4月22日、我々のチーム(下記)は 11^281+1 の約数である 176桁の合成
数を「一般数体ふるい法(GNFS)」で分解した。
これは一般数体ふるい法による1番大きな分解である（もうすぐ他のチームに
よるもっと大きな分解が完了するらしいので1番である期間はそう長くないと
思われる）。
5月10日追記：200桁の分解が発表された。
c176 in 11^281+1 =
10098240736531334505088844
65819427259940099192936939289070048049173631682915
37078836750124948329070667886041202454205608993748
49022836745595410281489604207498450138102224691173
= p87 . p89
p87 = 8428398995380842661984668205419427509
43860088703946121840940131686719691460399191375953
p89 = 119812086993812743242137195174352093894
91006236671100986363096780488054684807819312870741
11^281+1 の部分的な分解はすでに行われていた:
11^281+1 = 2 * 2 * 3 * 2165143447416427 * 73717873044643423196357
* 47677949460728118782533826487424424473
* 46402408546690245400968842648859676155371
* c176
[多項式選択]
多項式は次のものを採用した。
なお以下では k は 10^3, M は 10^6, G は 10^9 を表す.
f(x) =
42465167160 * x^5
+ 17988038900026354 * x^4
- 24485816371689913728521 * x^3
- 1668083704791996143020318484 * x^2
+ 666155199819630813243886284231438 * x
+ 51503023516231281215723647769021985660
g(x) =
385940178780061631 * x
- 750313181756151817259725353359779
この多項式ペアは Kleinjung による多項式選択プログラムを用いて生成した。
多項式選択は2月5日から3月18日まで行われた。はじめの2週間は1台のPCを
動かし、次の3週間は立教大学とNTTにある 52台のPCを使った。
そして上記の多項式ペアを3月8日に見つけた。
最後の週は 32台を用いたがより良い多項式を見つけることはできなかった。
もっとも多く用いたPCは Pentium 4(Northwood)[3.2GHz] ベースのもの
であった。このPCに換算して 3.5年の計算量になる。しかしこれだけの時間
を費やす必要はなかったと思われる。
[ふるい]
ふるいは 3月16日に開始した。投入する PC は徐々に増やされ、大学の春休
み期間中にはかなりの台数に上った。
小さな special-Q においては高々 512MB のRAMで済んだが大きなspecial-Q
に対してはそれ以上が必要となった。
ふるいのプログラムは我々独自のものである。その性能は最適化が進み徐々
に高速になって行った。
使用 PC:
立教大学
6 x Pentium III[1.0GHz] with 512MB RAM
70 x Pentium 4[2.4GHz-3.4GHz] with 512M-2GB RAM
1 x Athlon 64[2.0GHz] with 1GB RAM
148 x Pentium 4[2.6GHz] with 512MB RAM
NTT:
32 x Pentium 4[3.2GHz] with 2GB RAM
28 x Pentium III + 4 x Opteron[1.0GHz-3.8GHz] with 512MB-4GB RAM
富士通研究所:
100 x Pentium III[dual 1.0GHz] with 1GB RAM (Primergy Blade Server)
8 x Pentium III[dual 1.4GHz] with 1.5GB RAM
7 x Pentium 4[3.8GHz] with 2GB RAM
合計 399台のPCを用いたが、これらが常時稼動していたわけではない。
ふるいの時間は実時間で27日間かかった。この間に用いたPCの合計時間は
Pentium 4[3.2GHz] を1台だけ用いたものとすると 9.7年になる。
我々は lattice sieve だけを用い line sieve は用いなかった。
ふるい領域は [-16384,16384)×[1,16384] を基本とし special-Q（の基底）
によって変形したものを用いた。
special-Q は代数側で用いた
30.5M-221.2M では 111.5M-113.4M を除きおよそ 10.2M個のidealsを用い、
28.8M-30.5M と 221.2M-227.0M の一部のおよそ 0.3M個の ideals を用いた。
factor base の限界は代数側は 0.95Q であり、有理側は 80M である。
large prime の限界はどちらの側も 4G である。
生成した relations は 576 372 161 個である。
なお、large primes はどちらの側も 2個までに制限した。
また free relations は利用しなかった。
[Filtering]
Filtering は 4月7日に重複relations の削除から開始した。
4月11日の夜までの relations は取り込んだ。relations が不足したときに
備えてふるいは継続していた。
Filtering が終了したのは 4月16日の正午である。
Cavallar のアルゴリズムを 21-way merge まで行った。
使用環境は 32 x Pentium 4[3.2GHz] with 2GB RAM をギガビット・イーサ
ネットでつないだものである。しかし大体は 1, 2台あるいは 9台であった。
実時間は 9日間であった。ただし実際に必要としたのは 2.5日であり、その
差はふるいの結果を待っていたこと、clique プログラムが予想以上にメモリ
を消費したこと、ネットワーク・サーバが故障したことなどに起因する。
576 372 161 ふるいの出力relations数
455 989 949 重複を削除した後のrelations数
328 707 916 有効な factor base の個数
27 220 932 singleton and clique operation後の個数
27 219 940 その有効な factor base 数
[行列計算]
行列のサイズは 8 526 749 x 8 525 751 であり、非ゼロ要素の個数は
1 707 545 745 であった。
方法は Block Lanczos 法で block長は 256-bit であった。
36 x Pentium 4[2.8GHz-3.2GHz] をギガビット・イーサネットでつなぎ MPI
によるクラスタシステムとしたものを用いた。
Block Lanczos 法に入る前に重い 224列を削除した。これにより非ゼロ要素
の個数は 1 394 050 132 に減った。
Block Lanczos 法は 4月16に開始し、4月21日に終了した。およそ 5.3日で
あった。
この 256個の解から最初の行列の 32個の解を作り出した。
それから2次指標を用いて単数部を調整してこの 176桁の数を法とする 24個
の平方関係式を得た。
[平方根]
代数的数の平方根の計算には Nguyen のアルゴリズムをネットワークの並列
計算に合うようにアレンジしたものを用いた。
使用したPCはNTTの 36 x Pentium 4[2.8GHz-3.6GHz] である。
上の24個の関係式ひとつにつきおよそ 1 時間かかる。
この計算は 4月21日の深夜から22日未明にかけて行われた。
4番目の関係式から分解を得た。
謝辞
多項式選択プログラムをご提供くださったKleinjung博士のご厚意に感謝する。
by
青木 和麻呂
植田 広樹
木田 祐司
下山 武司