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

Comments

for the sake of our eyes

[fatmav]

the ps version looks much better:
http://www.cse.iitk.ac.in/primality.ps

Re:I always thought is was in P

[Anonymous Coward]

For P, it has to be polynomial in the size of _the input_. The input size here is log(n) since it requires log(n) bits to represent n. log(n)^12 hence is polynomial (which i believe their algo guarantees), whereas sqrt(n) is not.

Factoring might still be NP

[IntelliTubbie]

For those of you wondering about the implications for cryptography, this does not imply that composite numbers can be factored in polynomial time. This algorithm is simply a primality test -- that is, it tells you whether or not a number has any proper divisors (in polynomial time), but it doesn't tell you what these divisors actually are. Determining whether a number is prime has always been considerably easier than finding the prime factorization.

In fact, for schemes like RSA -- where the key is the product of two large primes -- we already know that the number is composite, by definition, so a more efficient primality test doesn't give us any new information.

Cheers,
IT

Re:What's Polynomial Time?

[Goonie]

The technical definition is kinda long and complex, but in essence it's like this. Given a problem of some size n, a polynomial time algorithm is guaranteed to give a solution in time proportional to a polynomial of n. If a polynomial-time algorithm exists that solves a problem, then the problem is said to be in polynomial time.

To give an example, say you've got a list of numbers and you want to know the sum. That can be done in linear time - ie, the time taken is proportional to the length of the list of numbers. The size of the problem (n) is defined by the length of the list and the time taken (T) is as follows: T = c1 * n + c0, where c1 and c0 are some fixed constants. The formula for T is a polynomial, and so the problem "LIST-SUM" is in polynomial time. It would still be in polynomial time if the formula for T was a polynomial with n^2, n^3, n^50 terms in it, or even terms like n^1.5 (because as n grows very large an n^1.5 term will always be smaller than an n^2 term).

Showing you an example of something outside polynomial time is a little more difficult, but some standard examples are SAT (the satisfiability problem) or the travelling-salesman problem, which you can read about in any book on the subject.

Re:If this is true...

[ipfwadm]

They could have easily taken over the infrastructure of a modernized computer-bent, encryption-shielded society such as the US or Japan.

Primality testing and factorization are not one and the same. It is possible to know that a number is not prime without knowing its factors. Breaking encryption requires factoring the product of two huge primes (it is already known that the number you're trying to factor is NOT prime, so Primes being in P is more or less useless by itself for this particular application), and factorization has yet to be shown to be in P.

If you're confused by "P" and "NP"....

[Erpo]

look here.

Implications

[davemarmaros]

There are 2 different problems:
1) Determining if a number is prime [is 909 prime?]
2) Determining the factors of a number [what are the factors of 909?]

This article claims to be able to solve problem 1 in Polynomial time.

However, problem 2 is MUCH harder, and that is the one which will break cryptography as we know it. This article does not claim to solve problem 2, so we're safe for now.

We already knew that...

[FalafelXXX]

The famous result by Miller 1976 (and indepdently rediscovered(?) by Rabin 1980) already did that. The only difference is that their algorithm was in RP (randomized polynomial). Namely, if the algorithm says it is prime it might be wrong (with probablity half, say), and if it says that the number is not prime, then it is not prime for sure.

Now, if you have a number n, you run this algorithm, say 20*log(n) times. If the algorithm says it is prime on all executions that it is prime, you know damn sure it is. If it says it isn't, you are sure it isn't. There is a rediclously tiny probablity that if the algorithm claims that it is prime in all executions, that it is still not prime. This probablity is so small, that it can be essentially ignored. Now, random bits are cheap nowadays, so this is quite satisfactory. This is in fact the algorithm that turned the RSA crypto system into a practical and useful algorithm, because suddently finding primes became easy.

To break RSA, and become really famous, one has to come up with a polynomial time algorithm for factoring. It might even be that RSA can be broken without factoring, but this is still an open question (I think).

Ahh, and BTW. Polynomial time means polynomial time in the size of the input. So if the number is n, the size of the input is O(log(n)), and the running time needs to be O( (log(n))^(O(1)) ).

Ok. End of boredom.

Re:We already knew that...

[Mornelithe]

I probably really shouldn't be replying, because it's been a while since I read how it works, but I can copy the algorithm and tell you where I think it would break (if at all). Please correct me where I'm wrong.

1. Generate two random primes p and q
2. Calculate n = pq and phi(n) = (p - 1)(q - 1) = n - (p + q) + 1 (Note: phi(n) is the number of primes less than n (Euler's totient function, I believe). phi(p) = p - 1 for prime p, and phi(pq) = phi(p)phi(q) for p relatively prime to q (note, this step breaks if p or q aren't prime))
3. Generate e
4. Calculate d, the inverse of e (mod phi(n)) (i.e. d*e = 1 (mod phi(n)))
5. is the enciphering key, is the deciphering key
6. For plaintext P, you get ciphertext C by doing: C = P^e mod n, and get P back by doing P = C^d mod n

So, now there's the matter of why it works. Here we go:

• Because of Fermat's Little Theorem, we know that a^(phi(n)) = 1 (mod n)
• Since ed = 1 (mod phi(n)) we have: ed = 1 + k*phi(n) for some integer k
• So, if we encipher and decypher, we have: (P^e)^d = P^(ed) (mod n)
• Which also means we have: P^(1 + k*phi(n)) = P*(P^(k*phi(n))) = P*((P^phi(n))^k) = P*(1^k) = P (mod n)

So when p or q are not prime, phi(n) != (p - 1)(q - 1), so when you calculate d, you'll get something that doesn't negate the encrypting process (because its not a multiplicative inverse mod the real phi(n)), so you'll probably get junk when you decipher.

I don't really feel like doing a detailed analysis of the algorithm, but I imagine that this isn't used as a primality test because it's running time probably isn't polynomial time.

Primality testing has never been hard

[sasami]

This result, if true, is very interesting from a theory standpoint.

As far as practice, it's fairly irrelevant. Probabilistic primality testing can be done in constant time with bounded error.

The Miller-Rabin test will tell you if a number is prime with at most 1/4 probability of error. That sounds ridiculous, but the catch is that you can iterate it using a random parameter. Do the test twice and your probability drops to 1/16. Do it fifteen times and your chances of being wrong are about one billionth.

If you're truly paranoid, do it 50 times. That'll bring the error rate of the algorithm magnitudes below the error rate of your hardware.

---
Dum de dum.