W(668) Factorization Complete
November 10th, 2002

Earlier this year, Richard Wackerbarth, Paul Leyland and Don Leclair decided to re-form the NFSNET collaboration to factor large integers by the Number Field Sieve. NFSNET uses a relatively small number of servers to coordinate a relatively large number of client machines which perform the sieving stage of the NFS algorithm. Each factorization is defined by a "project" which holds information such as the number being factored, the polynomials used, the size of the factorbases and so forth. The servers' responsibility is to provide project details to the clients, to allocate regions to be sieved, and to collect the results from the clients for further processing later.

The NFS implementation on which we based NFSNET is that developed by CWI in Amsterdam. CWI granted us a source license which permits us to modify the code for NFSNET's purposes and to distribute binaries built from it. Virtually all the client/server code was written from scratch, the vast majority by Don and Richard. The post-sieving phases also used CWI's software with a few modifications to let it run under Windows XP.

The 204-digit integer Woodall(668), aka 668*2^668-1, was chosen as the test-bed for the new NFSNET for two reasons. First, it had no known factors despite extensive ECM work and was a most-wanted number in Paul Leyland's Cullen and Woodall page. Second, a 204-digit integer with a simple SNFS polynomial is sufficiently large to be likely to throw up some challenges without being so large that they would be unsurmountable.

In the parameter selection phase, we chose the polynomials 167-4x^6 and (2^112)x - 1, which share a common root m=2^(-112) modulo W(668). We used factor bases containing primes to 50 million on each side (just under 3 million primes in each) and allowed up to two large primes up to 2^29 on each side. We chose to sieve over lines with |a| <= 18 million. We listed large prime ideals within a relation if they exceeded 10 million.

The sieving phase took 40 days elapsed (September 6 through to October 15 inclusive) and 1040 days cpu. There were up to 55 clients running under MacOSX, x86/Linux, x86/FreeBSD and several versions of Microsoft Windows.

The average machine had a performance close to a 800MHz PIII and used about 78Mb of active memory for the siever. The task allocation server handed out about 35,000 tasks, corrresponding to b-values up to 8,610,750. The clients returned a total of 44,065,495 relations to the server.

The raw set of relations were initially processed by Richard Wackerbarth to remove a few duplicates and the singletons --- that is, those relations which contain large primes which themselves only occur once in the entire collection. Singleton removal can generate further singletons, so this process was repeated until no singletons remained. Richard then performed several filtering runs to merge relations sharing large primes which appeared only twice. This process reduced the data to 18,272,456 relations. This data set, a file of just over a gigabyte, was compressed and written to CD. The raw data was also compressed and written to two further CDs. All the data was then airmailed to Paul Leyland at Microsoft Research in Cambridge UK.

More filtering was performed at MSR Cambridge to reduce the very large but very sparse data to something more manageable by the linear algebra software. A few experiments were performed on the raw data but most attention was paid to the pre-filtered set. A series of filter runs, using merges of up to weight 8, reduced the number of relation-sets to 5,595,070 containing a total of 25,015,789 relations. When fully factored, these relations required a file of 2.44Gb to hold them all. When the free relations were added, the data produced a matrix with 5,658,329 rows and 5,687,746 columns with a weight of 306,788,165 set bits after the densest rows corresponding to primes under 120 had been discarded.

Finding linear dependencies in this large bit-matrix was done with the parallel block Lanczos implementation of Peter Montgomery and Stathis Papaesthathiou. It was run on all 32 cpus of a cluster of 16 dual 1GHz-PIII machines connected by gigabit ethernet and a dedicated switch. The parallel processing harness used was MP-MPICH running under Windows .NET Server. The master node used 174Mb of memory and the 31 client nodes 73Mb each. As each machine has 2G RAM memory usage was moderate. The complete computation took 177 hours, though it had to be restarted from a checkpoint part way through because of a network failure.

The square root program was run on a single 2.53GHz P4 under Windows XP. The first two dependencies yielded on the trivial factorization but the third dependency yielded a factorization. Each dependency took 135 minutes to process.

A result of all this effort is that we now know that 668*2^668-1 is the product of:

9033730244285668673572460098039181123844478857716071399 and

90562092375658215875921181947930788536808446402237006554398265875609391652\ 489319078490885430679432762271341198116663573505774591722137302629050980393

which have 55 and 149 digits respectively.

Other results from the first project undertaken by the revived NFSNET include a much better understanding of how to run a largely-automated NFS factorization (and several ways of how *not* to run one) and client / server software which, although far from being a fully polished product, is now in a state for distribution to beta testers. The beta-test project will be to factor 6^257-1, which is one of the Most Wanted Numbers in the Cunningham project.

Don, Paul & Richard.