On March 20th 2003, NFSNET completed the factorization of 12^178+1.

The factors of the C145 cofactor are:

p69 = 720167766050900193760846961135216805551800888406370139983414556549013 and

P76 = 6514151017892214401693652198176752391997114754246624661507706543007713794261

We used SNFS with the polynomials x-m and 4*x^6+9 which share a root m=6*12^29 mod 12^178+1.

We used factor bases with primes up to 40 million for the sextic and linear polynomials. Up to two large primes less than 500 million were allowed on each side.

Sieving began on February 16th, 2003 and finished on February 25th, 2003. During that period 54 computers from 22 users sieved and found a total of over 43.8 million relations.

The relations were stripped of singletons and duplicates and the 26 million or so survivors written to CD and mailed to Cambridge where they arrived on March 5th. On receipt it was found that the file was corrupt but largely recoverable. Around 400,000 relations were lost but the remaining 25,911,702 relations were still sufficient to complete the factorization so we decided not to resend the missing ones.

Filtering and merging the relations reduced them to a matrix which had 3723972 rows and 3748760 columns. The linear algebra on this matrix took 79.4 hours elapsed time, about 950 hours total cpu time on 30 processors of the MSR Cambridge cluster. It finished on the evening of March 10th. Unfortunately, very few "pseudodependencies" were found in the data and the square root program was unable to find factors.

Peter Montgomery, the author of the linear algebra and square root software had come across a very similar failure a few weeks earlier. He and Paul Leyland worked together to see if the problem could be understood and avoided in future. In the interim, the cluster was set to work on the matrix for 2,673-, which did complete successfully.

A new and slightly smaller matrix was created and the linear algebra job restarted. It took 77.5 hours elapsed and around 930 hours total cpu time, finishing on the afternoon of March 20. This time the run was successful, in that although the number of pseudodependencies was much smaller than normal, enough true dependencies remained for the square root program to succeed in finding factors of 69 and 76 digits.

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

The NFSNET administrators:

Chris Card
Jeff Gilchrist
Don Leclair
Paul Leyland
Richard Wackerbarth

Contributors to the 12^178+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 10 others who have not selected to be listed here.