New Method Said to Solve Key Problem in Math

The New York Times ^ | August 8, 2002 | Sara Robinson

[I Hired Craig Livingstone]

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.

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

[I Hired Craig Livingstone]

Thought some of you all might find this interesting.

[Seeking the truth]

I did, thanks for posting.

[SkyRat]

No secure comunication anymore? Isnt this new way to compute primes the out for encryption programs like PGP?

[TrappedInLiberalHell]

These are three young mathematicians in their prime. Literally.

[Guillermo]

Nerds.

[I Hired Craig Livingstone]

I you're interested, it's also worth checking out the web site and looking at the algorithim. It's amazing how "simple" solutions are that have baffled man for centuries.

[Doc Savage]

God, I love your name. Wish I'd thought of it!! Great tag!

[Robert A Cook PE]

Thought the biggest "math" problem nowdays was a high-school graduate calculating 1+1 ..

[I Hired Craig Livingstone]

That's what I was thinking as I read it, too. Although, the article seemed to indicate that previously primes could be determined to an extremely high degree of accuracy anyway.

Hopefully someone with some math/computer science knowledge will show up on this thread and clear that up.

[I Hired Craig Livingstone]

I thought it was pretty funny, too, until I realized people might think I was Hillary!

[LibWhacker]

No secure communication anymore?

Apparently, this new algorithm is not as fast as some we already have. So we're safe. However, it does give you a definitive answer; no more fussing around with probabilities: "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."

[Paradox]

Gee, when was the last time a discovery of this magnitude was announced, coming from an Islamic country? Seems the Hindu's of India spend more time thinking about the nature of the universe, over thinking how to remove themselves from it.

A bump for the Indians, who make great immigrants to this country too.

[Doctor Stochastic]

Well, I read the paper last Monday so here's my summary. It's a breakthrough in theory. The point is that it is not really very easy to determine if a large number P is prime. Dividing by all the numbers smaller that the Sqrt(P) obviously takes Sqrt(P) time. If P is several hundred digits long, this is too expensive.

There are randomized methods of determining if P is a prime. One method is to picke a number a much smaller than P and compute a**(P-1) mod P (meaning, when a number is bigger than P, replace it by the remainder on dividing by P). If the result is not 1, then P is not prime. If it is 1, then P is most likely prime. The test fails less than 1/2 the time. If two a's are used, the probability of failure is 1/4, three a's give 1/8, etc. Of course one may be wrong but that is unlikely to happen.

There are other methods of determining if P is a prime but they are a bit more expensive (having to do with elliptic curves, etc.)

The paper under discussion gives a deterministic (not random, no failures) method of proving P is a prime. This method takes Log(P)**12 operations. (Trial division takes Log(P)**(P/2) for example.) The method works on the principle that all the binomial coefficients of (x+y)**P are divisible by P (except for the first and last) if P is a prime.

So given a large number P, it is possible to test if P is prime with no more than Log(P)**12 operations. It's a great result.

[I Hired Craig Livingstone]

I think I got most of that. :)

Thank you!

[Reeses]

So we're safe.

The NSA has gotten awfully quiet these days about public key cryptography. I suspect it’s because they have developed clever methods of determining the factors of very large primes. It may take a $500 million computer to do the attack but if they could do it they wouldn’t be telling anybody. Any discoveries about primes are probably kept top secret because of the proliferation of public key cryptography. Most mathematicians are employed by the NSA and are not able to brag about their discoveries. If anything you want to transmit must be kept absolute secret, a good first step is to exchange your keys the old fashioned way.

[Reeses]

determining the factors of very large primes.

oops, let me correct myself: very large numbers. Primes don't have unknown factors.

[OBAFGKM]

PGP is still "PGP." The new algorithm provides only a sure-fire method of determining whether or not a large number is prime. Cracking PGP requires factoring a large number that's the product of 2 primes -- a much more difficult problem that nobody seems to have much of a handle on using conventional computers. (So-called "quantum computers" may eventually make PGP useless, but none have yet been built. Do a search on "Shor's algorithm" for more info.)

[LibWhacker]

It may take a $500 million computer to do the attack but if they could do it they wouldn’t be telling anybody.

Yep, this is where I'd put my money. I was watching a boring interview with some Senator the other day (I thought it might have been John Edwards, who sits on the Senate Intelligence Committee. But looking at his picture now, I don't think it was him.) and was about to fall asleep when suddenly he said something to the effect, I'm paraphrasing, now, "If I could tell you about the computers the NSA has in that building up there, it'd make business, industry and academia green with envy."

I wouldn't be too surprised if some top secret Manhattan Project for computers has constructed amazing next-generation hardware for use by the Pentagon and/or the NSA.

Cryptologists and cryptographers -- even those who don't work for the NSA -- have been complaining for at least 25 years about government oversight of their work and restrictions on publication. Some of it is classified before the author ever gets a chance to go to print. Not good for making rapid advances in the field, but necessary if we want to stay ahead of our enemies.

[ConvictHitlery]

Not exactly (about testing if a**(p-1) MOD p is equal to 1 or not). This WIDELY used method (based on Frmat's theorem) for a single "a", has an absolute certitude to confirm that a number is NOT prime, but has only a very good probability of confirming that the number is prime. However, if more values for "a" are used this probability improves only a little ( on the scale of numbers with 200 digits). This is because there are non prime numbers "p" for which this test will fail for any "a". These are the so-called McMichael numbers. Fortunately, they seem to have multiple small factors, so a pretest to check if "p" divides evenly by lets say the first 1000 prime numbers will weed out these "Fermat felons".

[B4Ranch]

ping