..complete and total nonsense. Especially if you paid a survey company with a clear understanding of what kind of results you want. Can you imagine them publishing a survey saying "1% of surveyed users admit to copying illegal software, the rest either did not know or care".
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)) ).
Slashdot Mirror
..complete and total nonsense. Especially if you paid a survey company with a clear understanding of what kind of results you want. Can you imagine them publishing a survey saying "1% of surveyed users admit to copying illegal software, the rest either did not know or care".
900,000 servers, and they are all data-mining the internet for porn. Awesome.
First oppressed by the governments, and now oppressed by using Microsoft products. There is no mercy in this world.
Elad Verbin proved that floodit is NP-Hard more than a year ago. See the comments here: http://valis.cs.uiuc.edu/blog/?p=2005".
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.