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)