Comment 900,000 servers... (Score 1) 127
Comment No mercy... (Score 1) 151
White House Correspondent Tweets His Heart Attack 77
Woman Tells State Judiciary Committee, "DoD Implanted A Microchip Inside Me" 222
Comment Earlier proof http://ithat NP-Hardness of floodit. (Score 1) 322
eBay Urges Rethink On EU Plan's "Brick and Mortar" Vendor Requirement 139
Seinfeld's Good Samaritan Law Now Reality? 735
US Grants Home Schooling German Family Political Asylum 1324
Comment We already knew that... (Score 5, Informative) 444
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.