73^108+1

  Henrik Olsen announces the complete factorization of the number
N=(73^108+1)/(73^36+1) from Richard Brent's Factor Tables by the
Special Number Field Sieve (SNFS).  It was previously known that

        N = 14355864190873 * c122

where c122 is a 122 digit composite number given by

 c122 = 1005116928320330140943503035063152044013\
	8364308603498467772789731589554770700866\
	7408160401995423411850917898131374949092\
	57

The two polynomials used were

        X^6 - X^3 + 1 and
        X - 73^12

with common root 73^12 (mod N).

  The region sieved was b < 3337541 and |a| < 3670016.
A factorbase size of 200000 and large prime bound of
20M was used for both polynomials.
  A total of 2126001 relations was collected forming
a 823214 x 827565 matrix.

  The linear algebra stage took 32 CPU hours on a
375MHz Celeron using about 130 MB of memory, the square
root stage took 119 minutes and found the factorisation
in the fifth dependency checked.

  On Apr 22, 2000 it was found that c122 = p45 * p77

  p45 = 124010655803607210228737419021387688438676073

  p77 = 81050851784229770582594372775492791169028692268535791496748406582257650570209

My NFSNET page
NFSNET homepage
Cunningham Project homepage