RSA encryption relies on being able to find large primes. For quite some time, the Miller-Rabin test has been known to be able to determine whether a given number is prime with as great a likelihood as you wish (say, with likelihood of error much lower than the chances that your computer made a mistake). Thus the claim was that primality testing was very likely in P, although no algorithm for primality testing in P was known. Until now.
Continue reading →