Turns out, Primes are in P

zorba1 writes "Manindra Agrawal et. al. of the Indian Institute of Technology Kanpur CS department have released a most interesting paper today. It presents an algorithm that determines whether a number is prime or not in polynomial time. While I haven't gone through the presentation in detail, it looks like a promising, albeit non-optimized, solution for the famous PRIMES in P problem."

Re:Big consequences related to encryption

[God! Awful]

Well, encryption based on the multiplication of large primes, anyway.

Yeah... that step in key generation where you check whether a candidate key is prime or not will now be performed with 100% confidence instead of that annoying 99.999999999999999% confidence we used to have.

-a

Re:Oh yeah? Well...

[braindead]

• I have developed an algorithm that will determine if any number less than a google is prime in O(1). Above a google it degrades pretty fast, though.

Aha... is that based on a precomputed sieve with 10^100 elements, by any chance? ;-)

(it's googol, by the way. Google.com is obviously not prime, based on the fact that they haven't IPO'd yet)

Re:Crypto repercusions?

[Anonymous Coward]

>I am by no means a heavy duty math cruncher or cypherpunk
.
.
.
>Start at 10^100 and count down using this algorythm

You do realize that there are 99999999999999999999999999999999999999999999999999 9999999999999999999999999999999999999999999999999 numbers between 10^100 and 10^99, don't you?

Re:Big consequences related to encryption

[Anonymous Coward]

That "proof" would have killed my CS professor.

Re:What's Polynomial Time?

[Kaz Riprock]

Back in the days of parachute pants, leg warmers, and the 80's, there was a man....a man with a rapping and dancing vision. His name...

MC Polynomial.

And he sang a song..."P can't Touch This". Before the drum break of this song, Poly sang:

It's a prime, because you know
P can't touch this
P can't touch this
Stop...Polynomial Time...

Thus giving rise to a branch of mathematical order functions denoting the complexity of a problem...

Either that or it's defined pretty well here [ic.ac.uk].

The question is

[einhverfr]

Whether polynomial time is longer or shorter than prime time.

Re:Big consequences related to encryption

[kyletinsley]

"If you can determine if a number is prime in polynomial time, you can break RSA in polynomial time."

Awww fuck polynomial time.... I'm still waiting for somebody to determine it in STOP! hammer time...

Doooooooo doo doo doo, doooooooooooooooooooo do - Can't crack this!

---
God that was stoopid... sleeeep goooood!

Re:p=np?

[welthqa]

how long have you guys been waiting for a topic on prime numbers, it's like your entire lives have been building up to this point. hurray!

It would be interesting...

[GnomeKing]

...if he HAD found a way to do factoring in P time... gotta wonder what would happen if he took a holiday to the states - I'm sure SOMEONE would try to have a go at him for breaking encryption

Re:What's Polynomial Time?

[Salsaman]

There is a remote island in the South Pacific called 'Polynosia' (not to be confused with 'Polynesia').

The island has a number of strange customs.

1) All the women on this island are called 'Polly' in reverence to the island's god, Polynose.

2) The men of the island are very philosphical (maybe because all the women are called Polly, so it gets very confusing). They spend most of their time poring over mathematical problems.

3) The island has strict laws on the use of technology. Telephones are not allowed, aircraft are not allowed to land there, in fact the only way to reach the island is by boat, nevertheless it is very popular with tourists.

4) It is considered offensive to Polynose for anyone who is not a Polynosian woman (a Polly) to prepare food. Since the island is popular with holiday makers though, all of the enterprising Polly's have opened small restaurants called 'Polly-meal-time'.

The men of the island, in order to discuss their mathematical musings, recently opened a cafe. To distinguish this from all the restaurants, they named it 'Polly-no-meal-time'.

The article reports that recently a boatload of mathematicians visited Polynose, and told the island's men how to check if a number is prime.

Thus the headline 'Primes can now be solved in Polly-no-meal-time'.

/me ducks :-)