[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

No Subject



CC: 
From: [email protected] (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 <[email protected]> [email protected] (Paul Rubin) writes:
> >In article <[email protected]>,
> >Samuel S Wagstaff <[email protected]> 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    [email protected]    San Rafael, California
> 
> A mathematician whose age has doubled since he last drove an automobile.
>