Slashdot Mirror
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."
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
How to rationalize theft.
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)
>I am by no means a heavy duty math cruncher or cypherpunk
9 9999999999999999999999999999999999999999999999999 numbers between 10^100 and 10^99, don't you?
.
.
.
>Start at 10^100 and count down using this algorythm
You do realize that there are 9999999999999999999999999999999999999999999999999
That "proof" would have killed my CS professor.
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.
Mordor...a magical, mythical land where women are more rare than dragons--but where every man would rather find a dragon
Whether polynomial time is longer or shorter than prime time.
LedgerSMB: Open source Accounting/ERP
"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!
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!
100% Pure Evil With The Look And Feel Of Wholesome Goodness
...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
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'.