snfs248.htm

SNFS248

2004年4月4日早朝、我々のチームは特殊数体ふるい法(SNFS)で248桁の合成数の分解に成功した。

これは SNFS による素因数分解の新記録である。なお、これまでの記録は 244桁であった。

この数は 2^1642+1 の約数で Cunningham project で 2,1642M と名前をつけられているものである。

  2^1642+1 = 2,1642L * 2,1642M
  2,1642M = 2^821 + 2^411 + 1

  2,1642M = c248
=   139838398039428521505951093426146672317977242051
  61451430391332862456574221363722734055314582922181
  82394011694786083970706758188061429005670580578819
  43219670611471791456566889090642387438187278519182
  88932286008372802624437907070565445887094633267201
= p88 * p160

  p88 =       75052937460116417664924678548932616036
  64038102314712839047907776243712148179748450190533


===== 統計情報 =====
以下では k は 10^3 を M は 10^6 を G は 10^9 を表すものとする。

[多項式]
f(x) =  x^6 + 2*x^3 + 2
m = 2^137

[ふるい]
計算機:
電気通信大学に設置されたPentium 4 2.53GHz (FSB 533MHz) with 1GB RAM 
を64台と立教大学のさまざまな速度、メモリ量の Pentium4 を36台用いた。
所要時間：
全部で 50日かかったがすべての PC がその間フル稼働していたわけではない。
Pentium 4 2.53GHz (FSB 533MHz)を一台フル稼働させたとすると 8.2年
かかるものと推定される。ただし今回は relation を集めすぎているので
どこまで減らせるかを実験中である。

[Line sieve]
用いなかった。

[Lattice sieve]
sieve領域: [-16k,16k)x[0,8k)
special q: 有理数側のみにとった。大きさは 1.02M から 200M までで
1.03M から 1.06M までと 33.9M から 51.4M までは除いた。
factor base bound: 有理側では 0.95q までとし、代数側では 100M までとした。
large prime bound: どちらも 4G とした。
以上から 558 455 641 個の relations を得た。

[Filtering]
アルゴリズムは Cavallar のものを部分的に用いたものである。
計算機は Pentium 4 2.53GHz (1GB-RAM) with 100baseT を 32 台用いた。
ただしほとんどの時間は 1, 2, 4, or 8 台しか使っていない。
所要時間は 8 日であるがほとんどの時間は人間の操作待ちの時間である。
  558 455 641 最初のrelationの個数
  438 270 192 二重登録を削除した後のrelationの個数
  323 629 061 実際に使われたfactor baseの個数
   25 247 811 singleton処理、clique処理の後のrelationの個数
   25 246 816 そこで使われたfactor baseの個数

[線形代数]
入力行列のサイズは 7 429 778 x 7 429 097 であり、ゼロでない要素の総数は
 1 544 659 604 であった。
まずこれのゼロでない要素が多い96列を取り除いた。これでゼロでない要素の個数は
 1 397 375 593 に減った。
この行列の核に含まれるベクトルを block Lanczos 法で 128 個求めた。
計算機は NTT の Pentium 4 (3.2GHz) を 16 台ギガビット・イーサネットでつないだ
クラスタマシンで行った。
所要時間は 15日であった。ただしハードウェアの故障などで無駄になった時間を除いた
実質的な時間は 9.5 日である。
この 128次元の解から取り除いた96列分の解にもなっているものを求めると
33 個の解が見つかった。これらを 32 個の2次指標による検査にかけて 31 個の
解を得た。

[平方根]
代数的数の平方根の計算には Montgomery-Nguyen 法を用いた。

立教大学の Pentium 4 * 8 台(平均 2.53GHz) を用いた。
[線形代数]の最初の解から最終的な分解を得ることができた。
所要時間は4時間であった。


すべてのプログラムは我々が開発した。ただし平方根の計算では Pari が数体
のいくつもの対象の計算をした。

この研究の一部は通信・放送機構等が推進するCRYPTRECの支援を受けた。

by
青木 和麻呂
植田 広樹
木田 祐司
下山 武司
園田 裕貴