World Record for "Integer Factorization"; Used to Verify PKC Security

The fun and excitement just doesn't stop in the world of mathematics.

Let's see, the other day researchers at the University of Minnesota published a paper entitled When Two and Two is Not Equal to Four, then the folks at Wolfram Research announced Wolfram 2,3 Turing Machine Research Prize, and finally the news about the Godel Prize. Now we hear that mathematicians have broken a record of some kind or another by generating a hard-to-factor number that is a 307 digits long.

After nearly a year's worth of calculation, computer clusters of 146 PCs from the Ecoles Polytechniques Federales de Lausanne (EPFL), the University of Bonn,and NTT Corporation factored the 307-digit number using the special number field sieve, a technique devised in the 1980s by A.K. Lenstra, H.W. Lenstra, John Pollard, and Mark Manasse.

The experimental results show the completion of integer factorization for a world record of a 1017-bit composite number, a substantial increase over the special number field sieve method world record (911 bits). The results go on to show the factorization for (2^1039-1)/5080711, a special-type composite number. The difficulty in the integer factorization problem is the foundation of security and in regard to RSA encryption using the current 1024-bit encryption key as the mainstream. Consequently, the new world record is signifcant in that the effectiveness of the security and strength can be more precisely estimated.

Using the sieve program developed at the University of Bonn, NTT, EPFL, and the University of Bonn respectively provided 84.1 percent, 8.3 percent, and 7.6 percent of the calculation resources, and the calculation amount equivalent to 95 years of operation on a 3-Ghz Pentium D. PC clusters at NTT and EPFL, consisting of 110 and 36 PCs, respectively, were run in parallel for more than two months for the calculations. The results were 47 non-trivial solutions of the simultaneous equations defined by an approximate 70,000,000 x 70,000,000 large sparse linear matrix.

"This is the largest 'special' hard-to-factor number factored to date," explains EPFL cryptology professor Arjen Lenstra. (The number is "special" because it 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.

While relatively easy to identify huge prime numbers (that is, if you're an experienced mathematician with lots of computer power and several grad assistants), factoring numbers down into their prime components is hard. The most recent factoring record is RSA200, a 200-digit "non-special" number whose two prime factors were identified in 2005 after 18 months of calculations that took over a half century of computer time.

All this would not have been possible in 1990 when Lenstra began using number theory and distributed computing to factor. Increased computer power and better computational techniques have make all this possible. "We have more powerful computers, we have come up with better ways to map the algorithm onto the architecture, and we take better advantage of cache behavior," Lenstra explains.

What's nexst? 1024-bit encryption? "The answer to that question is an unqualified yes," says Lenstra. For the moment the standard is still secure, because it is much more difficult to factor a number made up of two huge prime numbers, such as an RSA number, than it is to factor a number like this one that has a special mathematical form. But the clock is definitely ticking. "Last time, it took nine years for us to generalize from a special to a non-special hard-to factor number (155 digits). I won't make predictions, but let's just say it might be a good idea to stay tuned."

Posted by Jon Erickson at 08:48 AM  Permalink