Featured Research

from universities, journals, and other organizations

A Mighty Number Falls

Date:
May 21, 2007
Source:
Ecole Polytechnique Fédérale de Lausanne
Summary:
Mathematicians and number buffs have their records. And at last, an international team has broken a long-standing one in an impressive feat of calculation. Mathematicians have just 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.

Mathematicians and number buffs have their records. And now, an international team has broken a long-standing one in an impressive feat of calculation.

Related Articles


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 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.

Although it is relatively easy to identify huge prime numbers, factoring, or breaking a number down into its prime components, is extremely difficult. RSA encryption, named for the three individuals who devised the technique (Ronald Rivest, Adi Shamir and Leonard Adleman), takes advantage of this. Using the RSA method, information is encrypted using a large composite number, usually 1024 bits in size, created by multiplying together two 150-or-so digit prime numbers. Only someone who knows those two numbers, the "keys", can read the message. Because there is a vast supply of large prime numbers, it's easy to come up with unique keys. Information encrypted this way is secure, because no one has ever been able to factor these huge numbers. At least not yet.

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.

The international team factored the current 307-digit behemoth using the "special number field sieve," a method devised in the late 1980s by Lenstra (then at Bellcore), his brother Hendrik, then a professor at UC Berkeley, English mathematician John Pollard and Mark Manasse from DEC. The 11-month job took a century of computer time.

A feat like this would have been unthinkable back in 1990 when Lenstra started applying number theory and distributed computing to the task of breaking factoring records. Increased computer power and refined computational techniques have raised the bar, and will continue to do so. "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.

Is the writing on the wall for 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."


Story Source:

The above story is based on materials provided by Ecole Polytechnique Fédérale de Lausanne. Note: Materials may be edited for content and length.


Cite This Page:

Ecole Polytechnique Fédérale de Lausanne. "A Mighty Number Falls." ScienceDaily. ScienceDaily, 21 May 2007. <www.sciencedaily.com/releases/2007/05/070521100535.htm>.
Ecole Polytechnique Fédérale de Lausanne. (2007, May 21). A Mighty Number Falls. ScienceDaily. Retrieved October 23, 2014 from www.sciencedaily.com/releases/2007/05/070521100535.htm
Ecole Polytechnique Fédérale de Lausanne. "A Mighty Number Falls." ScienceDaily. www.sciencedaily.com/releases/2007/05/070521100535.htm (accessed October 23, 2014).

Share This



More Computers & Math News

Thursday, October 23, 2014

Featured Research

from universities, journals, and other organizations


Featured Videos

from AP, Reuters, AFP, and other news services

Chameleon Camouflage to Give Tanks Cloaking Capabilities

Chameleon Camouflage to Give Tanks Cloaking Capabilities

Reuters - Innovations Video Online (Oct. 22, 2014) — Inspired by the way a chameleon changes its colour to disguise itself; scientists in Poland want to replace traditional camouflage paint with thousands of electrochromic plates that will continuously change colour to blend with its surroundings. The first PL-01 concept tank prototype will be tested within a few years, with scientists predicting that a similar technology could even be woven into the fabric of a soldiers' clothing making them virtually invisible to the naked eye. Matthew Stock reports. Video provided by Reuters
Powered by NewsLook.com
Internet of Things Aims to Smarten Your Life

Internet of Things Aims to Smarten Your Life

AP (Oct. 22, 2014) — As more and more Bluetooth-enabled devices are reaching consumers, developers are busy connecting them together as part of the Internet of Things. (Oct. 22) Video provided by AP
Powered by NewsLook.com
Google's Inbox Is The Latest Gmail Competitor

Google's Inbox Is The Latest Gmail Competitor

Newsy (Oct. 22, 2014) — Google's new e-mail app is meant for greater personalization and allows users to better categorize their mail, but Gmail isn't going away just yet. Video provided by Newsy
Powered by NewsLook.com
Free Math App Is A Teacher's Worst Nightmare

Free Math App Is A Teacher's Worst Nightmare

Newsy (Oct. 22, 2014) — New photo-recognition software from MicroBlink, called PhotoMath, solves linear equations and simple math problems with step-by-step results. Video provided by Newsy
Powered by NewsLook.com

Search ScienceDaily

Number of stories in archives: 140,361

Find with keyword(s):
 
Enter a keyword or phrase to search ScienceDaily for related topics and research stories.

Save/Print:
Share:  

Breaking News:

Strange & Offbeat Stories

 

Space & Time

Matter & Energy

Computers & Math

In Other News

... from NewsDaily.com

Science News

Health News

Environment News

Technology News



Save/Print:
Share:  

Free Subscriptions


Get the latest science news with ScienceDaily's free email newsletters, updated daily and weekly. Or view hourly updated newsfeeds in your RSS reader:

Get Social & Mobile


Keep up to date with the latest news from ScienceDaily via social networks and mobile apps:

Have Feedback?


Tell us what you think of ScienceDaily -- we welcome both positive and negative comments. Have any problems using the site? Questions?
Mobile iPhone Android Web
Follow Facebook Twitter Google+
Subscribe RSS Feeds Email Newsletters
Latest Headlines Health & Medicine Mind & Brain Space & Time Matter & Energy Computers & Math Plants & Animals Earth & Climate Fossils & Ruins