Mersenne: All Cunningham Wanted Numbers Factored

[Peter-Lawrence.Montgomery]

             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.

       //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.


_________________________________________________________________________
Unsubscribe & list info -- //www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ      -- //www.tasam.com/~lrwiman/FAQ-mers