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."
I can tell if a number is prime via:
bool isprime(p)
for i = 2 to sqrt(p)
if p mod i == 0
return false
endif
endfor
return true
endfunc
If I'm not correct, that algo is O(n), thus polynomial, thus in P. But for very large p, that algo is impractical.
Things you think are in the Constitution, but are not.
the ps version looks much better:
http://www.cse.iitk.ac.in/primality.ps
// FIXME: put sig here
If I'm reading this correctly, we've got a nearly guaranteed winner of the Nobel Prize here.
This would be more in line for a Fields Medal than a Nobel Prize.
hm... I'm not sure why it removes comparison symbols when set to plain text... oh well, I wrote out "is less than" this time
They're saying the the time T necessary to determine whether or not an N digit number is prime satisfies this equation:
T is less than N ^ k + a
for some values (can be any finite value) of k and a.
Basically, it's a statement about how well an algorithm scales to REALLY large numbers.
preview is your friend
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.
It's funny when I read the comments, and I see all kinds of stuff that reminds me of my Discrete Structures class (we did the P and NP stuff at the end)...
Makes me wonder what this means for computer theory, but if you think about it, polynomial time can still be slow for very large n with very big powers... although not as bad as an exponential with large n's (assuming you go out far enough that the exponential will grow faster then the polynomial)
Kudos to the team that discovered this
There are only 10 kinds of people in this world... those who understand binary and those who don't
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.
If by "superclass", you mean problems that are (thought to be) harder than the other set of problems, then yes.
But technically speaking, NP-complete problems actually form a "sub"class of NP problems.
And yes, primes is not _known to_ be a NP-complete problem, so this doesn't really affect complexity of 3-SAT directly.
a simple way to think of it:
an NP-complete (NP=non-polynomial) problem is one that can be solved, but takes about 8*age_of_universe time to solve. To get around this, approximation algorithms are used, but these can never give a 100% guarantee of finding the correct solution, nor may provide the same solution if it were to execute on the same data twice.
a polynomial-time problem is one that can be solved within our lifetimes, guarantee 100% accuracy, and can always generate the same solution for the same data.
there's a LOT more to it. The book Intro to Algorithms has a good chapter on the topic of NP-completeness, which will explain the intricate and gory details.
The One Rule Of Chess You'll Ever Need: Don't play someone who carries a kit in their bookbag.
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.
Out of interest, will this finding have any impact on the effectiveness of present day cryptography?
Probably not. While it is possible that this research could lead to results in speeding up factoring, a faster algorithm for determining whether a number is prime is not going to compromise the security of RSA.
Your RSA key pair is derived from 2 large primes. The way we generate keys is to randomly test large random numbers to see if any of them are prime. Ergo, we must already have an efficient formula for determining if a number is prime or not.
FYI, the most commonly used algorithm is Euler's formula. Euler's formula doesn't actually tell you if a number is prime, but it will usually give a non-zero output if the number is not prime, so if you run it enough times with different inputs, you can be 99.99999% sure that a number is prime. However, a small percentage of numbers are "pseudoprimes" -- numbers that are not prime but which will also satisfy Euler's formula. Therefore, after you discover a candidate prime, you should use a different (slower) formula to double-check.
Since this is fairly common knowledge among geeks who use encryption, I'm somewhat surprised that so many people here jumped to the same conclusion you did.
-a
How to rationalize theft.
NP stands for Nondeterministic Polynomial.
ie, it can be completed by a nondeterministic machine in polynomial time. The main problem with NP algorithms is that there aren't any nondeterminisitic machines around. (A nondeterministic machine can attempt all paths to try to reach a conclusion at once whereas a deterministic machine can only try one at a time.)
And the muscular cyborg German dudes dance with sexy French Canadians
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.
>I'm not sure why it removes comparison symbols when set to plain text...
Slashdot removes left angle brackets in an attempt to stop abuse. Since it still lets raw right angle brackets through for old style quoting (which I prefer), the left ones have to go on unverified tags.
To display a left angle bracket despite that you'll need to type its ISO code, which renders the bracket unusable for tags (which is a good thing).
ie: < is entered with this: <
Just something to note down FFR. Oh, and can be handy if you want to try to slip through some important, on-topic simple tables or ascii art. Sometimes. But not lately.
- o
<
\__/
If you could be told what you can see or read, then it follows that you could be told what to say or think - BoC
So I'm already sensing the level of confusion rising as this is a very confusing topic. Here's a quick review. Note: I'm going to do this on a higher level and not start talking about Formal Languages as this is not the place to teach it. So in loose terms, Problems that in P are easily solveable. For example, sorting is a problem in p. Proof: I can sort a set of n numbers in no worse than n^2 time using a bubble sort. (Yes - I know there's faster but this is an example). The bubble sort just compares every number to every other number. Assuming you didn't optimize the algorithm you'd compare each number to every other number and they'd be sorted in no worse than n*n = n^2 comparisons. So what is NP? NP are problems that given a proposed solution we can verify that the solution is correct or not in polynomial time. An example of this is factoring. (note: it is not known whether factoring is in P). Given current methods we know factoring a big number into its prime factors. But if I was to tell you that p=q*r you could very quickly multiply q*r and see if it is equal to p and "verify" my answer. Another way to think about it is you can try out one branch of computation in polynomial time. So what is NP-complete? NP complete problems are is follows. A problem is NP-Complete iff 1) The problem is in NP 2) A solution in polynomial time to this problem would yield a polynomial time solution to all other problems in NP. That is, no other problem in NP is harder than NP-Complete and if one NP-Complete problem is solveable in Polynomial time than all of NP is solveable in polynomail time, P=NP and you will win doctorates and a nobel prize, turing award and a million bucks from the clay institute for proving this. Sigh - you are probally still confused.. :)
If religous zealots don't believe in Evolution, then why are they so worried about bird flu?
This is old news (1997). If one looks at TAOCP Volume 2, third edition, page 396, there are three mentioned algorithms. One algorithm operates at O(log n)^5, proves with rigor, and depends on the proof of the extended Riemann Hypothesis(tm). There is also aother that is in (log n)^O(log log log n) that does not depend on unproven hypothesises, yet is not exactly P.
-Kevin
Indeed, primality has been known since the 80's to belong to the class RP (problems solvable in expected polynomial time by a randomised algorithm). It has never (in recent years) been suspected of being NP-complete. Most experts don't even think factoring is NP-complete.
(All this assuming P!=NP, or else all these distinctions collapse.)
no you dont need recursive call. as r is O(log(n)) so size of r is O(log log(n))) so if an exponential time algorithm is used for checking the primality of r, it'll be exp in log(log(n)) i.e. linear in log(n)
Same goes with q. as it's "small" you can afford an exponential algoritm.
also x is a variable, those eqns (12) really are polynomial eqns.
Note that this algorithm takes O((log n)^12). For this to actually be faster than, say, factoring n directly, and assuming a multiplicative factor of 1 in the order statistic, n has to be at least 3*10^22, or roughly 75 bits long. This algorithm is probably very ineffective at factoring small integers.
This post expresses my opinion, not that of my employer. And yes, IAAL.
no it wont as q is "small", as proved in lemma 4.2 r is O(log(n)^6) and so is an upper bound on q. so the size of q is O(log(log(n)) and an exponential time in that will be linear in log(n) !!
First off, 'x' doesn't matter. The loop at the bottom checks a congruence of two polynomials over two finite rings (if I'm reading it right, the first is generated by x^r-1 and the second by the input n). Simplistically, this amounts to grinding out the coefficients of the two polynomials and verifying that the difference of the polys equals zero, modulo the ring generator. The actual 'value of x' is never used.
Second, if you check the order statistic calculation, they're assuming worst-case on factoring 'r' (they apply order r^1/2 for that factorization). They then make an assumption that O(r^1/2) = O((log n)^3), or that O(r) = O((log n)^6), which seems rather suspect (as if they knew the answer ahead of time and plugged in a recursive value for it). Nevertheless, they do go to some length to show that such an r exists, and that it requires at most O((log n)^6) iterations of the first loop to find it.
As for 'q', I think again it is determined by brute-force factoring r-1. On the one hand, r is small; on the other hand, that doesn't mean a damn thing when it comes to dealing with order statistics, which I think is also a little suspect.
This post expresses my opinion, not that of my employer. And yes, IAAL.
I thought things that sounded the same but were spelled differently were homophones. I thought homonyms were spelled the same with different meaning.
YOUR NIT HAS BEEN PICKED!!!
NP-complete problem are no superclass of NP, but they are considered to be the hardest problems in NP. "The hardest problems in NP" means that if one finds and deterministic polynomial algorithm for a NP-complete problem, you could use this algorithm as a subprocedure for any problem in NP (every instance of a problem in NP can be reformulated as an instance of this NP-complete problem in det. pol. time) and therefore P=NP.
But it is more likely that there exists no det. pol. time alg. for any NP-complete probleme and so P != NP)
I was trying to keep it simple because the original poster said that he didn't know anything about theoretical CS.
Any sufficiently advanced technology is indistinguishable from a rigged demo
--Andy Finkel (J. Klass?)
He didn't jump to a conclusion. He asked a question.