On April 26th 2003, NFSNET completed the factorization of 5^298+1.

The factors of the C189 cofactor are:

p50 = 52509417634810887468425272956814828347615306977561

p139 = 309215659108473421850257135381750596752032594371193030632855570 \
           775794490723811439924506279453668132877400892213241277235128318 \
           1220537622773

We used SNFS with the polynomials -X + 5^50 and m^6+25 which share a root m=5^50 mod 5,298+. 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 89 machines from 33 participants. Sieving began on February 24th, 2003 and finished on March 29th, 2003.

The sievers found 43.5 million relations. The filtering stage reduced these to a matrix which had 4,897,158 rows and 4,903,379 columns. Primes less than 120 were excluded providing a savings in matrix weight of 40,881,211 and a final matrix weight of 247,805,504.

The linear algebra was performed on the MSRC cluster using 30 of its 1Ghz P-III CPUs. It began on April 19th and finished after 157.7 hours (a bit over 6.5 days). The cpus were running at approximately 50% capacity and so the total cpu time was around 2,400 hours. The discrepancy between the CPU time and the elapsed time is explained by the latency in the inter-CPU communications via gigabit ethernet.

The result of the linear algebra was 125 linear dependencies in the matrix. In the square root phase each dependency required 70 minutes to process on a 2.5GHz-P4 workstation.

The first generated only the trivial factorization but the second produced the factorization shown above.

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

The NFSNET administrators:

Chris Card
Jeff Gilchrist
Don Leclair
Paul Leyland
Richard Wackerbarth

Contributors to the 5^298+1 factorization:

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