Mighty Mathematical Feat Accomplished

Three institutes collaborated to accomplish a Herculean task -- they determined the prime factors of a 307-digit, 1024 1017-bit number that could be used to encrypt messages and e-commerce transactions.

On March 6, computer clusters from three institutions --?? the EPFL, the University of Bonn and NTT in Japan -- reached the end of eleven months of strenuous calculation, churning out the prime factors of a well-known, hard-to-factor number that is a whopping 307 digits long.

“This is the largest ‘special' hard-to-factor number factored to date," explains EPFL cryptology professor Arjen
Lenstra. (The number has a special mathematical form – it is close to a power of two.) The news of this feat will grab the attention of information security experts and may eventually lead to changes in encryption techniques.

Lenstra and colleagues last factored a similarly formed 155-digit, 512-bit number on August 22, 1999.
Lenstra says that it took the team nine years to go from factoring a specially formed (read: relatively easy) number to factoring generalized 512-bit numbers, but suggests people should "stay tuned" to see how long it takes this time.

Factoring a number into its prime components is a daunting task.
This difficulty forms the basis of RSA encryption, which is a widely used public-key encryption algorithm that works by generating a number n -- the product of two large prime numbers p and q -- and encrypting a message based on it.

If an efficient algorithm can be found for obtaining p and q for any given n, the system will fall apart. To prove that no such algorithm exists, RSA has an open challenge for people to factor various values for n; $605,000 is still waiting to be collected by any worthy competitor.

It has kept me awake for about four years, but I have yet to find a full solution; I would bet the US government has a way.

Update (5:xx pm): I emailed Arjen Lenstra to ask what number they factored. His response in full, reprinted with permission:

[T]he number we factored is 2^1039-1. a factor 5080711 was known already, but could not be used to make it easier to factor (2^1039-1)/5080711. so, the 'difficulty' was equivalent to that of a 'special' 1039-bit number. please note that 1024-bit RSA moduli (which are not 'special') would be quite a bit harder -- but, we'll be getting there...

The 307-digit number is actually (2^1039-1)/5080711, which is 1017-bits.

In further emails, Lenstra said an epaper with further details may be posted in the next week or so. Lenstra also said that the number made it possible to use the special number field sieve, instead of the general number field sieve; the special number field sieve is faster.

A Mighty Number Falls [Ecole Polytechnique Fédérale de Lausanne]