On March 17th 2003, NFSNET completed the factorization of 2^673-1.

The factors of the C151 cofactor are:

p59 = 68396769572915971687133122358352070840260017483089158059519 and

P92 = 23882525111457526669660263269125438250762730250942712633131 \
         193354954889195068879706608493409

Numbers of the form 2^n-1 are known as Mersenne numbers and 2^673-1 was the smallest Mersenne number whose complete factorization was unknown. That distiction now falls to 2^713-1.

We used SNFS with the polynomials x-m and 2*x^6-1 which share a root m=2^112 mod 2^673-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 less than 500 million were allowed on each side.

Sieving began on January 29th, 2003 and finished on February 17th, 2003. During that period 67 computers from 29 users sieved and found a total of over 43 million relations.

A CD containing the relations was sent by airmail from Austin on 26th February and arrived in Cambridge 5th March. Richard had run a preliminary filtering step to remove singleton relations, leaving 25,653,719 on the CD. Filtering at Cambridge reduced this to a matrix with 3,556,972 rows and 3,561,585 columns. Block Lanczos running on 30 cpus of the MSR Cambridge took 121 hours elapsed, around 1500 hours cpu, to find 108 linear dependencies in the matrix. The square root program took about an hour to find that the first dependency yielded the factorization p59*p92.

Our thanks go to all the contributors for their efforts and to CWI for letting us use a modified version of their NFS software.

For more information visit http://www.nfsnet.org.

The NFSNET administrators:

Chris Card
Jeff Gilchrist
Don Leclair
Paul Leyland
Richard Wackerbarth

Contributors to the 2^673-1 factorization:

Brian Beesley, Chris Card, Jeff Gilchrist, Francois Grieu, Alex Kruppa, Rick Lavoie, Don Leclair, Paul Leyland, Jeramy Ross, Igor Schein, Martin Schroeder, Richard Wackerbarth and 17 others who have not selected to be listed here.