Two Recent Factoring Records

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

The records are based on factoring large numbers -- finding the numbers to multiply together to get other numbers -- using sophisticated computer algorithms. Numbers that can only be divided by themselves and 1 without leaving a remainder are "prime" numbers. Examples of prime numbers are 2, 3, 5, 7 and 11. All other numbers are composite -- they can be divided by some prime numbers without leaving a remainder. For example, 3 and 5 are the prime factors of 15.

The Elliptic Curve Factoring Algorithm uses mathematical objects called elliptic curves to try to find a prime factor of a large number. Each elliptic curve tried has a small but positive chance of finding a prime factor of a number. The chance of success decreases as the size of the unknown prime factor increases. Many mathematicians and computer scientists around the world try thousands of elliptic curves every day in efforts to factor various large numbers of interest. As this work is performed, occasionally a new record largest prime is found. Prime factors having 30 or 40 decimal digits are discovered frequently. Less often a prime with 50 to 60 digits is found. Before August, 2012, the record sizes of primes found by the Elliptic Curve Method were one 72-digit prime and two 73-digit primes.

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

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

To give some sense of the size of this second number, 11306+1 means 11 multiplied by itself 306 times with 1 added: 11 x 11 x 11 x 11 x ... x 11 + 1. The resulting number is 319 digits in length, begins with 4636194, and ends with 389562.

On September 11, 2012, R. Propper discovered a 75-digit prime factor (a bit smaller than Wagstaff's 75-digit one) using the Elliptic Curve Method.

Given the world-wide effort being made in elliptic curve factoring, a factor of 75 digits was expected to appear approximately in 2012. However, the 79-digit factor was a surprise. A prime factor that large should not have appeared for quite a few more years. Another surprise was that Professor Wagstaff had tried only a few thousand elliptic curves on the number factored when the 79-digit factor appeared. Each of these curves had less than one chance in a million of discovering the 79-digit prime. It is as if Professor Wagstaff bought 1000 one dollar lottery tickets once and won the million dollar prize!

The Elliptic Curve Method was invented in 1985 by H. W. Lenstra, Jr. Many implementations of it have been made. The version 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.

Send e-mail to Sam Wagstaff

(This page last modified September 24, 2012)