SNFS274

2006年1月23日13時10分、我々のチームは特殊数体ふるい法(SNFS)で
274桁の合成数の分解に成功した。

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

この数は 6^353 - 1 の約数で Cunningham project で 6,353- と
名前をつけられているものである。

   c274 = (6^353-1)/5 =
  97369150518441644256595898307653103810177469944544
  60344424676734039701450849424662984652946941878917
  94816051886144204066226423206167081784681898063663
  68550930451357370697905234613513066631782316112426
  01530501649312653193616879609578238789980474856787
  874287635916569919566643
  = p120 * p155
   p120 = 
  13509526133011265183077504963559080738112103111138
  27323183908467597440721656365429201433517381980576
  36666351316191686483
   p155 = 
  72074438111130193764393586402902539161389086709970
  78170498495662717857340748450948116108762737328670
  41786794660514517682420730722427836886613902736846
  23521


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

[多項式]
f(x) =  x^6 - 6
m = 6^59

[ふるい]
計算機:
立教大学、NTT、富士通研究所の PentiumIII(1.0GHz) と Pentium4(2.6-3.4GHz)
を多数用いた。
所要時間：
Pentium4(3.2GHz) を一台フル稼働させたとすると 16.6年かかるものと推定される。
（Athlon64(2.0GHz) の場合は 17.3年かかるものと推定される。）

[Line sieve]
用いなかった。

[Lattice sieve]
ふるい領域: 
    512M 点：小さな special-Q (約 4.9M個の Q)
    1G 点：大きな special-Q (約 5.8M個の Q)
    領域の形は標準的には [-16K,16K)×(0,16K] および [-32K,32K)×(0,16K] であるが
    special-Q ごとに縦横比が変化する。
special-Q: 有理数側のみにとった。大きさは 5M から 200M までの 10.7M 個を用いた。
因子基底の大きさの上限: 有理側では 0.95Q までとし、代数側では 150M までとした。
large prime の大きさの上限: どちらも 16G 用に「ふるい」のパラメータを最適化したが
 128G までのものを拾い集めた。
以上から 2 497 019 540 個の relations を得た。

[Filtering]
アルゴリズムは Cavallar のものを部分的に用いたものである。
計算機は各段階でいろいろなPCを用いたが最も重い処理では Opteron 2.0GHz
(4GB-RAM) を 2 台用いた。
所要時間は 14 日である。
2 497 019 540 最初のrelationの個数
2 208 187 490 二重登録を削除した後のrelationの個数
2 576 689 745 実際に使われたfactor baseの個数
   15 653 157 free relation の個数
   84 078 616 singleton処理、clique処理の後のrelationの個数
   84 078 359 そこで使われたfactor baseの個数

[線形代数]
入力行列のサイズは 19 591 108 x 19 590 832 であり、ゼロでない要素の総数は
4 498 603 077 であった。
まずこれのゼロでない要素が多い224列を取り除いた。これでゼロでない要素の個数は
 3 938 362 368 に減った。
この行列の核に含まれるベクトルを block Lanczos 法で 256 個求めた。
計算機は NTT の Pentium4(3.2GHz, with 2GB-RAM) を 25 台ギガビット・イーサネット
でつないだクラスタマシンで行った。
メンテナンスの時間などを除いた実質的な所要時間は 34.64日であった。
この 256個の解から取り除いた224列分の解にもなっているものを求めると
34 個の解が見つかった。これらを 32 個の2次指標による検査にかけて 30 個の
解を得た。

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

NTT の Pentium4(3.6GHz) 1台を 50分用い、次いで
NTT の Pentium4(3.2GHz) * 25台を 3.2時間用いた。

すべてのプログラムは我々が開発した。

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