Factorisation of F10

F10 = 2210 = 21024 + 1 is the tenth Fermat number.

At 20 October 1995 two small prime factors of F10 were known:

F10 = 45592577 . 6487031809 . c291

Here c291 is a 291-decimal digit composite number. The small factors were found by Selfridge (1953) and Brillhart (1962). The composite number c291 has been the "most wanted number" ever since the factorization of F9 in 1990.

On 20 October I found a 40-digit prime factor p40 of c291:

p40 = 4659775785220018543264560743076778192897

The quotient is a prime p252 of 252 decimal digits. Thus we have the complete factorization

F10 = 45592577 . 6487031809  . 4659775785220018543264560743076778192897  . p252

The Computation

The computation to find p40 used Lenstra's elliptic curve method (ECM)
It took about 3000 curves with first-phase limit 2000000 to find the factor. This total includes some curves with smaller limits, appropriately weighted. Each curve with limit 2000000 requires 46 million multiplications modulo the 291-digit number to be factored, and this takes about 11 hours on a Sun Viking Sparc. Overall, the computation took about 140 Mflop-years.

Further Details

See my paper Factorization of the tenth Fermat number, Mathematics of Computation 68 (1999), 429-451.

Factorisation of F9 by ECM

It is possible to find the factorisation of F9 by ECM, although it was first found by SNFS.

Factor of F13

Using ECM on a Dubner Cruncher, I recently found a 27-digit factor of F13.

Richard Brent
26 October 1995
(revised 15 Feb 1996)