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:I always thought is was in P

[Walker]

What are you referring to as your input size n in O(n)? The number p? The correct size n is the number of digits of p. That algorithm is definitely non-polynomial for that (correct) n.

Re:Big consequences related to encryption

[DavidTC]

Of course, there's still a larger chance of a cosmic ray flipping a bit in the processor or memory then the math being wrong, anyway. ;)

This may seem like a strange question, but isn't a non-prime that passes the 99.99999999999% check just as good as a prime in encryption? I mean, seriously, is anyone really going to notice it's not prime? Sure, they could accidently stumble on the 'wrong' factors while trying decode it, but, seriously, halving the time to decode your message isn't a huge mistake, considering we're talking on the order of centuries at least. ;)

Impact on Crypto is Postive

[Majestik]

There have been comments as to the relation of this finding to the strength of modern prime depending crypto algorithms. Based on my understanding won't this increase the stength of crypto not decrease it.

Prime based encryption schemes (RSA,etc) are based on the complexity of factoring large numbers into primes, not the the ability to determine if a number is prime or not.

Incidently, many implementiotions make use of pseudo-primes, as the ability to validate primeness is (or was) cumbersome, and not actual primes. This should give implementations the ability to ensure key pair values are actual primes which would strengthen the resulting encryption.

Re:Big consequences related to encryption

[Goonie]

Uh, no. Just because you can tell whether a number is prime in polynomial time, doesn't mean you can find the factors of a number in polynomial time, as I understand it.

Re:Big consequences related to encryption

[tbo]

Thank you. I'm glad someone finally pointed out that we already have a classical (as opposed to quantum) probabilistic algorithm for determining primality. Every other fool on this board is running around wearing his/her tin hat and shouting about RSA being defunct. All this does is push primality testing from the BPP complexity class into the P complexity class. It is significant in the sense that it weakens the argument for BPP being larger than P.

Of course, we also have a polynomial-time algorithm for prime factorization (Shor's Algorithm). It's just that it requires a quantum computer, which is difficult to build. So far, the biggest number factored is 15... 1024 bit keys will be safe for a while yet. I believe it's 15 - 20 years until they're broken, if Moore's Law holds for quantum computers in terms of maximum number of qubits possible (so far, it roughly has, but then, we're only at about 7 qubits).

the most amazing part is...

[keshto]

this work was done by undergrads for their senior honors thesis under Dr. Agarwal's supervision. Isn't that amazing!!! Dr Agarwal was also my undergrad advisor- he is one amazing fellow and damn smart too!! I just wish my honors thesis had been even a fraction of this...

Re:bad in math?

[kavau]

Hold your breath... the algorithm is log2(n)^12 where n represents the number to be tested, not the number of digits. If you denote the number of digits by m, that is, m = log2(n), you get a complexity of O(m^12). The algorithm is therefore polynomial in the number of digits, with a very large exponent of 12. This large exponent could easily hamper the practical use of the algorithm, as Adam correctly demonstrated. The upshot is: Adam is right, RelliK is wrong!

Please STOP!

[phliar]

Everyone: just because you start out by writing "I'm no mathematician, but..." doesn't means you can pull crap right out of your ass. Words mean things, and when you talk about math, words mean things exactly. Please don't misuse them.

It's the Sieve of Eratosthenes. A number n is of size log(n). This is a deterministic algorithm; why bring up NP? What is the time complexity of division? And here's a hint: you start with n-digit (n=100) numbers and present an algorithm that runs in time 10^n. This is in P?

Has anyone actually read the paper? The algorithm is outlined, with a complexity analysis. Don't forget, P-time doesn't mean usable.