On March 27, 2010, Michael Vang found a 54-digit factor of F12 using GMP-ECM.
F12 is the 12th Fermat number 2^(2^12)+1 = 2^4096 + 1. Fermat numbers are of
special interest for integer factorization, and F12 is the smallest unfactored
Fermat number. F11 = 2^2048+1 was completely factored in 1988 by Brent and
Morain, and F10 = 2^1024+1 was completely factored in 1995 by Brent [1].
About F12. Before Michael Vang's discovery, we knew the following factors:
F12 = 114689 * 26017793 * 63766529 * 190274191361 * 1256132134125569 * c1187
where c1187 denotes a composite number of 1187 digits. Michael Vang found a
54-digit factor of c1187 [3]:
c1187 = 568630647535356955169033410940867804839360742060818433 * c1133
where c1133 is still a composite number, of 1133 digits. This 1133-digit
cofactor is still out of reach of factorization algorithms such as NFS
(which was used recently to factor the 232-digit number RSA-768), thus
the best hope to complete the factorization of F12 is that another factor
is found by ECM.
About GMP-ECM. GMP-ECM is a program for integer factorization using the
Elliptic Curve Method (ECM). ECM was invented by Hendrik W. Lenstra, Jr.
The first version of GMP-ECM was written by Paul Zimmermann, using the
GNU MP (GMP) library for efficient arithmetic. Several people contributed
to GMP-ECM, in particular Pierrick Gaudry developed some efficient assembly
code for Stage 1, and Alexander Kruppa developed (among other contributions)
some special-purpose code to factor Fermat numbers. This part of the ECM code
was used by Michael Vang. For more on GMP-ECM or to download the program,
visit [2].
About the lucky curve. The curve used by Michael Vang has sigma=1428526317,
and the corresponding group order is:
2^4 * 3^2 * 7 * 17 * 293 * 349 * 8821 * 23753 * 65123 * 2413097 * 9027881 *
23759413 * 45947380867
The second-largest group order factor 23759413 is below the stage 1 bound
B1=43000000 used by Michael Vang, and the largest factor 45947380867 is below
the stage 2 bound B2=199103726650 used by GMP-ECM for this value of B1.
[1] http://prothsearch.net/fermat.html
[2] http://www.loria.fr/~zimmerma/records/ecmnet.html
[3] http://www.mersenneforum.org/showthread.php?p=209724