GNFS164

On December 19, 2003, we factored the 164-digit number of 2^1826 + 1
by General Number Field Sieve.
This is the 2nd largest factoring by GNFS.

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

p68 = 
34334644886182446546273008924242084634327089789559\
771215864092254849

We selected the following polynomial by rough use of Montgomery-Murphy method.
f(x) =
8293702863045600 x^5
+5627796025215486707 x^4
+557524556427309931902111 x^3
+176917216602508818430161036 x^2
-13601173202899548432935219131949 x
-12171622290476241497444980012311021

M = 411268775932725752596939184846

Sieving region was 
[-16384, 16384) x [0, 8192)
Special-Q's were taken from 43*10^6 to 194*10^6, about 8.2*10^6 primes.

Rational factor base consited of the primes less than 4*10^7,
and algebraic factor base consited of the primes less than special-Q.

Large prime bound was 4*10^9 for both sides.

Sieving took about one month. It is scaled to about 7 years 
if we only use one PC(Pentium-4 [2.53GHz] with 1G RAM). 

Lattice sieve found 409711156 relations,
line sieve found 48732057 relations.

Filtering reduced the matrix size to 7501898 x 7500801 
with 1251138505 non-zero entries.

Block Lanczos method solved this matrix in about 12 days 
using 16 PCs(same PC as above) connected through Gigabit Ethernet.
The block size was 128.

Computing square-root used Montgomery-Nguyen method.

All programs were developed by us except the square-root stage
where Pari gave many number field invariants.

This factoring is partly supported by the CRYPTREC project which is
sponsored by Telecommunication Advancement Organization and other
organizations.

-----------------
Kazumaro AOKI
Yuji KIDA
Takeshi SHIMOYAMA
Yuki SONODA
Hiroki UEDA