GNFS164

2003年12月19日、我々のチーム(下記)は 2^1826+1 の約数である 164桁の合成数を
「一般数体ふるい法(GNFS)」で分解した。
これは一般数体ふるい法による2番目に大きな分解である。

c164 =
97583673891702451651094659376990232450771614233997\
85325879473864808161869141292797373828054892194274\
08614639625580843270216606887108154934492304270050\
90485779545989
= p68 * p97

p68 = 
34334644886182446546273008924242084634327089789559\
771215864092254849

多項式は次のものを採用した。これの探索には Montgomery-Murphy の方法を
一部省略して用いた。

f(x) =
    8293702863045600 x^5
   +5627796025215486707 x^4
   +557524556427309931902111 x^3
   +176917216602508818430161036 x^2
   -13601173202899548432935219131949 x
   -12171622290476241497444980012311021
with
M = 411268775932725752596939184846

ふるいの領域は
[-16384, 16384) x [0, 8192)
である。

Special-Q には 43*10^6 から 194*10^6 までの 8.2*10^6 個の素イデアルを用
いた。

有理側の factor base は 40*10^6 未満の素数からなり、
代数側の factor base は special-Q 未満の素数からなる。

Large prime の限界は両方ともに 4*10^9 である。

ふるいにはおよそ一ヶ月を要した。これは Pentium-4 2.53GHz に 1G RAM を
搭載した PC 一台に換算すると 7 年かかることになる。

Lattice sieve は 409711156 個の relation を見つけ、
line sieve は 48732057 個の relation を見つけた。

Filtering はこれらを 7501898行 7500801列の行列に集積した。
この非ゼロ要素の個数は 1251138505 である。

Block Lanczos 法はこの行列（の定める連立方程式）を約 12日で解いた。
これにはギガビットイーサネットで接続された 16台の PC（ふるいで用いたの
と同等のもの）を用いた。Lanczos 法の block size は 128 とした。

平方根の計算には Montgomery-Nguyen 法を用いた。

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

この研究の一部は通信・放送機構等が推進するCRYPTRECの支援を受けた。
より詳しくは SCIS 2004 at Sendai, Jan.27-30 の予稿集を参照されたい。 

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