The New York TimesThe New York Times ScienceAugust 8, 2002  

Home
Job Market
Real Estate
Automobiles
News
International
National
Politics
Business
Technology
Science
- Earth Science
- Life Science
- Physical Science
- Social Science
- Space
- Columns
Health
Sports
New York Region
Education
Weather
Obituaries
NYT Front Page
Corrections
Opinion
Editorials/Op-Ed
Readers' Opinions


Features
Arts
Books
Movies
Travel
Dining & Wine
Home & Garden
Fashion & Style
New York Today
Crossword/Games
Cartoons
Magazine
Week in Review
Multimedia
College
Learning Network
Services
Archive
Classifieds
Personals
Theater Tickets
Premium Products
NYT Store
NYT Mobile
E-Cards & More
About NYTDigital
Jobs at NYTDigital
Online Media Kit
Our Advertisers
Member_Center
Your Profile
E-Mail Preferences
News Tracker
Premium Account
Site Help
Privacy Policy
Newspaper
Home Delivery
Customer Service
Electronic Edition
Media Kit
Community Affairs
Text Version

Discover New Topics in Depth


Find More Low Fares! Experience Orbitz!


Go to Advanced Search/Archive Go to Advanced Search/Archive Symbol Lookup
Search Optionsdivide
go to Member Center Log Out
  Welcome, arasr

New Method Said to Solve Key Problem in Math

By SARA ROBINSON

Three Indian computer scientists have solved a longstanding mathematics problem by devising a way for a computer to tell quickly and definitively whether a number is prime - that is, whether it is evenly divisible only by itself and 1.

Prime numbers play a crucial role in cryptography, so devising fast ways to identify them is important. Current computer recipes, or algorithms, are fast, but have a small chance of giving either a wrong answer or no answer at all.

Advertisement


The new algorithm - by Manindra Agrawal, Neeraj Kayal and Nitin Saxena of the Indian Institute of Technology in Kanpur - guarantees a correct and timely answer. Though their paper has not been published yet, they have distributed it to leading mathematicians, who expressed excitement at the finding.

"This was one of the big unsolved problems in theoretical computer science and computational number theory," said Shafi Goldwasser, a professor of computer science at the Massachusetts Institute of Technology and the Weizmann Institute of Science in Israel. "It's the best result I've heard in over 10 years."

The new algorithm has no immediate applications, since existing ones are faster and their error probability can be made so small that it is practically zero. Still, for mathematicians and computer scientists, the new algorithm represents a great achievement because, they said, it simply and elegantly solves a problem that has challenged many of the best minds in the field for decades.

Asked why he had the courage to work on a problem that had stymied so many, Dr. Agrawal replied in an e-mail message: "Ours was a completely new and unexplored approach. Consequently, it gave us hope that we might succeed."

The paper is now posted on the computer science department Web page at the Indian Institute of Technology (www.cse.iitk.ac.in).

Methods of determining whether a number is prime have captivated mathematicians since ancient times because understanding prime numbers is the key to solving many important mathematical problems. More recently, attention has focused on tests that run efficiently on a computer, because such tests are part of the underlying mathematics of several widely used systems for encrypting data on computers.

So-called primality testing plays a crucial role in the widely used RSA algorithm, whose security relies on the difficulty of finding a number's prime factors. RSA is used to secure transactions over the Internet.


On Sunday, the researchers e-mailed a draft of the paper on the result to dozens of expert mathematicians and computer scientists. Dr. Carl Pomerance, a mathematician at Bell Labs, said he received the paper on Monday morning and determined it was correct.

After discussing the draft with colleagues over lunch, Dr. Pomerance arranged an impromptu seminar on the result that afternoon.

That he could prepare and give a seminar on the paper so quickly was "a measure of how wonderfully elegant this algorithm is," Dr. Pomerance said. "This algorithm is beautiful."




E-Mail This Article
Printer-Friendly Format
Most E-Mailed Articles
Reprints

Click Here to Receive 50% Off Home Delivery of The New York Times Newspaper.


Home | Back to Science | Search | Corrections | Help | Back to Top


Copyright 2002 The New York Times Company | Permissions | Privacy Policy
E-Mail This Article
Printer-Friendly Format
Most E-Mailed Articles
Reprints


Topics

 Alerts
Mathematics
Computers and The Internet
Create Your Own | Manage Alerts
Take a Tour
Sign Up for Newsletters

U.S. v. Microsoft: The Inside Story of the Landmark Case

Price: $24.95 Learn more.



You can solve today's New York Times crossword puzzle online. Click here to learn more.




Search Sales
Search Rentals
Find Commercial Space
Mortgage & Moving Services
* Mortgage Quotes
* Moving Quotes
* City Comparisons
* Mortgage Payment Calculator
Presented by Monstermoving.com