Note Primes is in P was not a shock as a result. We already knew that the Riemann Hypothesis implied that primality could be decided in polynomial time. What was surprising about the result was how elementary the algorithm and the correctness proof were.
Note Primes is in P was not a shock as a result. We already knew that the Riemann Hypothesis implied that primality could be decided in polynomial time. What was surprising about the result was how elementary the algorithm and the correctness proof were.