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
distinction now falls to 2^713-1 (or 2^739-1 if you define Mersenne numbers as
those with prime exponents only).
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 around the world 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 CPU-hours, 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 about NFSNET 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, Igor Schein, Martin Schroeder, Richard
Wackerbarth and 18 others who have not selected to be listed here.
_________________________________________________________________________
Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
