77^99+1

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

        N = 3 * 37 * 199 * 1567 * 1198261 * c111

where c111 is a 111 digit composite number given by

 c111 = 7773048638325342429281290081062354044963\
	7573208042710474012782870810501234831072\
	0076311791338192562859855297311

The two polynomials used were

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

with common root 77^11 (mod N).

  The region sieved was b < 240000 and |a| < 1572864.
A factorbase size of 100000 and large prime bound of
20M was used for both polynomials.

  A total of 2010500 relations was collected forming a
  277k X 278k matrix.

The linear algebra stage took 4.5 hours on a 350MHz P-II, using about 64MB
of memory, the square root stage took 15 minutes and found the factorisation
in the first dependency checked.

  On Jan 11, 2000 it was found that c111 = p44 * p68 where

p44 = 45495610700908433529819589513080984946748161

p68 = 17085271564824019592126711738403460516260822908889472733271104325151

My NFSNET page
NFSNET homepage
Cunningham Project homepage