41^108+1

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

        N = c117

where c117 is a 117 digit composite number given by

 c117 = 1319585952970470476136194853869635810365\
	6821186281593277228314236145504842341663\
	3424896376324179188313624767689483041

The two polynomials used were

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

with common root 41^12 (mod N).

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

  A total of 2028830 relations was collected forming a
   245k x 253k matrix.

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

  On Jan 25, 2000 it was found that c117 = p37 * p80

  p37 = 2401875630912132869922741680893871713

  p80 = 5493981186983217750528321585817926391177\
	5897301024312507652843208265631162225857

  
My NFSNET page
NFSNET homepage
Cunningham Project homepage