 News Home
 Hot Topics
Current
 Categories
 From the Magazine

17 April 2014 12:48 pm ,
Vol. 344 ,
#6181

Officials last week revealed that the U.S. contribution to ITER could cost $3.9 billion by 2034—roughly four times the...

An experimental hepatitis B drug that looked safe in animal trials tragically killed five of 15 patients in 1993. Now,...

Using the two highquality genomes that exist for Neandertals and Denisovans, researchers find clues to gene activity...

A new report from the Intergovernmental Panel on Climate Change (IPCC) concludes that humanity has done little to slow...

Astronomers have discovered an Earthsized planet in the habitable zone of a red dwarf—a star cooler than the sun—500...

Three years ago, Jennifer Francis of Rutgers University proposed that a warming Arctic was altering the behavior of the...


17 April 2014 12:48 pm ,
Vol. 344 ,
#6181
 ScienceNow
 ScienceInsider
 ScienceLive
 About Us
Loooooooooong Division
23 May 2007 (All day)
A team of mathematicians has set a new record for factoring a large number into primes, breaking a massive 307digit number into its three indivisible factors and besting the previous mark by 30 digits. Written as a binary string of zeros and ones, the number is 1017 places or "bits" longnearly as long as the 1024bit numbers currently used to encode electronic messagesand the researchers' method of using a network of computers raises the prospect of hijacking PC and videogame systems to try to crack codes. However, security experts say they're confident they can stay ahead of wouldbe hackers.
To keep financial transactions or military intelligence under wraps, these secret messages are transformed into strings of numbers, which are then multiplied or otherwise mixed up with other large numbers that serve as "keys" for scrambling and decoding the message. For example, the widely used RSA encryption scheme uses two keys. A public key is essentially a very large number that is the product of two prime numbers and is available to everyone. A private key consists of the two prime numbers. The public key allows anyone to send an encrypted message, but only the holder of the private key can read it, using the two prime numbers to unlock the original message. The only known way to crack RSA is to factor the public key, which requires long, bruteforce calculation. Nevertheless, in 1999 researchers mustered enough computing power to show that 512bit public keys then commonly used in Europe could be factored into the primes (Science, 3 September 1999, p. 1472). That result led to an increased adoption of 1024bit keys.
To factor the 1017bit behemoth, Thorsten Kleinjung of Bonn University and colleagues distributed the number crunching over hundreds of computers that among them tallied a total of 95 years of processing time. Previously, one important step in the computation, called the matrix step, had to be performed by a large cluster of computers in a single location. "What is a really new aspect of this work is that we have been able to distribute this matrix step over [computers at] different locations," says Arjen Lenstra of the Swiss Federal Institute of Technology in Lausanne. The team reported the result in an open memo to their fellow mathematicians.
The result raises the possibility that criminals might someday commandeer computers on the Internet to crack codes, Lenstra says. In fact, Play Station 3 videogame systems, which are optimized for number crunching and typically connected to the Internet, could provide a useful resource for such chicanery. Kleinjung and his colleagues are now trying to get their hands on a substantial number of Play Stations. "We want to have thousands of them, or ten thousands, and see what analytic potential they may have," says Lenstra.
Ronald Rivest, a cryptographer at the Massachusetts Institute of Technology in Cambridge and one of the developers of the RSA code, says that a real breakthrough in the basic mathematics of factoring large numbers might cause a problem, but meanwhile he is confident that RSA encryption will remain secure. "There are already recommendations to switch to keys of 2048 bits; ... the software is flexible," he says.
Posted In: