CC: From: stewarts@ix.netcom.com (Bill Stewart) Subject: 167-digit number factored X-Mailer: Mozilla/2.1 (compatible; Opera/2.1; Windows 95) The article's gotten a bit garbled through replies, but this was on sci.crypt.
In article <phrE5EDtw.D1w@netcom.com> phr@netcom.com (Paul Rubin) writes:
In article <5dna0l$nrl@arthur.cs.purdue.edu>, Samuel S Wagstaff <ssw@cs.purdue.edu> wrote:
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
Congratulations.... was this factorization much easier than factoring a general 167 (or 160) digit number?
Yes, this c167 is much easier. I just finished the 136-digit number
n = (2^454 - 2^341 + 2^227 - 2^114 + 1)/13
(a divisor of (2^1362 + 1)/(2^454 + 1)). The sieving took 85 machine-days (about two weeknights) on a network of 60 SGI machines, and took advantage of n's representation as a polynomial in 2^113. Last year's factorization of RSA130 (130 digits) took 6 calendar-months to sieve, at multiple sites. By the way, the new factorization is n = p49 * p88, where
p49 = 2393102462756185953833037662530180237989024296581 p88 = 14952485345141425227257136559467580083134337 \ 51379919088823926933276083374444560702796609
The c167 factorization of (3^349 - 1)/2 was about as hard as doing a general number around 115-120 digits. -- Peter L. Montgomery pmontgom@cwi.nl San Rafael, California
A mathematician whose age has doubled since he last drove an automobile.