http://www.torontostar.ca/NASApp/cs/ContentServer?pagename=thestar/Layout/Article_Type1&c=Article&cid=1026144105926&call_page=TS_News&call_pageid=968332188492&call_pagepath=News/News

NEW DELHI (AP) — Indian computer scientists said Friday they have solved a mathematical problem that has eluded researchers for 2,200 years — and could be crucial in modern times in improving computer configurations.

A three-member team of scientists at the Indian Institute of Technology in the northern Indian city of Kanpur have devised a method that will make no mistake in quickly determining a prime number — those that are divisible only by themselves and the numeral 1.

Prime numbers hold the key to solving many mathematical problems and play an important role in cryptography — the art of writing or breaking codes. Scientists have long worked on ways to improve methods to identify a prime number.

Greek mathematician Eratosthenes was the first to raise this problem around 200 B.C., when he offered one way of determining whether a number is prime.

Computer scientists and mathematicians have since devised many faster ways to solve the problem, but all such methods carry a small risk of error. Some methods occasionally fail to detect a prime number, while others may select a non-prime number.

"Our algorithm is deterministic; it has no chance of committing any error," said Manindra Agrawal, the principal author of the formula. An algorithm is a set of instructions for solving a specific mathematical problem in a limited number of steps.

Agrawal and his two associates — Neeraj Kayal and Nitin Saxena — have authored a paper detailing the formula, which was posted on their department's Web site Sunday. Copies of the paper were also dispatched to leading computer scientists and mathematicians around the world.

"We have received several responses. All of them have expressed satisfaction with the new algorithm," Agrawal said by telephone. "No one has doubted our claim."

The new algorithm will have no immediate applications, however, because current methods used in computers are faster.

"We have used more steps than the current methods in use," explains Agrawal.

"Our first objective was to find a method that is foolproof. Now, I am sure other researchers, or maybe some of us, will start asking how can the number of steps be cut down and make the computation faster."

Surely they have computer programs that can work out if it's a prime number in like, a few seconds? (As in, so how's what they've got now an improvement?)

Still, makes a change from it being Americans. :p

Originally posted by Firefly
Surely they have computer programs that can work out if it's a prime number in like, a few seconds? (As in, so how's what they've got now an improvement?)
.

Computers can only find prime factorization quickly if it's a small number - if you have a humongous 500 digit number it can take a computer a very long time.

Does anyone know if this poses a threat to encryption schemes that are based on prime numbers, like RSA?

That's great.

Can I find a description of the algorithm anywhere on the net?

A prime number with hundreds of digits, takes weeks for a computer to check. Yes if primes can be found and numbers checked for primeness quickly it will weaken RSA and other cryptos.

The method the dudes found is simple to program, and different from the brute force of try dividing by each number till you get a hit or get above the square root. BUT (according to comentators) the new method is not drastically faster.

Heh, thought computers were faster than that. Still, suppose every little helps. Why are prime nunbers so essential in an encryption? (I really don't belong in this forum :p)

here is a small demonstration of how prime numbers are important for encryption:

it is not currently possible to factor very large numbers in a short amount of time. I will use that fact to encrypt my message. Lets say my message has 100 characters. i choose 100 primes, in ascending order. make them large primes. at least 10-100 digits each. then, i change each letter a-z to 1-26, and raise the corresponding prime to that power. for example, if the first prime is 11, the second is 13, and the first word of the message is "ad", then i will get 11^1 and 13^4 as my first two numbers. Finally, i multiply all those numbers together. it will be an enormous number, on the order of 10^1000 digits. but computers can do multiplication very very very fast.

now i send my huge number to my friend, and if she knows my list of primes, then she can just start dividing them and see if they are factors. it is quite easy to take a list of 100 primes and see if they are factors. dividing is almost as fast as multiplying.

someone who doesn t know the list of primes will never be able to factor the number. there is no way to check and see whether a number is prime (quickly). it would take many times the age of the universe to check a number with as many digits as i mention.

because of the prime factorization uniqueness theorem, when the friend factors the number, she will see a list of exponents over her primes, the exponents will be in the range 1-26, each one corresponding to a letter of the alphabet. she can now easily decode the message.

this is not really how encryption is done, this is too simple, and rather unpractical, but the underlying principal is the same.

the key is this: multiplying primes is easy, factoring them is hard. any process that cannot be undone is a loss in information. a gain in entropy. as soon as someone develops a way to easily check whether a number is a prime, then she won t need a key, a list of primes, to decode the message.

Might this breakthrough help in solving the Clay Mathematics Institute's Millenium Prize Problem concerning the Riemann Hypothesis?

http://www.claymath.org/prizeproblems/riemann.htm

Solve it and win $1,000,000! :)

The Riemann hypothesis asserts that all interesting solutions of the equation

What do they mean by "Interesting"? :confused:

By the way the fx was constructed (and extended) all even negative numbers were immediate --uninteresting-- solutions

That's very interesting. I would have thought computers were faster than that. From reading this thread, it seems like what the researchers did lessons the strength of common day encryption. Why is that a good thing? Does this new algorithm make it easier to develop a better encryption algorithm in some way? As you can tell, I'm lost in how this is better for security.