77^108+1

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

        N = 1135671153553 * c124

where c124 is a 124 digit composite number given by

 c124 = 5916700930949690254961348443230914200304\
	2532792717122504696492697918413381795271\
	3899030068380285456195669381863172860518\
	8737

The two polynomials used were

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

with common root 77^12 (mod N).

  The region sieved was b < 907199 and |a| < 3670016.
A factorbase size of 200000 and large prime bound of
20M was used for both polynomials.
  A total of 2799213 relations was collected forming
a 442403 x 468435 matrix.

  The linear algebra stage took 10 CPU hours on a
375MHz Celeron using about 75 MB of memory, the square
root stage took 17 minutes and found the factorisation
in the first dependency checked.

  On May 13, 2000 it was found that c124 = p40 * p84

  p40 = 9142863113597035623974665029104113334881

  p84 = 647138741708876919560526895795021002626501858202824776079044988439712818160592210977

My NFSNET page
NFSNET homepage
Cunningham Project homepage