From: stewarts@ix.netcom.com
Date: Sat, 22 Feb 1997 00:48:06 -0800 (PST)
To: cryptography@c2.net
Subject: No Subject
Message-ID: <199702220848.AAA21157@toad.com>
MIME-Version: 1.0
Content-Type: text/plain


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