Two Elliptic Curve Factoring Records


Professor Wagstaff announces two recent record factorizations by the Elliptic Curve Integer Factoring Algorithm, primes of 79 and 75 decimal digits.

On August 2, 2012, Wagstaff found the 75-digit factor
336842026814486816413712532665671525518487238461533945786937785048474675329
of 11304+1.

Ten days later, on August 12, 2012, he found the 79-digit factor
2302872188505279576573535015926441913945044975483579529517513795897664211127797
of 11306+1.

The previous elliptic curve record was a 73-digit prime found in 2010 by J. Bos, T. Kleinjung, A. Lenstra and P. Montgomery. That prime was the first one discovered with more than 70 digits. Before that, the records were primes of 68 and 67 digits found in 2009 and 2006, respectively. See Zimmermann's list of integer factorization records. The Elliptic Curve Method found primes with at least 40, 50 and 60 digits in 1991, 1998 and 2005, respectively. Given the world-wide effort being made in elliptic curve factoring, a factor of 75-digits was expected to appear about now. However, the 79-digit factor was a surprise. A factor that large should not have appeared for quite a few more years.

See also Zimmermann's top 50 list of largest ECM factorizations. The running time of the Elliptic Curve Method depends roughly on the size of the prime factor it discovers, rather than on the size of the number factored. This is why record Elliptic Curve Method factorizations are listed by size of the prime factor it finds. Click here for Brent's list of the largest factors found by ECM.

The Elliptic Curve Method was invented in 1985 by H. W. Lenstra, Jr. Many implementations of it have been made. The version we used was ecm-6.4 of GMP-ECM, written by P. Zimmermann, P. Leyland, A. Kruppa, D. Cleaver, B. Gladman, P. Gaudry, T. Kleinjung, L. Fousse, J. Papadopoulos and C. Bouvier. See GMP-ECM.

For the 75-digit factor of 11304+1 the bound B1=1e9 was used with sigma=3885593015. The program ran for about 100 minutes. The number factored had 181 digits. The prime factors had 75 and 107 digits. The elliptic curve group order was 2^2 * 3 * 5^2 * 13 * 41 * 11971 * 14923 * 15887 * 16333 * 119129 * 970961 * 3408437 * 10882111 * 38612713 * 173109949 * 1584686398147. Thus, B1=180e6 would have been large enough.

For the 79-digit factor of 11306+1 the bound B1=800e6 was used with sigma=3648110021. The program ran for about 75 minutes. The number factored had 191 digits. The prime factors had 79 and 113 digits. The elliptic curve group order was 2^2 * 3^3 * 5 * 17 * 29 * 31 * 127 * 197 * 673 * 3947 * 18481 * 938939 * 19305469 * 26324929 * 46026329 * 97707917 * 138483313 * 764489238641. Thus, B1=140e6 would have been large enough.


Send e-mail to Sam Wagstaff


(This page last modified September 24, 2012)