The NFSNET collaboration can announce that the factors of the Cunningham Most Wanted Number 6,257-.c173 are

p58 = 9306689489306197083232219997965248298881691751524941849307 and
p115 = 3673586540800931510375730400071935007467990878958458570282 \
411761897012162305639685693749182381299754408271638230437

This factorization is the first result from NFSNET's beta test program. An earlier alpha-test factorization of Woodall(668) was run only on the NFSNET organizers' machines. The present computation had contributions from 28 people and about 80 machines.

We owe a big debt to CWI as represented by Herman te Riele and Peter Montgomery. They let us use their implementation of NFS and to re-distribute modified copies of the rootfinder and siever programs. We also thank all the individuals and organizations that let us use their computers for the sieving phase.

Technical details of the computation are as follows.

We used the polynomials x^6-6 and x-m which share a root m=6^43 (modulo 6^257-1). We used factor bases with primes up to 50 million for the sextic and 40 million for the linear polynomial. Up to two large primes < 500 million were allowed on each side.

The sievers returned 43,082,997 relations to the server run by Richard Wackerbarth in Austin, Texas. The data was written to CD and airmailed to Paul Leyland in Cambridge, UK, for the post-processing steps. Unfortunately, it never arrived (we believe it was lost in the Xmas rush) and had to be re-sent. This mishap delayed the computation by several weeks. Normal postal delay is only a few days.

Filtering and merging reduced the data to a matrix with 4,231,165 rows and 4,267,169 columns. We found linear dependencies modulo 2 in the matrix with a parallelized block Lanczos program running on the 32-cpu cluster at Microsoft Research Cambridge. The program took 9 days elapsed and approximately 80 days total cpu time on 1Ghz PIII processors.

The square root stage took four hours on a 2.53GHz P4 machine and produced the factors given above on the first dependency.

The NFSNET admins, who are:

Jeff Gilchrist
Don Leclair
Paul Leyland
Richard Wackerbarth