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."
the ps version looks much better:
http://www.cse.iitk.ac.in/primality.ps
// FIXME: put sig here
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.
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.
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
Power corrupts. PowerPoint corrupts absolutely.
From looking at the algo, I can't figure out what 'x' (or maybe it's a chi) is? Can someone help? I've looked it over, but couldn't find a definition of it. I'm also assuming that the 'if (r is prime)' line is a recursive call to itself? Also, how do we determine 'q' the 'largest prime factor of r-1' ? Another recursive call to get the factors? I must admit, I'm kind of lost by the algo, but it's still interesting.
Things you think are in the Constitution, but are not.
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.
Any sufficiently advanced technology is indistinguishable from a rigged demo
--Andy Finkel (J. Klass?)
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.
look here.
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.
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).
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.
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.
Freedom is not the license to do what we like, it is the power to do what we ought.
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
We give a deterministic O((log n)**12) time algorithm for testing whether a number is prime.
[Sorry, the Slashdot filter does not allow me to superscript the 12.]
The algorithm takes O(log2(n)**12) time, where n is number being factored. If we optimistically assume that this algorithm can test the primality of a 16-bit number in one microsecond, then here is how long it would take to test time primality of some larger numbers.
I don't know what a realistic base time for this algorithm really would be, and I don't know where the cross over point against existing exponential time deterministic primality testing algorithms would be, but at least this provide a sense of how log2(n)**12 grows.
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'.
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.
Unlimited growth == Cancer.