Date: Fri, 7 Sep 2001 22:26:15 -0400 Reply-To: Peter-Lawrence.Montgomery@cwi.nl Sender: Number Theory List From: Peter-Lawrence.Montgomery@cwi.nl Subject: All Cunningham Wanted Numbers Factored All Cunningham Wanted Numbers Factored Peter Montgomery pmontgom@cwi.nl September 7, 2001 The Cunningham tables have factorizations of b^n +- 1 for small b and n. The full reference is John Brillhart, D.H. Lehmer, J.L. Selfridge, Bryant Tuckerman, and S.S. Wagstaff, Jr., "Factorizations of b^n +- 1, b = 2, 3, 5, 6, 7, 10, 11, 12 up to high powers", Contemporary Mathematics, Volume 22, American Mathematical Society. http://www.cerias.purdue.edu/homes/ssw/cun/index.html The first edition appeared in 1983 and the second in 1988. Sam Wagstaff, the principal maintainer of the tables, is sending a third edition to the publisher this month. TRADITION OF WANTED NUMBERS One Cunningham project tradition has been lists of wanted numbers, usually chosen by author John Selfridge. These have served as challenge numbers -- somebody who claims a superior factoring algorithm will typically demonstrate it on these numbers, which have resisted repeated attempts by others. Pages lviii-lix of the 1983 edition list 10 "most wanted" numbers and 15 "more wanted" numbers. The largest of these is the 71-digit repunit (10^71 - 1)/9. All were factored within about two years, usually by the just-discovered quadratic sieve or by P-1. Page lxxxvi of the 1988 edition lists 10 "most wanted" numbers and 22 "more wanted" numbers, the smallest being the 86-digit number (3^199 - 1)/(2 * 1360648969) and the largest being the 148-digit cofactor (2^512 + 1)/2424833 of the Fermat number F9. All of these were later factored, usually by the elliptic curve method (ECM), multiple-polynomial quadratic sieve (MPQS), or number field sieve (NFS). The F9 factorization made international headlines. The wanted lists have been revised many times between printed editions, approximately annually, as existing entries are factored. The largest number to ever appear, a 291-digit cofactor of F10 = 2^1024 + 1, was factored in October, 1995, when Richard Brent found a 40-digit factor by ECM. The May 31, 2001 list has 10 "most wanted" numbers and 16 "more wanted" numbers, ranging from 144-digit cofactors of 2^631 + 1 and 2^617 + 2^309 + 1 to the 193-digit number (11^191 - 1)/195867 . [There had been 34 wanted entries in July, 2000 -- the other 8 were factored before May 31.] ENTIRELY NEW LISTS The publication of the 3rd edition starts a new era. For the first time since the 1983 edition appeared, the old lists have been completed en masse. All 26 numbers on the May 31 lists were factored by September 7, or 99 days later. The average pace was one number completed every four days. The following individuals contributed to this effort: Bruce Dodson, Lehigh University, Bethlehem, PA, USA Jens Franke, Institute for Pure Mathematics, Bonn, Germany Torbjorn Granlund, Swox, Stockholm, Sweden Thorsten Kleinjung, Institute for Pure Mathematics, Bonn, Germany John Klos Arjen Lenstra, Citicorp, NY, USA (home in NJ) Paul Leyland, Microsoft Research, Cambridge, UK Peter Montgomery, Microsoft Research, Redmond, WA, USA (home in CA) Robert Silverman, Bedford, MA, USA Herman teRiele, CWI, Amsterdam, The Netherlands We used computer facilities at Centrum voor Wiskunde en Informatica (CWI), Amsterdam, The Netherlands High Performance Computing Center North, Stockholm, Sweden Institute for Applied Mathematics, Bonn, Germany Institute for Pure Mathematics, Bonn, Germany Lehigh University, Bethlehem, PA, USA Microsoft Research, Cambridge, UK RSA Security, Bedford, MA, USA SARA, Amsterdam, The Netherlands Stockholm University, Department of Mathematics, Stockholm, Sweden Swedish Institute of Computer Science, Stockholm, Sweden Swox, Stockholm, Sweden plus some home PCs (including a laptop during intercontinental flights!). Only one of the 26 wanted numbers had a prime factor under 47 digits. That number, a c168 cofactor of 3^382+, left a c127 when its 42-digit factor was found by ECM. All other factors were found by SNFS. One wanted number had two factors over 90 digits: 2,619+ = 3 * p91 * p96 p91 = 125738815991080426576344660082527825631801224969 \ 7661907431303034629811311740864601663325811 p96 = 576735513593459498091224888775105070536100466874 \ 272552892992673568274909599171018374973329229033 This is just below the previous size record 10^211 - 1 = 3*3*p93*p118. Both are dwarfed, however, by the new factorization 2^727 - 1 = p98 * p122 p98 = 1760629171181543403793488187233161167077749116644 \ 5300472749449436575622328171096762265466521858927 p122 = 400994997261837585178919394286016657070637945934 \ 4394068988852655680258152926272814339895974344415 \ 0539520890742947533452401 Although 2^727 - 1 is not on the May wanted list, it has long been the first entry in the 2^n - 1 table with no known prime factor. Now that honor goes to 2^751 - 1, followed by 2^809 - 1 and 2^971 - 1. QUICK LINEAR ALGEBRA TO THE RESCUE This effort had factored 19 of the 26 wanted numbers as of August 23, when Sam Wagstaff announced an August 31 freeze date for contributions to the third edition. At that point, several of the remaining wanted numbers were almost sieved, but the linear algebra had been taking 1-2 calendar-weeks per number, pushing their projected completion dates past the August 31 deadline. SARA, a Dutch High-Performance Computing Center in Amsterdam, had been down August 13-20, to enlarge its network (teras) of shared memory 500 MHz MIPS R14000 processors. Peter Montgomery had written a parallel MPI-based version of his Block Lanczos linear algebra code earlier in 1999-2001. Happily, this code functioned well on the new hardware configuration, There was little system downtime, enabling many linear algebra jobs to be run during the crisis period. The recently added teras capacity meant there were short waits for jobs to run. The largest matrix run on teras, for 2^727 - 1, was 3847967 x 3862821. This took 99153 real-time seconds (about 27.5 hours) using 25 processors. The estimated single-processor time is 1200000 seconds (330 hours) for that same matrix on the same hardware, so the job got almost 50% utilization of the 25 processors. By the morning of August 31, eight days after Wagstaff's freeze announcement, we had completed 23 of the 26 wanted numbers, in addition to 2^727 - 1 and some early holes (likely candidates for new wanted numbers). Then Wagstaff announced that Selfridge was on vacation, unable to revise the wanted lists at this time, and gave us approximately one more week to submit results. One more wanted factorization, 2^641 + 1, arrived later on August 31. The last two wanted numbers, cofactors of 2^641 - 1 and 5^283 + 1, had undergone little sieving prior to Wagstaff's freeze announcement. [Conrad Curry had been sieving 2^641 - 1 a year earlier, but none of us had been able to contact him -- we waited until his school year began August 20 before restarting it.] We sieved these last two numbers madly, spreading the effort over several sites. By September 2, we had enough sieving data for 2^641 - 1 -- its factorization was found two days later, with the linear algebra taking 12 wall-clock hours on 16 processors for a 2.548 M x 2.551 M matrix. 5^283 + 1 took longer -- we sieved until September 5, the first convenient date for contributors to merge their data. Collectively we had gathered 10% more relations than needed. Only 5.67 M relations survived the first round of filtering, compared to a typical 8 M or more. A quick but sloppy second stage of filtering left a 2.920 x 2.960 matrix, which 25 teras processors finished in 14 hours. The factorization was found at 03:50 UTC on September 7, about 27.5 hours after the last data file had reached CWI, when one of four square root jobs found a non-trivial factorization. When we submitted 2^641 - 1 to Wagstaff, we checked that he had all wanted factorizations except 5^283 + 1. Alas, Wagstaff lacked 3^386 + 1. That had been done two weeks earlier, but nobody had sent the result to Wagstaff. The oversight was quickly remedied. During those final days, we also finished 11,407M, a 130-digit cofactor of 11^407 + 1 and the then-smallest composite cofactor in the new table. This factorization used the polynomial f(X) = X^5 - 9*X^4 - 16*X^3 + 53*X^2 + 37*X - 23 with root m = 4 + 11^(-18) + 11^19. The smallest composite cofactor in the 3rd edition is another c130, compared to c51 in the 1983 edition and c80 in the 1988 edition. While the 5,283 + 1 linear algebra was running, activity remained busy on other fronts. Jens Franke found a 44-digit factor of 2^1120 + 1 by ECM. The 112-digit cofactor was prime and didn't need more work. Then Paul Leyland, Sam Wagstaff, Alec Muffett, Bruce Dodson, and Arjen Lenstra set a MPQS record. They split a 135-digit cofactor of 2,1606L (which divides 2^803 - 2^402 + 1 and 2^1606 + 1) into 66- and 69-digit prime factors. The prior MPQS champions were RSA-129 (the original challenge number for the RSA cryptosystem, many contributors) and the c127 (90! + 1)/1381173038633 by Sean Irvine. Within the Cunningham table, the old records are two 124-digit numbers by Jens Franke. Leyland et al allowed three large primes, as did Franke.