From: ssw@cs.purdue.edu (Samuel S Wagstaff)
Newsgroups: sci.math.numberthy
Subject: Record NFS factorization
Message-ID: <199702101402.JAA24232@arthur.cs.purdue.edu>

NFSNET, a group of people who factor large numbers using the
Number Field Sieve algorithm, announces a record factorization:

On Tuesday, 4 February 1997, we completed the factorization of a
composite number of 167 digits, one of the `More Wanted' factorizations
of the Cunningham Project.  It is:

3,349- = (3^349 - 1)/2 = c167 = p80 * p87

where

p80 = 940428508899845109982891523204385417985320180216539562\
      83741193211654025280185459
p87 = 174165493740875256464746388999480533990944334266849687\
      054611524922878840708206608860499

This factorization was `More Wanted' because it was the smallest number
of the form 3^n - 1 whose complete factorization was not yet known.  Now
the complete factorization of 3^n - 1 is known for all n <= 370.

The penultimate prime factor has 80 digits, a record.  The 167-digit
number is also the largest number ever factored by the Number Field
Sieve, eclipsing our factorization of (10^167 - 1)/9 last October.
(Actually, the factorization of (10^167 - 1)/9 was slightly harder
than that of (3^349 - 1)/2 for technical reasons.)  For more
information about the Number Field Sieve, see the book, "The Development
of the Number Field Sieve," edited by A.K. Lenstra and H.W. Lenstra, Jr.,
Springer-Verlag Lecture Notes in Mathematics, volume 1554, 1993.

The goal of the Cunningham Project is to factor numbers of the form
b^n +- 1, for b < 13 and having up to a few hundred decimal digits.  Its
record is the book, "Factorizations of b^n +- 1, b = 2, 3, 5, 6, 7, 10,
11, 12," by J. Brillhart, D. H. Lehmer, J. L. Selfridge, B. Tuckerman,
and S. S. Wagstaff, Jr.  The second edition of this book was published
in the Contemporary Mathematics series, volume 22, of the American
Mathematical Society in 1988.  All factors in it fit on one line,
except the ultimate factors, which are often large and which are
relegated to an Appendix.  The new p80 penultimate factor above is the
first factor discovered which will not fit on one line of the book.  It
will force the authors to change the format of the third edition, in
preparation now, to accommodate it.

NFSNET is a collaborative effort to factor numbers by the Number Field
Sieve.  It relies on volunteers from around the world who contribute
the "spare time" of a large number of workstations to perform the
sieving.  In addition to completing work on other numbers, their 75
workstations sieved 3,349- during the months of December and January.

The organizers and principal researchers:

Marije Elkenbracht-Huizing, Peter Montgomery, Bob Silverman,
Richard Wackerbarth, Sam Wagstaff, Jr.

They wrote the programs, collected the data, and factored 3,349-.

The volunteer sievers:

Leo Broukhis
Ed Buzzi
Damien Doligez
Oyvind Eilertsen
Bill Hodgeman
Matthew Jackson
Michel Kern
Harry J Smith
Ray Van Tassle
Richard Wackerbarth
Paul Zimmermann

If you would like to volunteer the services of your workstation to
help factor large numbers, please email rkw@factoring.dataplex.net
to learn how to join NFSNET.

Sam Wagstaff