On September 1st, 2003, NFSNET completed the factorization of 2^713-1.

The factors of the C171 cofactor are:

p56 = 25302796036126213353739363322307560110912714814142460639 and

p115 = 412024428126665339629695779250098784736173464971825416238036090352082134 \
           0784053375183825542777493894566793029100537

We used SNFS with the polynomials x^6-2 and x-m which share a root m=2^119 mod 2^713-1. We used primes up to 50 million on the rational and algebraic sides, with up to two large primes < 500 million on each side.

The sieving stage was performed by NFSNET participants using 170 machines from 63 participants. On average there were about 80 machines active each day. Sieving began on July 6th, 2003 and finished on August 1st, 2003.

Approximately 13.4M lines were sieved and 43.7 million relations were found. The filtering stage reduced these to a matrix which had 5,439,158 rows and 5,443,789 columns. Primes less than 120 were excluded providing a savings in matrix weight of 42,600,948 and a final matrix weight of 274,645,568. The matrix had an average of 50.49 set bits per row and 50.45 set bits per column.

The linear algebra was performed on the MSRC cluster using 28 of its 1Ghz P-III CPUs. It began on August 20th and finished after about 221.8 hours (about 9 days, 5.8 hours).

During the square root phase we were unusually unlucky. The first six dependencies provided only the trivial factorization. The factors were found on the seventh dependency. Each dependency took 48 minutes on a 2.5GHz P4 machine.

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^713-1 factorization:

Brian Beesley, Andrei Belenko, Chris Card, Robert Clark, John Dilick, Richard Farmbrough, Decio Luiz Gazzoni Filho, Jeff Gilchrist, Francois Grieu, Rich Harms, Sander Hoogendoorn, Simon Josefsson, Rick Lavoie, Don Leclair, Paul Leyland, Aaron Lehmann, Tommy McCabe, Andreas Pipp, Martin Schroeder, Team Prime Rib, Richard Wackerbarth, and 43 others who have not selected to be listed here.