Factorisation of F9 by ECM

F9 = 229 = 2512 + 1 is the ninth Fermat number.

In June 1990 F9 was factored using SNFS: see A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, and J. M. Pollard, "The factorization of the ninth Fermat number", Mathematics of Computation 61 (1993), 319-349.

The factorization is F9 = 2424833 . p49 . p99 where

p49 = 7455602825647884208337395736200454918783366342657

I was curious to see if it would be feasible to find the penultimate 49-digit factor by ECM. I tried many curves with the "birthday paradox" variant and first-phase limit 107 (slightly smaller than the predicted "optimal" limit of about 3 x 107). I expected that it would take about 90,000 curves.

On 29 April 1997, after trying about 73,000 curves, I "rediscovered" the 49-digit factor. The "lucky" elliptic curve is defined as in my report "Factorization of the tenth and eleventh Fermat numbers" [161] with parameter sigma = 862263446.

The group order is

22 . 33 . 52  . 7 . 331 . 1231 . 1289  . 6277 . 68147 . 1296877  . 9304783 . 9859051 . 44275577

Richard Brent
2 May 1997